Preuve de l'indécidabilité du problème de l'arrêt

J'ai du mal à comprendre la preuve de l'indécidabilité du problème de l'arrêt.

Si renvoie si le programme s'arrête ou non sur l'entrée , pourquoi devons-nous passer le code de pour et ?a b P a $H(a,b)$$a$$b$$P$$a$$b$

Pourquoi ne pouvons-nous pas alimenter avec et une entrée arbitraire, disons, ?P $H()$$P$$x$

La preuve vise à trouver une contradiction. Vous devez comprendre quelle est la contradiction dérivée, afin de comprendre pourquoi est utilisé comme entrée pour lui-même. La contradiction est informelle: si nous avons une machine H (a, b) qui décide "a accepte b", alors nous pouvons construire une machine qui accepte des machines qui ne s'acceptent pas. (Lu que quelques fois jusqu'à ce que vous l' obtenez.) La machine représentée dans l'image - Appelons- - ne accepte pas ?M M ( P ) = P ⟨ P $P$$M$$M(P) =$$P$$\langle P \rangle$

La contradiction se produit lorsque vous demandez: accepte-t-il ? Essayez de trouver les deux options pour voir comment il y a une contradiction.⟨ M $M$$\langle M \rangle$

⟨ M ⟩ M ⟨ M $M$ accepte si et seulement si n'accepte pas ; c'est clairement une contradiction.$\langle M \rangle$$M$$\langle M \rangle$

C'est pourquoi il est essentiel pour la preuve d'exécuter sur lui-même et non sur une entrée arbitraire. Il s'agit d'un thème commun dans les preuves d'impossibilité appelées arguments diagonaux.$P$

Ignorez l'image pendant un instant; nous y reviendrons sous peu. Le programme est censé être un testeur d'arrêt: lorsque nous donnons à une entrée d'un programme (pensez à comme la liste d'un programme) et n'importe quoi pour , agit comme suitH a a b H ( a , b $H(a, b)$$H$$a$$a$$b$$H(a, b)$

1. Si le programme représenté par s'arrête lorsqu'il reçoit en entrée, répondra "oui". D'un autre côté, si le programme décrit par s'exécute indéfiniment lorsqu'il reçoit l'entrée alors répondra "non".b H ( a , b ) a b H ( a , b $a$$b$$H(a, b)$$a$$b$$H(a, b)$
2. Surtout, le programme s'arrêtera toujours et donnera la bonne réponse pour toutes les paires .( a , b $H$$(a, b)$

L'argument selon lequel est impossible à construire repose sur l'action d'un programme "pervers" particulier, , qui utilise comme sous-programme. prend comme entrée une liste de tout programme, , et fait ce qui suit:P H P $H$$P$$H$$P$$x$

P(x) =
  run H(x, x)
  if H(x, x) answers "yes"
      loop forever
  else
      halt

Ce n'est pas difficile de voir ça

$P(x)$ s'arrêtera si et seulement si le programme s'exécutera indéfiniment lorsqu'il recevra sa propre description en entrée.$x$

Jusqu'ici tout va bien: sera certainement un programme tant que son sous-programme sera un programme.$P$$H$

Revenons maintenant à l'image. Que se passe-t-il si reçoit sa propre description en entrée? L'image décrit juste ce scénario: Soit la description du programme , puis, en remplaçant dans la partie surlignée ci-dessus, nous auronsp $P$$p$$P$

P ( p $P(p)$ s'arrêtera si et seulement si le programme s'exécutera indéfiniment.$P(p)$

De toute évidence, ce comportement paradoxal est impossible, nous sommes donc obligés de conclure que le sous-programme ne peut pas être un testeur d'arrêt, car il échoue dans le cas où il est donné en entrée. Il peut y avoir d'autres cas où fonctionne comme il se doit, mais comme échoue dans au moins une situation, il ne peut pas s'agir d'un testeur d'arrêt complet, comme requis.( p , p ) H $H$$(p, p)$$H$$H$

Essayez une plus jolie preuve avec des animations. Et puisque les réponses doivent contenir plus qu'un simple lien vers un site, voici la réponse à votre question.

Rappelons d'abord comment fonctionne la preuve de la non-existence de l'oracle Halting. Nous prouvons que, étant donné tout candidat Hà un oracle Halting, il existe un programme Pet une entrée apour lesquels il Hne parvient pas à prédire correctement ce qui se P(a)passe.

Théorème: Soit Hn'importe quel programme qui prend deux entrées et renvoie toujours soit haltou loop. Il existe alors un programme Qet une entrée atels que Q(a)s'arrête si, et seulement si, H(Q,a)revient loop.

Preuve. Considérez le programme

program P(y):
  if H(y,y) = halt then
    loop forever
  else:
    return

Soit Q = Pet a = P. Soit H(Q,a) = haltou H(Q,a) = loop:

• si H(Q,a) = haltalors Q(a)(ce qui est juste P(P)) fonctionne pour toujours selon la définition de P.
• si H(Q,a) = loopalors Q(a)arrêtez par la definitoin de P.

QED

Vous avez demandé pourquoi nous avons envisagé H(P,P)au lieu d' H(P,X)un autre X. La réponse évidente est "car H(P,P)c'est ce qui fait fonctionner la preuve"! Si vous l'utilisiez H(P,X)pour un arbitraire X, vous seriez coincé. En effet, la preuve ressemblerait alors à ceci:

Preuve cassée. Considérez le programme

program P(y):
  if H(y,y) = halt then
    loop forever
  else:
    return

Soit Q = Pet a = Xpour certains arbitraire X. Soit H(Q,X) = haltou H(Q,X) = loop:

• supposons H(Q,X) = haltalors que nous ne pouvons pas dire ce qui se P(X)passe, car si les P(X)arrêts dépendent de ce qui H(X,X)revient. Nous sommes bloqués. Cependant, si nous le savions P(X)et que nous X(X)sommes les mêmes, nous pourrions progresser. (Donc, nous devrions vraiment prendre X = P).
• si H(Q,a) = loopalors nous sommes à nouveau coincés, et nous serions décollés si X = P.

Pas de QED.

J'espère que cela montre que nous devons tenir H(P,P)compte afin de faire fonctionner notre idée.

Le résultat de la preuve est cette analogie:

$P$$_{(P)}$$P^{\prime}$$_{(P^{\prime})}$$P$$_{(P)}$$_{(P)}$$_{(P)}$

$_{(P)}$$_{(P^{\prime})}$