Ich habe Probleme, den Beweis für die Unentscheidbarkeit des Halteproblems zu verstehen.
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 ?
Warum können wir mit P und einer beliebigen Eingabe, z. B. x , versorgen ?
Antworten:
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 PP M M( S.) = P nicht akzeptieren ?⟨ P⟩
Der Widerspruch entsteht, wenn Sie fragen: HatM akzeptieren ? Versuchen Sie, die beiden Optionen herauszufinden, um festzustellen, wo ein Widerspruch besteht.⟨ M⟩
akzeptiert ⟨ M ⟩ , wenn und nur wenn MM ⟨ M⟩ M 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
quelle
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 ) H ein ein b H( a , b ) wirkt wie folgt
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:H P H P x
Das ist nicht schwer zu sehen
So weit so gut: wird sicherlich ein Programm sein , solange sein Unterprogramm HP H 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 durchP 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 ) H H
quelle
H
wird nicht mehr als einmal aufgerufen, es gibt überhaupt keine RekursionP
.H(P, P)
wird nicht ausgeführtP
, es wird nur "magisch" bestimmt, obP
angehalten wird oder nicht, wenn es selbst übergeben wird.H(P,P)
muss nicht ausgeführt werdenP
, aber es muss ausgeführt werden, umH(x ↦ H(x,x), P)
zu bestimmen, obP
angehalten wird. Welches erweitert sichH(x ↦ H(y ↦ H(y,y), x), P)
und so weiter.H
ist in diesem Proof nicht angegeben. Also nein, es nicht haben nichts ausführen , um, ob das seinP
oder sich. Der Beweis beginnt mit der Annahme, dass irgendeine Art von ProgrammH
existiert, 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.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
H
für ein Halting-Orakel ein ProgrammP
und eine Eingabe gibt,a
für dieH
nicht richtig vorhergesagt werden kann, wasP(a)
passiert.Theorem: Sei
H
jedes Programm, das zwei Eingaben annimmt und immer entwederhalt
oder zurückgibtloop
. Dann gibt es ein ProgrammQ
und eine Eingabea
, dieQ(a)
anhält, wenn und nur dann, wennH(Q,a)
zurückkehrtloop
.Beweis. Betrachten Sie das Programm
Lass
Q = P
unda = P
. EntwederH(Q,a) = halt
oderH(Q,a) = loop
:H(Q,a) = halt
dannQ(a)
(was gerade istP(P)
) läuft ewig nach der Definition vonP
.H(Q,a) = loop
dannQ(a)
halt durch die definoin vonP
.QED
Sie haben gefragt, warum wir uns überlegt haben,
H(P,P)
stattH(P,X)
für andereX
. Die offensichtliche Antwort lautet: "WeilH(P,P)
der Beweis funktioniert"! Wenn SieH(P,X)
für eine beliebige verwendetX
, dann würden Sie stecken bleiben. In der Tat würde der Beweis dann so aussehen:Unterbrochener Beweis. Betrachten Sie das Programm
Lass
Q = P
unda = X
für einige willkürlichX
. EntwederH(Q,X) = halt
oderH(Q,X) = loop
:H(Q,X) = halt
wir an, wir können nicht sagen, wasP(X)
passiert, denn obP(X)
angehalten wird, hängt davon ab, wasH(X,X)
zurückkommt. Wir stecken fest. Wenn wir das jedoch wüsstenP(X)
undX(X)
dasselbe sind, könnten wir Fortschritte erzielen. (Also sollten wir wirklich nehmenX = P
).H(Q,a) = loop
wir dann wieder stecken, und wir wären stecken geblieben, wennX = P
.Keine QED.
Ich hoffe dies zeigt, dass wir überlegen
H(P,P)
müssen, um unsere Idee umzusetzen.quelle
Das Ergebnis des Beweises ist diese Analogie:
Wenn eine Person behauptet, kann sie ( P ) das Gefühl jeder Person P 'erkennen, wenn sie / erP ( S.) P′ ( S.′) P ( S.) ( S.) ( S.) . 🙂
quelle