Beweis der Unentscheidbarkeit des Halteproblems

25

Ich habe Probleme, den Beweis für die Unentscheidbarkeit des Halteproblems zu verstehen.

http://computing.guide/wp-content/uploads/2014/12/HaltingProblem1.jpg

Wenn zurückgibt, ob das Programm a bei Eingabe b anhältoder nicht, warum müssen wir den Code von P sowohl für a als auch für b übergeben ?H(a,b)abPab

Warum können wir mit P und einer beliebigen Eingabe, z. B. x , versorgen ?H()Px

Netik
quelle
Beachten Sie, dass in dem hier verwendeten Rechenmodell jede (codierte) Eingabe zulässig ist. Es gibt keine Typprüfung oder ähnliches. Sie können ein Programm jederzeit codieren und als Eingabe an sich selbst übergeben.
Asmeurer
2
Sie könnten füttern H jeder gewünschten Eingabe . Die Struktur dieses Beweises erfordert die Berücksichtigung einer bestimmten Eingabe.
David Richerby
1
Sie können dem Programm beliebige Eingaben hinzufügen. Ziel ist es, den Widerspruch zu finden. Theoretisch sollte die Maschine 'H' für alle Arten von Eingaben funktionieren. Damit betrachten wir eine aller möglichen Eingaben, was zu Widersprüchen führt.
Ugnes
Dieser Beweis ist subtil fehlerhaft. Überlegen Sie, ob ich ein H () habe, das für alles außer für sich selbst funktioniert. Das wäre immer noch eine allgemeine Lösung für das Halteproblem.
Joshua
Verwandte, möglicherweise doppelte: cs.stackexchange.com/questions/42819/…
Ilmari Karonen

Antworten:

27

Der Beweis zielt darauf ab, einen Widerspruch zu finden. Sie müssen verstehen, woraus der Widerspruch besteht, um zu verstehen, warum als Eingabe für sich selbst verwendet wird. Der Widerspruch ist informell: Wenn wir eine Maschine H (a, b) haben, die "a akzeptiert b" entscheidet, können wir eine Maschine konstruieren, die Maschinen akzeptiert, die sich selbst nicht akzeptieren. (Lies das ein paar Mal, bis du es bekommst.) Die auf dem Bild gezeigte Maschine - nennen wir es M - M ( P ) = macht PPMM(P)=P nicht akzeptieren ?P

Der Widerspruch entsteht, wenn Sie fragen: Hat M akzeptieren ? Versuchen Sie, die beiden Optionen herauszufinden, um festzustellen, wo ein Widerspruch besteht.M

akzeptiertM , wenn und nur wenn MMMM akzeptiert keine ; Das ist eindeutig ein Widerspruch.M

Aus diesem Grund ist es für den Beweis unerlässlich, auf sich selbst auszuführen und keine willkürlichen Eingaben zu machen. Dies ist ein häufiges Thema bei Unmöglichkeitsbeweisen, die als diagonale Argumente bezeichnet werden.P

aelguindy
quelle
38

Ignoriere das Bild für einen Moment. Wir werden es in Kürze bekommen. Das Programm soll ein Haltetester sein: Wenn wir H eine Eingabe eines Programms a (denken Sie an a als die Auflistung eines Programms) und überhaupt etwas für b , H ( a , b ) gebenH(a,b)HaabH(a,b) wirkt wie folgt

  1. Wenn das durch Programm bei Eingabe von b anhält , antwortet H ( a , b ) mit "Ja". Wenn andererseits das durch a beschriebene Programm bei Eingabe von b für immer läuft, dann ist H ( a , b )abH(a,b)abH(a,b) wird mit „Nein“ beantworten.
  2. Wichtig ist, dass Programm immer anhält und die richtige Antwort für alle Paare gibt ( a , b )H(ein,b) .

Das Argument, dass es unmöglich ist , zu erstellen, beruht auf der Aktion eines bestimmten "perversen" Programms, P , das H als Subroutine verwendet. P nimmt als Eingabe eine Auflistung eines beliebigen Programms, x , und führt Folgendes aus:HPHPx

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

Das ist nicht schwer zu sehen

stoppt genau dann, wenn das Programm xP(x)x für immer ausgeführt wird, wenn eine eigene Beschreibung als Eingabe angegeben wird.

So weit so gut: wird sicherlich ein Programm sein , solange sein Unterprogramm HPH ein Programm ist.

Kehren Sie jetzt zum Bild zurück. Was passiert, wenn eine eigene Beschreibung als Eingabe erhält ? Das Bild beschreibt genau dieses Szenario: Sei p die Beschreibung von Programm P , dann ersetzen wir den oben hervorgehobenen Teil durchPpP

wird genau dann angehalten, wenn das Programm P ( p ) für immer ausgeführt wird.P(p)P(p)

