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

Rémi (2023-10-24T05:11:24Z)

@Ruxor

Merci beaucoup pour votre réponse!

Ruxor (2023-10-21T20:06:32Z)

@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é.

Rémi (2023-10-20T09:18:47Z)

Je sais que cet article de blog a été écrit il y a longtemps, mais je l'ai trouvé très intéressant et je ne peux pas m'empêcher de retenir une question. Vous avez écrit ceci:

"quand on décrit les choses comme ça, je pense qu'il est absolument impossible pour un débutant de s'en faire une intuition, encore moins de comprendre pourquoi les niveaux Δ¹₁ et Δ¹₂ sont beaucoup plus importants que tout ce qui vient après (ni pourquoi ce sont les ensembles Π¹₁, et pas les Σ¹₁, qui se comportent un peu comme les ensembles récursivement énumérables =Σ⁰₁"

Pourrais-je avoir plus de détails sur pourquoi Δ¹₁ et Δ¹₂ sont plus importants et en quoi (et pourquoi si ce n'est pas clair) les ensembles Π¹₁ ressemblent aux ensembles Σ⁰₁?

Je vous remercie pour votre article et votre éventuelle réponse.

Nick Mandatory (2022-05-09T14:55:39Z)

As-tu vu https://www.amazon.fr/Calculabilit%C3%A9-Beno%C3%AEt-Monin/dp/2916352961, qui parle de tellement de thèmes dont j'ai appris l'existence dans ce blog qu'on pourrait le croire écrit par toi, à ton insu (ce qui serait d'ailleurs une péripétie tout à fait dans l'esprit du blog) ?

Ruxor (2018-09-13T19:25:50Z)

@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.

jonas (2018-09-13T15:18:34Z)

On re-reading, it seems to me that your first definition for <URL: d.2015-11-16.2337.rigorous > rule (vii) is incorrect. It currently says:

> (vii) si, pour un certain p on a, pour tout i, que ‹p, ‹i›, 0› ∈ ℰ, alors ‹‹7›, ‹p›, 0› ∈ ℰ, tandis que si (toujours pour un certain p) on a, pour tout i, que ‹p, ‹i›, v_i› ∈ ℰ où v_i≠0, alors ‹‹7›, ‹p›, 1› ∈ ℰ

This version doesn't give your abstract machine more power than the Turing-completeness it already has, because it would be enough to call p for one input. That is you could expand ℰ to a strictly larger set by giving the following rule instead: (vii_0) if ‹p, ‹0›, 0› ∈ ℰ then ‹‹7›, ‹p›, 0› ∈ ℰ, but if ‹p, ‹0›, 0› ∈ ℰ for some v ≠ 0, then ‹‹7›, ‹p›, 1› ∈ ℰ. That's such a trivial function that you can even emulate it from the other rules, eg. I believe if ‹‹5›, ‹p›, r› ∈ ℰ then ‹‹5, ‹4›, ‹5, ‹6›, ‹3, 0›, ‹1, 0››, ‹1, 0›, ‹1, 1››, ‹p›, r› ∈ ℰ.

A version of rule that would correspond to the non_zero function defined above, and thus give the same hyperarithmetic power, would be the following: (vii_f) if, for a given p, ‹p, ‹i›, 0› ∈ ℰ for all i, then ‹‹7›, ‹p›, 0› ∈ ℰ; but if, for a given p, there are such v that ‹p, ‹i›, v_i› ∈ ℰ for all i and v_j ≠ 0 for some j, then ‹‹7›, ‹p›, 1› ∈ ℰ.

An intermediate rule between (vii_0) and (vii_♣), based on the note <URL: http://www.madore.org/~david/weblog/d.2015-11-16.2337.html#d.2015-11-16.2337.club >, would be this: (vii_m) if, for a given p, ‹p, ‹i›, 0› ∈ ℰ for all i, then ‹‹7›, ‹p›, 0› ∈ ℰ; but if, for a given p, there are such i and v that ‹p, ‹j›, 0› ∈ ℰ for all j < i and ‹p, ‹i›, v› ∈ ℰ and v ≠ 0, then ‹‹7›, ‹p›, 1› ∈ ℰ. The version (vii_♣) that you define later seems correct, and corresponds to the second part of that note.

Can you clarify what exact rule you meant to write, or why (vii) works as written?

DM (2017-01-05T21:57:23Z)

Que penses-tu de cette thèse:
http://www.theses.fr/2013PA010673/abes

ooten (2015-11-20T18:10:22Z)

Merci pour la réponse même si j'ai du mal suivre.

Ruxor (2015-11-20T13:01:42Z)

@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.

ooten (2015-11-19T21:02:42Z)

Y a-t-il des machines plus puissantes et intéressantes que les machines hyperarithmétiques ?

Ruxor (2015-11-19T15:08:26Z)

@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".

jonas (2015-11-18T10:24:55Z)

I agree that your definition seems to cover all computable functions over the natural numbers, and have drafted an argument on <URL: http://esolangs.org/wiki/Amycus >.


You can post a comment using the following fields:
Name or nick (mandatory):
Web site URL (optional):
Email address (optional, will not appear):
Identifier phrase (optional, see below):
Attempt to remember the values above?
The comment itself (mandatory):

Optional message for moderator (hidden to others):

Spam protection: please enter below the following signs in reverse order: 1cbff9


Recent comments