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

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: >, 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:

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

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: 70ecdd

Recent comments