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

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: 317ee7


Recent comments