Comments on Qu'est-ce qu'une machine hyperarithmétique ?

@Rémi:

J'avoue ne pas me rappeler précisément pourquoi j'ai écrit ça (comme d'habitude, j'écris un billet de blog pour oublier le sujet après). L'idée générale que j'avais est probablement que Δ¹₁ a une caractérisation de type « calculabilité » / « constructibilité », de même que Π¹₁, et même Δ¹₂ si on tire un peu la ficelle, mais les niveaux plus élevés de la hiérarchie arithmétique n'ont rien de tel, j'ai vaguement le souvenir qu'ils ne sont pas du tout absolus ou pas du tout constructibles, ou quelque chose comme ça, mais je ne sais plus.

La réponse précise est certainement dans les livres de Barwise (“Admissible Sets and Structures” 1975) et Hinman (“Recursion-Theoretic Hierarchies” 1978) dans les Perspectives in Mathematical Logic — les deux sont censés être disponibles en ligne, d'ailleurs, je crois. Sur l'analogie entre Π¹₁ et Σ⁰₁, voir par exemple IV.§1–IV.§2 du livre de Hinman (ainsi que l'intro du chapitre IV) et théorème VIII.3.4 ibid, et aussi IV.§3 du livre de Barwise (p.ex. théorème IV.3.1). Sur Δ¹₂, voir plutôt du côté du chapitre V du livre de Hinman et V.§8 du livre de Barwise. (Passages trouvés après un parcours assez sommaire de ce qui peut être intéressant, il y en a un peu partout. Tout ça est certainement aussi dans le livre de Sacks (“Higher Recursion Theory” 1990), mais je ne l'ai pas autant consulté.

@jonas: Indeed, the version I meant to write is (vii_f). I edited the text accordingly. Version (vii_m) is equivalent (in the sense that it defines the same hyperarithmetic functions), and this fact is easy, while version (vii_♣) is also equivalent but harder to get.

@ooten: Il existe toute une hiérarchie de calculabilité supérieure, dont l'échelon hyperarithmétique est le plus bas. Cette hiérarchie correspond à des ordinaux qui ont des noms un peu exotiques et des descriptions plus ou moins naturelles ; pour certains échelons, on peut aussi décrire les choses sans parler d'ordinaux, comme je l'ai fait pour les machines hyperarithmétiques. Par exemple, si je renforce la capacité « être capable de décider si une suite de valeurs prend une valeur non-nulle » en « être capable de décider si une suite de valeurs prend une infinité de valeurs non-nulles », cela donne un type de machines encore plus puissantes (et associées à un ordinal qui porte le doux nom de « premier ordinal récursivement inaccessible »), on peut trouver qu'elles sont aussi assez naturelles et intéressantes. Il est difficile de dire où et comment cette hiérarchie s'arrête, parce que ça dépend de comment on définit les choses et ce qu'on est prêt à considérer comme une machine : il y a quand même une classe assez naturelle qui correspondrait à des machines monstrueusement puissantes (et essentiellement le plus gros au-delà duquel le terme de « machine » ne semble plus justifiable), ce qu'on appelle Δ¹₂, mais c'est un peu difficile à expliquer simplement en quoi cette classe consiste.

@jonas: There is a slight difference in rule 6 between what you wrote on <URL: http://esolangs.org/wiki/Amycus > and what I wrote: I had "if ‹p, a, v› ∈ ℰ then ‹‹6›, ‹p:a›, v› ∈ ℰ", whereas you changed this to "if ‹p, a, v› ∈ ℰ then ‹‹6›, ‹p,a›, v› ∈ ℰ" (the difference lies in the ‹p:a› versus ‹p,a› in second component of the RHS of the implication). In other words, if "6" is considered as an "eval" function, I had made the list (a) of arguments of the function/program (p) to be evaluated be the rest arguments of the eval function, whereas you introduced one more level of list. Both are equally legitimate, of course, and it's merely a question of taste; but the convention I used eliminates much, and presumably all (I didn't think about that too much), of the use(fulness) of "0".