Existe-t-il des preuves de l’indécidabilité du problème d’arrêt qui ne dépend pas de l’auto-référencement ou de la diagonalisation?

C'est une question liée à celle-ci . En le reformulant sous une forme beaucoup plus simple après de nombreuses discussions, la question semblait totalement différente.

La preuve classique de l’indécidabilité du problème posé consiste à démontrer une contradiction lorsqu’on essaie d’appliquer à lui-même un hypothétique décideur HALT. Je pense que cela est juste dénotant l'impossibilité d'avoir un HALT decider qui décide lui - même s'arrête ou non, mais ne donne aucune information au - delà de la décidabilité arrêt de tout autre cas.

Donc la question est

Existe-t-il une preuve indécidable du problème en cours d’arrêt qui ne dépend pas de la démonstration que HALT ne peut pas décider seul, ni de l’argument de la diagonalisation?

Petit montage: je vais m'engager dans le libellé original de la question, qui demande une preuve qui ne dépend pas du tout de la diagonalisation (plutôt que de simplement l'exiger pour ne pas dépendre de la diagonalisation qui dépend de HALT).

Oui, il existe de telles preuves dans la théorie de la calculabilité (théorie de la récursivité).

Vous pouvez d' abord montrer que le problème de l' arrêt (le jeu ) peut être utilisé pour calculer un ensemble G ⊆ N qui est 1-générique signifiant que dans un sens chaque Σ 0 1 fait à propos de G est décidée par un préfixe fini de G . Il est alors facile de prouver qu'un tel ensemble G ne peut pas être calculé (c'est-à-dire décidable).$0'$$G\subseteq\mathbb N$$\Sigma^0_1$$G$$G$$G$

Nous pourrions remplacer ici 1 générique par 1-random, c’est -à- dire Martin-Löf random , pour le même effet. Ceci utilise le théorème de base basse de Jockusch-Soare .

(Attention: on pourrait simplement montrer que calcule le Ω de Chaitin , qui est 1-aléatoire, mais ici, nous devons faire attention à savoir si la preuve que Ω est 1-aléatoire repose sur le problème bloquant étant indécidable! Par conséquent, il est plus sûr de utilisez simplement le théorème de bas niveau).$0'$$\Omega$$\Omega$

Republié de mon commentaire selon la demande:

Commencez par observer qu'il existe des problèmes indécidables (argument de cardinalité simple) et, en outre, qu'il existe un problème indécidable P ayant un TM M qui reconnaît ses membres (mais ne peut pas se terminer sur des non-membres). Maintenant, résoudre HALT (M) vous donne un décideur pour P. Nous vérifions d’abord si M s’arrête sur x. Si c'est le cas, nous l'exécutons et retournons la même chose que M. Sinon, nous le rejetons, car M s'arrête sur chaque membre de P. C'est maintenant une contradiction puisque nous avons supposé que P était indécidable.

Remarque: Il a précisé qu'il recherchait un argument évitant la diagonalisation utilisant directement HALT, et non un argument évitant totalement la diagonalisation.

EDIT: Cet argument est bloqué. Pouvez-vous montrer directement que RE-REC est non vide, sans compter que HALT est présent?

Une autre affiche a fait allusion à cela (en faisant référence à Chaitin), mais vous pouvez utiliser le paradoxe de Berry pour prouver que le problème persistant est indécidable. Voici un bref croquis de la preuve:

Soit HALT une machine qui décide si une machine M s’arrête sur l’entrée I. Nous allons démontrer que HALT elle-même ne s’arrête pas sur une entrée particulière, ce qui montre qu’elle est incapable de choisir la langue.

Considérons la fonction suivante f:

f (M, n) = a, où a est le plus petit entier positif non calculable par la machine M sur une entrée quelconque I avec | I | <n

En supposant que HALT soit une fonction calculable, f est également une fonction calculable; simulez simplement HALT (M, I) pour chaque machine M et saisissez la chaîne I de longueur inférieure à n. Si la simulation s'arrête, simulez M (I), enregistrez le résultat et recherchez le plus petit résultat a qui ne soit produit par aucune des paires M, n.

Maintenant, nous montrons que f n’est pas calculable: considérons f (f, 10000000 * | f | +10000000). Quel que soit le résultat, il doit s'agir d'un entier (positif) non calculable par la machine calculant f sur l'entrée I avec une longueur inférieure à celle indiquée ... et pourtant, nous venons de fournir un tel entier avec f et beaucoup plus bref. contribution.

Ainsi, f n'est pas calculable, et donc notre hypothèse que HALT était calculable est fausse. Je ne crois pas que cette preuve utilise la diagonalisation.

Vous ne savez pas si cela compte, mais vous pouvez le prouver en utilisant le théorème de récursivité. Le théorème de récursivité dit si $\{W_e\}_{e=1}^{\infty}$$f$$e$$W_e = W_{f(e)}$$0$$f$$e$$0$$W_e$$0$$e$$W_e(0)$$W_{f(e)}(0)$