Natürlich ist dieses paradoxe Verhalten unmöglich, daher sind wir zu der Schlussfolgerung gezwungen, dass das Unterprogramm kein Stop-Tester sein kann, da es in dem einen Fall fehlschlägt, in dem es als Eingabe ( p , p ) angegeben ist . Es mag andere Fälle geben, in denen H so funktioniert, wie es sollte, aber da H in mindestens einer Situation ausfällt, kann es nicht wie erforderlich ein vollständiger Stop-Tester sein.H(p,p)HH

Rick Decker
quelle
Ich mag diese Antwort. Obwohl ich den Beweis jetzt verstehe, scheint es nur zu beweisen, dass H eine Ausnahme für die Rekursionsgrenze auslösen kann.
Fax
2
@Fax Hwird nicht mehr als einmal aufgerufen, es gibt überhaupt keine Rekursion P. H(P, P)wird nicht ausgeführt P, es wird nur "magisch" bestimmt, ob Pangehalten wird oder nicht, wenn es selbst übergeben wird.
Ajedi32
@ Ajedi32 H(P,P)muss nicht ausgeführt werden P, aber es muss ausgeführt werden, um H(x ↦ H(x,x), P)zu bestimmen, ob Pangehalten wird. Welches erweitert sich H(x ↦ H(y ↦ H(y,y), x), P)und so weiter.
Fax
@Fax Die Implementierung von Hist in diesem Proof nicht angegeben. Also nein, es nicht haben nichts ausführen , um, ob das sein Poder sich. Der Beweis beginnt mit der Annahme, dass irgendeine Art von Programm Hexistiert, das magisch über das Stopp-Problem entscheidet, und geht dann zu dem Beweis über, dass die Existenz eines solchen Programms ein Widerspruch wäre und daher kein solches Programm existiert.
Ajedi32
1
@Fax Sie werfen jedoch einen guten Punkt darüber auf, ob ein Programm existieren könnte, das das Problem des Anhaltens entscheidet, außer wenn es selbst aufgerufen wird. Siehe Gibt es Beweise für die Unentscheidbarkeit des Halteproblems, die nicht von der Selbstreferenzierung oder Diagonalisierung abhängen? für eine interessante Frage dazu.
Ajedi32
9

Versuchen Sie einen schöneren Beweis mit Animationen. Und da ansewrs mehr als nur einen Link zu einer Site enthalten sollte, ist hier die Antwort auf Ihre Frage.

Erinnern wir uns zunächst daran, wie der Beweis der Nichtexistenz des Orakels Halting funktioniert. Wir beweisen, dass es bei jedem Kandidaten Hfür ein Halting-Orakel ein Programm Pund eine Eingabe gibt, afür die Hnicht richtig vorhergesagt werden kann, wasP(a) passiert.

Theorem: Sei Hjedes Programm, das zwei Eingaben annimmt und immer entweder haltoder zurückgibt loop. Dann gibt es ein Programm Qund eine Eingabe a, die Q(a)anhält, wenn und nur dann, wenn H(Q,a)zurückkehrt loop.

Beweis. Betrachten Sie das Programm

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

Lass Q = Pund a = P. Entweder H(Q,a) = haltoder H(Q,a) = loop:

  • wenn H(Q,a) = haltdann Q(a)(was gerade ist P(P)) läuft ewig nach der Definition vonP .
  • wenn H(Q,a) = loopdann Q(a)halt durch die definoin von P.

QED

Sie haben gefragt, warum wir uns überlegt haben, H(P,P)statt H(P,X)für andere X. Die offensichtliche Antwort lautet: "Weil H(P,P)der Beweis funktioniert"! Wenn Sie H(P,X)für eine beliebige verwendet X, dann würden Sie stecken bleiben. In der Tat würde der Beweis dann so aussehen:

Unterbrochener Beweis. Betrachten Sie das Programm

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

Lass Q = Pund a = Xfür einige willkürlich X. Entweder H(Q,X) = haltoder H(Q,X) = loop:

  • Nehmen H(Q,X) = haltwir an, wir können nicht sagen, was P(X)passiert, denn ob P(X)angehalten wird, hängt davon ab, was H(X,X)zurückkommt. Wir stecken fest. Wenn wir das jedoch wüssten P(X)und X(X)dasselbe sind, könnten wir Fortschritte erzielen. (Also sollten wir wirklich nehmen X = P).
  • wenn H(Q,a) = loopwir dann wieder stecken, und wir wären stecken geblieben, wenn X = P.

Keine QED.

Ich hoffe dies zeigt, dass wir überlegen H(P,P)müssen, um unsere Idee umzusetzen.

Andrej Bauer
quelle
Haha. Genial! :)
aelguindy
2

Das Ergebnis des Beweises ist diese Analogie:

Wenn eine Person behauptet, kann sie ( P ) das Gefühl jeder Person P 'erkennen, wenn sie / erP(P)P(P)P(P)(P)(P) . 🙂

(P)(P)

Ahmed Nassar
quelle