Gibt es einen intuitiveren Beweis für die Unentscheidbarkeit des Halteproblems als die Diagonalisierung?

30

Ich verstehe den Beweis für die Unentscheidbarkeit des Halteproblems (zum Beispiel in Papadimitrious Lehrbuch), basierend auf der Diagonalisierung.

Obwohl der Beweis überzeugt (ich verstehe jeden Schritt davon), ist er für mich nicht intuitiv in dem Sinne, dass ich nicht sehe, wie jemand ihn ableiten würde, ausgehend vom Problem alleine.

In dem Buch der Beweis wie : "Angenommen, löst das Halteproblem an einer Eingabe entscheidet, ob die Turing-Maschine für die Eingabe anhält . Konstruieren Sie eine Turing-Maschine , die eine Turing-Maschine als Eingabe verwendet , führt und kehrt die Ausgabe um. " Es wird dann gezeigt, dass keine zufriedenstellende Ausgabe erzeugen kann. M ; x M x D M M H ( M ; M ) D ( D )MHM;xMxDMMH(M;M)D(D)

Es ist die scheinbar willkürliche Konstruktion von , insbesondere die Idee, sich selbst und dann sich selbst zuzuführen, für die ich eine Intuition haben möchte. Was hat die Menschen dazu gebracht, diese Konstrukte und Schritte überhaupt zu definieren?M DDMD

Hat jemand eine Erklärung dafür, wie jemand seinen Weg in das Argument der Diagonalisierung (oder einen anderen Beweis) finden würde, wenn er diese Art von Argument nicht wüsste?

Nachtrag mit den ersten Antworten:

Die ersten Antworten weisen also darauf hin, dass der Nachweis der Unentscheidbarkeit des Halteproblems auf Cantors und Russells früherer Arbeit und der Entwicklung des Diagonalisierungsproblems beruhte und dass "von vorne" zu beginnen einfach bedeuten würde, dieses Argument neu zu entdecken.

Meinetwegen. Selbst wenn wir das Argument der Diagonalisierung als gut verstanden akzeptieren, stelle ich dennoch eine "Intuitionslücke" zum Stopp-Problem fest. Cantors Beweis für die Unzählbarkeit der reellen Zahlen finde ich eigentlich ziemlich intuitiv; Russells Paradoxon umso mehr.

Was ich immer noch nicht sehe, ist, was jemanden motivieren würde, basierend auf "Selbstanwendung" und dann auf sich selbst anzuwenden . Das scheint weniger mit der Diagonalisierung zu tun zu haben (in dem Sinne, dass Cantors Argument nichts Ähnliches besaß), obwohl es offensichtlich gut mit der Diagonalisierung zusammenarbeitet, sobald Sie sie definiert haben.M M ; M DD(M)MM;MD

PS

@babou fasste zusammen, was mich mehr beunruhigte als mich selbst: "Das Problem bei vielen Versionen des Beweises ist, dass die Konstruktionen anscheinend aus einem magischen Hut gezogen wurden."

user118967
quelle
3
Betrachten Sie die Möglichkeit, dass ein Beweis für die Existenz unzähliger Mengen nicht intuitiv sein muss, auch wenn wir uns daran gewöhnen, dass sie korrekt sind . Berücksichtigen Sie auch die Möglichkeit, dass diese Frage (falls richtig umformuliert) zu math.stackexchange.com gehört .
André Souza Lemos
4
Cantor hat das Diagonalisierungsargument gefunden, und jetzt können wir es nicht mehr vergessen: Aus dem Paradies, das Cantor uns erstellt, soll uns niemand vertreiben können .
Hendrik Jan
1
Nach weiteren Überlegungen muss ich fragen, warum Sie denken, dass dies so anders ist als Russells Paradoxon. Russells Paradoxon sieht sogar gleich aus, wenn wir die Notation für (dh Mengen als Funktionen betrachten, deren Werte oder sind ). Dann ist Russells Paradox zu definieren und dann zu überlegen . X SS(X)XStruefalseD(M) = not M(M)D(D)
1
Die Diagonalisierung ist eine Standardtechnik . Sicher, es gab eine Zeit, in der es nicht bekannt war, aber seit langem ist es Standard. Ihre Argumentation beruht also einfach auf Ihrer Unwissenheit (ich möchte nicht unhöflich sein, ist eine Tatsache: Sie wussten es nicht Alle anderen Beweise, die eine solche Technik verwenden und sie daher beim ersten Mal als seltsam empfinden. Wenn Sie sie 50 Mal gesehen haben, werden Sie wahrscheinlich verstehen, wie sie in einer neuen Situation angewendet werden kann.
Bakuriu
1
Vielleicht würden Sie meinen Kommentaraustausch mit Luke Mathieson lesen (im Anschluss an seine Antwort). Seine Antwort erklärt historisch, warum Turing Selbstanwendung verwendet hat (eine Frage, die Sie in Ihrer Frage stellen). Das scheint ziemlich genau zu sein, wie Mathematiker die Probleme zu dieser Zeit wahrgenommen haben. Meine eigene Antwort versucht, einen sehr einfachen Beweis zu liefern, der ihn nicht verwendet (oder zumindest zeigt, dass er nicht wesentlich ist). Möglicherweise könnte ich es noch einfacher machen als in meiner Antwort. Warum Lehrer immer noch Turings Beweise verwenden, ist ein soziologisches und pädagogisches (?!) Problem. cc @HendrikJan
babou

Antworten:

18

In Ihrer Bearbeitung schreiben Sie:

Was ich immer noch nicht sehe, ist, was jemanden motivieren würde, basierend auf "Selbstanwendung" und dann auf sich selbst anzuwenden . Das scheint weniger mit der Diagonalisierung zu tun zu haben (in dem Sinne, dass Cantors Argument nichts Ähnliches besaß), obwohl es offensichtlich gut mit der Diagonalisierung zusammenarbeitet, sobald Sie sie definiert haben.M M ; M DD(M)MM;MD

Eine verbreitete "populäre" Zusammenfassung von Turings Beweis lautet ungefähr so:

„Wenn wir eine Maschine hatte , ob eine andere Turing - Maschine stoppt entscheiden konnte oder nicht, wir diese andere Maschine zu konstruieren , verwenden könnte , dass eine Turing - Maschine gegeben wäre halt , wenn und nur wenn tat nicht halt. Aber dann konnten wir übergeben Sie als Eingabe an sich selbst und erhalten Sie so ein Paradoxon: Diese Maschine würde anhalten, wenn sie nicht anhalten würde! " D M M DMHDMMD

Nun ist leicht zu erkennen, dass die obige Zusammenfassung ein wichtiges Detail beschönigt - das Anhalten der Turing-Maschine hängt auch von ihrer Eingabe ab, die wir nicht spezifiziert haben! Aber dieses Problem kann leicht behoben werden: Wir müssen nur für jede Eingabemaschine eine geeignete Eingabe , bevor beide an .D x M M M HMDxMMMH

Was ist eine geeignete Wahl für , da wir letztendlich einen Widerspruch ableiten wollen? Nun, eine natürliche Wahl wird direkt durch den obigen "handwavy" Beweis nahegelegt, bei dem wir den Widerspruch letztendlich erhalten, indem wir die Maschine auf sich selbst laufen lassen . DxMD

Damit das Verhalten von in diesem Fall wirklich paradox ist, dh wenn es als aufgerufen wird, soll das Anhalten von vom Verhalten von abhängen, wenn es als aufgerufen wird. . Auf diese Weise werden wir den Widerspruch wollen wir erhalten , indem .D ( D ) , D ( M ) M M ( M ) M = DDD(D)D(M)M M(M)M=D

Wohlgemerkt, dies ist nicht die einzige Wahl. Den gleichen Widerspruch hätten wir auch herleiten können, indem wir beispielsweise eine Maschine so konstruierten dass genau dann anhält, wenn (anstelle von ) nicht anhält. es klar ist, dass die Maschine ihre Eingabe leicht duplizieren kann, bevor sie an , ist es nicht ganz so unmittelbar offensichtlich, wie eine Maschine konstruiert wird , die mit ihrem eigenen Code als Eingabe . Daher würde die Verwendung dieses anstelle von den Beweis unnötig komplizieren und ihn weniger intuitiv machen.D ' ( M ) M ( D ' ) , M ( M ) D M H D ' M H D ' DDD(M)M(D)M(M)DMHDMHDD

Ilmari Karonen
quelle
1
Wow, du hast meine Frage wirklich beantwortet! Das ist genau die Art von Geschichte, nach der ich gesucht habe! Ich lese immer noch alles, aber das scheint die akzeptierte Antwort zu sein. Vielen Dank!
user118967
18

Es kann einfach sein, dass es falsch ist zu glauben, dass jemand seinen Weg zu diesem Argument überlegt, ohne irgendwann zuvor ein ähnliches Argument in einem "einfacheren" Kontext zu machen.

Denken Sie daran, dass Turing Cantors Diagonalisierungsbeweis für die Unzählbarkeit der Reals kannte. Darüber hinaus ist seine Arbeit Teil einer Geschichte der Mathematik, die Russells Paradoxon (das ein Diagonalisierungsargument verwendet) und Gödels ersten Unvollständigkeitssatz (das ein Diagonalisierungsargument verwendet) umfasst. Tatsächlich hängt Gödels Ergebnis stark mit dem Beweis der Unentscheidbarkeit des Halteproblems (und damit der negativen Antwort auf Hilberts Entscheidungsproblem) zusammen.

Meine Behauptung ist also, dass Ihre Frage in gewisser Weise schlecht begründet ist und dass Sie das Halting-Problem nicht erreichen können, ohne den Rest (oder etwas bemerkenswert Ähnliches) zuerst zu überwinden. Während wir diese Dinge den Schülern zeigen, ohne die Geschichte durchzugehen, ist es unwahrscheinlich, dass Sie als arbeitender Mathematiker von nichts zu Turing Machines wechseln, ohne dass etwas dazwischen liegt. Der springende Punkt dabei war, die Berechnung zu formalisieren, ein Problem, das viele Menschen hatten seit Jahrzehnten an diesem Punkt gearbeitet.

Cantor benutzte die Diagonalisierung nicht einmal als ersten Beweis für die Unzählbarkeit der Reals. Wenn wir Veröffentlichungstermine als eine Annäherung an den Zeitpunkt betrachten, an dem er über die Idee nachdachte (nicht immer eine verlässliche Sache), dauerte es ungefähr 17 Jahre, bis er sie bereits kannte dass die Realzahlen unzählig waren, um das Argument der Diagonalisierung auszuarbeiten.

In Bezug auf die "Selbstanwendung" in dem Beweis, den Sie erwähnen, ist dies auch ein wesentlicher Bestandteil von Russells Paradoxon (das vollständig von der Selbstreferenz abhängt), und Gödels erster Unvollständigkeitssatz ist wie die leistungsstarke Version von Russells Paradoxon . Der Beweis für die Unentscheidbarkeit des Halteproblems wird von Gödels Arbeit so stark geprägt, dass es kaum vorstellbar ist, dorthin zu gelangen, weshalb die Idee der "Selbstanwendung" bereits Teil des Hintergrundwissens ist, das Sie benötigen, um das Halteproblem zu lösen . In ähnlicher Weise ist Gödels Arbeit eine Überarbeitung von Russells Paradoxon, so dass man nicht ohne das andere dorthin gelangt (man beachte, dass Russell nicht der erste war, der ein solches Paradoxon beobachtete, so dass Prototypen des Arguments der Diagonalisierung in der formalen Logik seit ungefähr existieren 600 v. Chr.). Sowohl Turing als auch Gödels Arbeit (die Stellen, über die wir hier sprechen) können als immer aussagekräftigere Demonstrationen der Probleme mit der Selbstreferenz und ihrer Einbettung in die Mathematik angesehen werden. Es ist also wieder sehr schwierig, darauf hinzuweisen, dass diese Ideen auf der Ebene, auf der sich Turing mit ihnen befasste, entstanden sinda priori waren sie der Höhepunkt der jahrtausendelangen Arbeit in Teilen der Philosophie, Mathematik und Logik.

Diese Selbstreferenz ist auch Teil von Cantors Argumentation, sie wird nur nicht in einer so unnatürlichen Sprache präsentiert wie Turings grundlegendere logische Arbeit. Cantors Diagonalisierung kann als eine Auswahl von Elementen aus der Potenzmenge einer Menge (im Wesentlichen Teil von Cantors Theorem) umformuliert werden. Wenn wir die Menge der (positiven) Reals als Teilmengen der Naturals betrachten (beachten Sie, dass wir nicht wirklich die zu ordnenden Ziffern benötigen, damit dies funktioniert, es ist nur eine einfachere Darstellung) und behaupten, dass es einen Widerspruch der Naturals zu gibt Wenn wir die Realitäten betrachten, können wir ein Element der Potenzmenge (dh ein Real) erzeugen, das nicht dem Bild der Surjektion entspricht (und daher einen Widerspruch herleitet), indem wir dieses Element als die Menge der Naturmenschen betrachten, die nicht in ihrer eigenen sind Bild unter dem Vorbehalt. Sobald wir es so formulieren,

Luke Mathieson
quelle
2
Ja, es scheint der Sinn von Turing zu sein, mit Hilfe von Maschinen Kreisförmigkeiten (aus denen die Diagonalisierung hervorgeht) wiederherzustellen, um eine abstrakte Vorstellung von Zeit einzuführen , mit der man auf neue Weise über Endlichkeit sprechen kann.
André Souza Lemos
Vielleicht können Sie mich aufklären, da ich mit einigen dieser Beweise nicht vertraut bin. Ich kann verstehen, dass diese Beweise mithilfe von Selbstreferenzierung gefälscht werden können. Ich kann sogar glauben (obwohl es vielleicht einen Beweis braucht), dass es in jeder Struktur, die für diesen Zweck konstruiert wurde, immer einen Selbstbezug gibt. Ich sehe jedoch nicht die Notwendigkeit, es explizit zu verwenden, um den Beweis zu seiner Schlussfolgerung zu führen. Sie können Cantors Argument auf diese Weise umformulieren, müssen es aber nicht. Und ich verstehe nicht, warum Sie es für das Halteproblem tun müssen. Ich habe vielleicht einen Schritt verpasst, aber welchen?
Babou
Um meine vorherige Bemerkung klarer zu machen, lautet die ursprüngliche Frage : " Gibt es einen intuitiveren Beweis für die Unentscheidbarkeit des Halteproblems ... ". Ich lasse das Ende aus, da ich das Gefühl habe, dass sich das OP hauptsächlich über den Mangel an Intuition beschwert. Ich glaube, dass es in der Tat einen intuitiveren Beweis gibt, der keine Selbstreferenz verwendet. Sie mögen denken, dass die Verwendung dieses Beweises pädagogisch unklug ist (da er nicht mit Russells und Gödels Arbeit zusammenhängt), aber wenn er die gestellte Frage beantwortet, warum sollte er abgelehnt werden? Sie scheinen die Frage eher zu leugnen als zu beantworten.
Babou
@babou Ich denke, das Problem hier ist, dass wir verschiedene Fragen beantworten. Das OP war in dieser Hinsicht wohl nicht gut formuliert. Die wiederholte Frage im OP-Korpus scheint mir zu lauten: "Wie hat jemand jemals an das Argument der Diagonalisierung gedacht, um zu beweisen ..." (natürlich umschrieben), und dass "die Konstruktionen einem magischen Hut zu entspringen scheinen". .
Luke Mathieson
@babou, auch um es ein wenig auszuarbeiten, mit einer richtigen Tastatur halte ich nicht die eine oder andere Weise für notwendigerweise pädagogisch nützlich (es würde stark vom Kontext abhängen). Tatsächlich ist es bei den meisten modernen CS-Kursen wahrscheinlich besser, auf das Argument der Diagonalisierung zu verzichten. Die meisten CS-Studenten sind einfach nicht mehr mathematisch geneigt, den Hintergrund zu kennen, der das Verständnis erleichtern würde, aber ich habe definitiv die Frage beantwortet Frage, die den ursprünglichen Textkörper beendete: ...
Luke Mathieson
9

Die Selbstanwendung ist kein notwendiger Bestandteil des Beweises

In einer Nussschale

Wenn es eine Turingmaschine , die das Halteproblem löst, können wir aus dieser Maschine eine andere Turingmaschine mit einem Halteverhalten (Haltecharakteristikfunktion) bauen, das nicht das Halteverhalten irgendeiner Turingmaschine sein kann.LHL

Das auf der selbst angewendeten Funktion aufbauende Paradoxon ( in dieser Antwort - Entschuldigung für Inkonsistenzen in der Notation) ist kein notwendiger Bestandteil des Beweises, sondern ein Gerät, das mit der Konstruktion eines spezifischen Widerspruchs verwendbar ist und das scheinbar "Wirkliche" verbirgt Zweck "der Konstruktion. Das ist wahrscheinlich der Grund, warum es nicht intuitiv ist.LDL

Es scheint direkter zu sein, zu zeigen, dass es nur eine unzählige Anzahl von Halteverhalten gibt (nicht mehr als Turing-Maschinen), die als charakteristische Haltefunktionen definiert werden können, die jeder Turing-Maschine zugeordnet sind. Man kann konstruktiv eine charakteristische Haltefunktion definieren, die nicht in der Liste enthalten ist, und daraus und aus einer Maschine , die das Halteproblem löst, eine Maschine , die diese neue charakteristische Haltefunktion aufweist. Aber da es konstruktionsbedingt nicht die charakteristische Haltefunktion einer Turingmaschine ist, kann keine sein. Da mit Turing-Maschinenbautechniken aus gebaut wird, kann keine Turing-Maschine sein.L L L H HHLLLHH

Die in vielen Beweisen verwendete Selbstanwendung von auf sich selbst ist ein Weg, den Widerspruch aufzuzeigen. Dies funktioniert jedoch nur, wenn die unmögliche Funktion zum Anhalten von Merkmalen aus der Diagonale der Liste der zulässigen Funktionen zum Anhalten von Merkmalen durch Umdrehen dieser Diagonale (Vertauschen von und ) erstellt wird. Es gibt aber unendlich viele andere Möglichkeiten, eine neue charakteristische Haltefunktion aufzubauen. Dann kann Nicht-Turing-Ness nicht mehr mit einem Lügner-Paradoxon belegt werden (zumindest nicht einfach). Die Selbstanwendungskonstruktion ist nicht intuitiv, da sie nicht wesentlich ist, aber sie sieht glatt aus, wenn sie aus dem Zauberhut gezogen wird.0 1L01

Grundsätzlich ist keine Turingmaschine, da es von Anfang an so ausgelegt ist, dass es ein Stoppverhalten aufweist, das nicht dem einer Turingmaschine entspricht und das direkter und damit intuitiver dargestellt werden kann.L

Anmerkung : Es kann sein, dass für jede konstruktive Wahl der Funktion für das unmögliche Anhalten der Charakteristik eine berechenbare Neuordnung der Aufzählung der Turingmaschine vorliegt, so dass sie zur Diagonale wird (ich weiß nicht). Dies ändert jedoch nichts an der Tatsache, dass die Selbstanwendung eine indirekte Beweismethode ist, die eine intuitivere und interessantere Tatsache verbirgt.

Detaillierte Analyse der Beweise

Ich werde nicht historisch sein (aber dank denen, die es sind, genieße ich es), aber ich versuche nur, die intuitive Seite zu bearbeiten.

Ich denke, dass die Präsentation von @vzn , der ich vor langer Zeit begegnet bin (ich hatte sie vergessen), eigentlich ziemlich intuitiv ist und sogar die Namensdiagonalisierung erklärt. Ich wiederhole es nur im Detail, weil ich der Meinung bin, dass @vzn seine Einfachheit nicht genug betont hat.

Mein Ziel ist es, einen intuitiven Weg zu finden, um den Beweis von Cantor zu erhalten. Das Problem bei vielen Versionen des Beweises ist, dass die Konstruktionen anscheinend aus einem magischen Hut gezogen wurden.

Der Beweis, den ich gebe, ist nicht genau der gleiche wie in der Frage, aber er ist korrekt, soweit ich sehen kann. Wenn ich keinen Fehler gemacht habe, ist es intuitiv genug, da ich es nach mehr Jahren abrufen konnte, als ich zählen möchte, und an sehr unterschiedlichen Themen arbeitete.

Der Fall der Teilmengen von (Cantor)N

Der Beweis von Cantor setzt voraus (es ist nur eine Hypothese), dass es eine Aufzählung der Teilmengen der ganzen Zahlen gibt, so dass alle diese Teilmengen durch ihre charakteristische Funktion die wenn und ist sonst .C j ( i ) 1 i S j 0SjCj(i)1iSj0

Dies kann als eine Tabelle , so dassT [ i , j ] = C j ( i )TT[i,j]=Cj(i)

Dann bauen wir unter Berücksichtigung der Diagonale eine charakteristische Funktion so dass , dh sie ist identisch mit der Diagonale der Tabelle, wobei jedes Bit auf den anderen Wert gekippt wird.D ( i ) = ¯ T [ i , i ]DD(i)=T[i,i]¯

Die Diagonale hat nichts Besonderes, außer dass es ein einfacher Weg ist, eine charakteristische Funktion , die sich von allen anderen unterscheidet, und das ist alles, was wir brauchen.D

Daher kann die durch gekennzeichnete Teilmenge nicht in der Aufzählung enthalten sein. Da dies für jede Aufzählung zutrifft, kann es keine Aufzählung geben, die alle Teilmengen von .NDN

Dies ist freilich nach der Ausgangsfrage ziemlich intuitiv. Können wir den Beweis des Halteproblems als intuitiv bezeichnen?

Der Fall des Halteproblems (Turing)

Wir gehen davon aus, dass wir eine Aufzählung von Turing-Maschinen haben (von denen wir wissen, dass sie möglich sind). Das einer Turingmaschine kann durch ihre charakteristische die wenn am Eingang anhält und ansonsten .H j ( i ) 1 M j i 0MjHj(i)1Mji0

Dies kann als eine Tabelle , so dassTT[i,j]=Hj(i)

Dann bauen wir unter Berücksichtigung der Diagonale eine charakteristische Haltefunktion so dass , dh sie ist identisch mit der Diagonale der Tabelle, wobei jedes Bit auf den anderen Wert gekippt wird.DD(i)=T[i,i]¯

Die Diagonale hat nichts Besonderes, außer dass es ein einfacher Weg ist, eine charakteristische Haltefunktion , die sich von allen anderen unterscheidet, und das ist alles, was wir brauchen (siehe Anmerkung unten).D

Daher kann das durch charakterisierte nicht das einer Turingmaschine in der Aufzählung sein. Da wir alle aufgezählt haben, schließen wir, dass es keine Turing-Maschine mit diesem Verhalten gibt.D

Bisher kein stoppendes Orakel und keine Berechenbarkeitshypothese : Wir wissen nichts über die Berechenbarkeit von und der Funktionen .THj

Nehmen wir nun an, wir haben eine Turingmaschine , die das Halteproblem lösen kann, so dass immer mit als Ergebnis .HH(i,j)Hj(i)

Wir wollen beweisen, dass wir mit eine Maschine bauen können , die die charakteristische Haltefunktion . Die Maschine nahezu identisch ist , so dass nachahmt , mit der Ausnahme , dass , wenn ist etwa mit dem Wert zu beenden , geht in eine Endlosschleife und endet nicht.HLDLHL(i)H(i,i)H(i,i)1L(i)

Es ist ziemlich klar, dass wir eine solche Maschine bauen können, wenn existiert. Daher sollte diese Maschine in unserer anfänglichen Aufzählung aller Maschinen sein (von denen wir wissen, dass sie möglich sind). Es kann aber nicht sein, da sein Stoppverhalten keiner der aufgezählten Maschinen entspricht. Maschine kann nicht existieren, was bedeutet, dass nicht existieren kann.LHDLH

Ich ahmte den ersten Beweis absichtlich nach und ging auf winzige Details ein

Ich habe das Gefühl, dass die Schritte auf natürliche Weise ablaufen, besonders wenn man Cantors Beweis als ziemlich intuitiv ansieht.

Man zählt zuerst die prozessualen Konstrukte auf. Dann nimmt und modifiziert man die Diagonale als eine bequeme Art, sie alle zu berühren, um ein unberücksichtigtes Verhalten zu erhalten, und erhält dann einen Widerspruch, indem man ein Objekt ausstellt, das das unberücksichtigte Verhalten hat ... wenn irgendeine Hypothese wahr wäre: Existenz von die Aufzählung für Cantor und die Existenz eines berechenbaren Stopporakels für Turing.

Hinweis: Um die Funktion zu definieren , können wir die umgedrehte Diagonale durch jede andere charakteristische Haltefunktion ersetzen, die sich von den in aufgelisteten unterscheidet und berechenbar ist ( z. B. von den in aufgelisteten ), sofern ein Halteorakel verfügbar ist . Dann müsste die Maschine entsprechend konstruiert werden, um als charakteristische Haltefunktion zu haben , und würde die Maschine , aber nicht so direkt nachahmen . Die Wahl der Diagonale macht es viel einfacher.DTTLDL(i)HH(i,i)

Vergleich mit dem "anderen" Beweis

Die hier definierte Funktion ist offenbar das Analogon der Funktion im in der Frage beschriebenen Beweis.LD

Wir bauen es nur so, dass es eine charakteristische Haltefunktion hat, die keiner Turing-Maschine entspricht, und bekommen daraus direkt einen Widerspruch. Dies gibt uns die Freiheit, die Diagonale nicht zu verwenden (für das, was es wert ist).

Die Idee des "üblichen" Beweises scheint zu versuchen, das zu töten, was ich als toten Fisch betrachte. Es heißt: Nehmen wir an, ist eine der aufgelisteten Maschinen (dh alle von ihnen). Dann hat es einen Index in dieser Aufzählung: . Wenn dann anhält, haben wir , so dass konstruktionsbedingt eine Schleife . Wenn umgekehrt nicht , dann ist so dass konstruktionsbedingt . Damit haben wir einen Widerspruch. Der Widerspruch ergibt sich aber aus der Art und Weise der charakteristischen Haltefunktion vonLjLL=MjLL(jL)T[jL,jL]=H(jL,jL)=1L(jL)L(jL)T[jL,jL]=H(jL,jL)=0L LL(jL)Lwurde konstruiert und es scheint viel einfacher zu sagen, dass keine Turing-Maschine sein kann, da es eine charakteristische Stoppfunktion aufweist, die nicht die einer Turing-Maschine ist.L

Ein Nebeneffekt ist, dass dieser übliche Beweis viel schmerzhafter wäre, wenn wir nicht die Diagonale gewählt hätten, während der oben verwendete direkte Ansatz kein Problem damit hat. Ob das sinnvoll sein kann, weiß ich nicht.

babou
quelle
Sehr Schön. Danke! Es scheint, dass Sie es irgendwie geschafft haben, die selbstklebenden Konstruktionen zu umgehen, die ich als mühsam empfand. Jetzt frage ich mich, warum die Leute sie überhaupt für notwendig hielten.
user118967
@ user118967 Ich habe versucht zu unterstreichen, dass die Verwendung der Diagonale nicht wirklich wichtig ist. Sie möchten lediglich eine charakteristische Anhaltefunktion definieren, die sich von den in der Tabelle aufgelisteten unterscheidet und die von den aufgelisteten berechnet werden kann, vorausgesetzt, wir haben ein Anhalteorakel. Es gibt unendlich viele solcher charakteristischen Haltefunktionen. Nun, das scheint im üblichen Beweis nicht so sichtbar zu sein, und es kann sein, dass einige Konstrukte dieses Beweises willkürlich erscheinen, einfach weil sie so sind, als ob man die Diagonale im obigen Beweis wählt. Es ist nur einfach, nicht wesentlich.
Babou
@ user118967 Ich habe eine Einführung hinzugefügt, die die Analyse der verschiedenen Beweise zusammenfasst. Es ergänzt den Vergleich zwischen Proofs (mit und ohne Selbstanwendung), der am Ende gegeben wird. Ich weiß nicht, ob ich die Diagonale wie gewünscht beseitigt habe :) (ich denke, es wäre unfair, das zu sagen), aber ich gebe Hinweise, wie man die offensichtliche Diagonale beseitigt. Und der Beweis verwendet keine Selbstanwendung, was als unnötiger, aber geschickter Trick erscheint, der das möglicherweise wichtigere Problem, das Stoppverhalten, verbirgt.
Babou
@ user118967 Um Ihren ersten Kommentar zu beantworten und nachdem Sie die am meisten aufgerufene Antwort gelesen haben, scheint es, dass die Hauptmotivation die Verbindung mit der Arbeit von Russell und Gödel ist. Jetzt habe ich keine Ahnung, ob es für diesen Zweck wirklich notwendig ist, und die Variante der selbstanwendenden Konstruktionen kann für diesen Zweck bestimmt studiert werden, aber ich sehe keinen Sinn darin, sie jedem aufzuzwingen. Darüber hinaus erscheint der direktere Beweis intuitiver und gibt dem Tool die Möglichkeit, die selbstanwendende Version weiter zu analysieren. Warum dann?
Babou
Ja, da stimme ich Ihnen eher zu.
user118967
8

Es gibt auch einen Beweis für diese Tatsache, der ein anderes Paradoxon verwendet, Berrys Paradoxon, das ich von Ran Raz gehört habe.

Angenommen, das Halteproblem wäre berechenbar. Sei die kleinste natürliche Zahl, die mit einem C-Programm der Länge nicht berechnet werden kann . Das heißt, wenn die Menge natürlicher Zahlen ist, die von C Programmen der Länge berechnet wurden , dann ist die kleinste natürliche Zahl, die nicht in .n S ( n ) n B ( n ) S ( n )B(n)nS(n)nB(n)S(n)

Betrachten Sie das folgende Programm:

  1. Gehen Sie alle C-Programme mit einer Länge von höchstens .n

  2. Überprüfen Sie für jedes dieser Programme, ob es anhält. wenn es der Fall ist, fügen Sie ihn in einer Liste .L

  3. Geben Sie die erste natürliche Zahl nicht in .L

Dies ist ein Programm zur Berechnung von . Wie groß ist dieses Programm? Die Kodierung von benötigt Zeichen, und der Rest des Programms hängt nicht von ab. Insgesamt beträgt die Länge also , beispielsweise höchstens . Wählen Sie , so dass . Dann berechnet unser Programm, dessen Länge höchstens beträgt , , was der Definition von widerspricht .n O ( log n ) n O ( log n ) C log n N C log N N N B ( N ) B ( N )B(n)nO(logn)nO(logn)ClognNClogNNNB(N)B(N)

Dieselbe Idee kann verwendet werden, um Gödels Unvollständigkeitssätze zu beweisen, wie Kritchman und Raz gezeigt haben .

Yuval Filmus
quelle
Vielleicht ist es in der Zeitung, die ich zitiere, oder in der klassischen Monographie Kolmogorov Complexity von Li und Vitányi.
Yuval Filmus
Glauben Sie übrigens, dass diese Methode einen Angriff auf das NP-gegen-CoNP-Problem darstellt?
Mohammad Al-Turkistany
Nein, solche Probleme sind im Moment für uns unbegründet.
Yuval Filmus
n
nnn
6

Es handelt sich um eine allgemeinere Idee, die als "Rekursionssatz" bezeichnet wird und möglicherweise intuitiver ist: Turing-Maschinen können ihre eigene Beschreibung verwenden (und sich selbst ausführen). Genauer gesagt gibt es einen Satz:

Für jede Turingmaschine Tgibt es eine Turingmaschine R, die rechnet R(x) = T(R;x).

Wenn wir eine Turingmaschine hätten, die das Halteproblem lösen könnte, dann könnten wir mit der oben beschriebenen Idee leicht eine Vielzahl von "Lügner" -Turingmaschinen konstruieren: zB in pythonartiger Notation,

def liar():
    if halts(liar):
        return not liar()
        # or we could do an infinite loop
    else:
        return True

Das kompliziertere Argument versucht im Wesentlichen nur, dies direkt zu tun, ohne den Rekursionssatz anzugreifen. Das heißt, es wird ein Rezept für die Erstellung von "selbstreferenziellen" Funktionen wiederholt. zB bei einer Turingmaschine Tist hier ein solches Rezept zur Konstruktion einer Rbefriedigenden

R(x) = T(R; x)

Definieren Sie zuerst

S(M; x) = T(M(M; -); x)

womit M(M; -)meine ich eigentlich, dass wir Meine Beschreibung einer Turing-Maschine berechnen (unter Verwendung der Beschreibung von ) und einfügen, die bei der Eingabe yausgewertet wird M(M; y).

Nun beobachten wir das, wenn wir uns Sselbst anschließen

S(S; x) = T(S(S; -); x)

Wir bekommen die Vervielfältigung, die wir wollen. Also, wenn wir uns setzen

R = S(S; -)

dann haben wir

R(x) = T(R; x)

wie gewünscht.


quelle
Der erste Absatz stimmt nicht mit dem Satz überein, den Sie zitieren, den ich unter dem Namen smn-Satz kenne.
Raphael
@ Raphael: In meinem Lehrbuch heißt es Rekursionssatz. :( Mein kurzer Versuch bei Google schlug fehl, alternative Namen zu finden.
Keine Bange; Vielleicht verstehe ich dich falsch, oder es gibt verschiedene Namen für das gleiche Ding. Ihr Satz "Turingmaschinen können ihre eigene Beschreibung verwenden" wird jedoch von dem Satz, den Sie zitieren, nicht unterstützt. Tatsächlich denke ich, dass es falsch ist: Wenn die Funktion, die ein TM berechnet, von seinem Index abhängt, wie würden dann all die unendlich vielen TMs aussehen, die dieselbe Funktion berechnen?
Raphael
TliarTruenot liar()False
TRR(x)=T(R;x)TRR(x)=T(R;x)
5

Der Turing-Beweis ist dem Cantors-Beweis ziemlich ähnlich, dass die Kardinalität der Realzahlen ("unzählbar") größer ist als die Kardinalität der Rationalzahlen ("abzählbar"), da sie nicht in eine 1: 1-Entsprechung gebracht werden können, dies jedoch nicht vermerkt / hervorgehoben wird Sehr viele Referenzen (kennt jemand welche?). (iirc) ein CS-Profi hat diesmal vor Jahren in der Klasse gezeigt (nicht sicher, wo er es selbst bekommen hat). In Cantors Proof kann man sich ein Raster mit horizontaler Dimension vorstellen, wobei die n- te Ziffer der Zahl und die vertikale Dimension die n- te Ziffer der Menge ist.

Die Turing-halting-Proof-Konstruktion ist ziemlich ähnlich, außer dass der Inhalt der Tabelle stattdessen Halt / Nonhalt für 1/0 ist und die horizontale Achse die n- te Eingabe und die vertikale Achse das n- te Computerprogramm ist. mit anderen Worten, die Kombination von Computerprogrammen und Eingaben ist zählbar, aber die unendliche Anzahl von Tabellen / Arrays ist unzählbar, basierend auf einer universellen Maschinensimulatorkonstruktion, die ein Anhalten in einen nicht anhaltenen Fall "umkehren" kann, vorausgesetzt, eine anhaltene Detektormaschine existiert (daher reductio ad absurdam ). .

Einige Beweise dafür, dass Turing Cantors Konstruktion zum Teil im Sinn hatte, sind, dass sein Papier mit dem Stoppbeweis von berechenbaren Zahlen als (nach dem Vorbild von) reellen Zahlen mit berechenbaren Ziffern spricht.

vzn
quelle
Nachtrag, es gibt in der Tat eine sehr "intuitive" Möglichkeit, Unentscheidbarkeit zu betrachten, aber es erfordert viel höhere Mathematik, um es zu begreifen (dh die Intuition eines Neophyten ist viel anders als die Intuition eines Experten). Mathematiker betrachten das Stopp-Problem als identische Beweise über ein Lawvere-Fixpunkt-Theorem, aber dies ist eine fortgeschrittene Tatsache, die für Studenten "noch" nicht sehr zugänglich ist. siehe Halteproblem, nicht berechenbare Mengen, häufiges mathematisches Problem? Theoretische Informatik & auch verlinkter Beitrag für refs
vzn
3

An dieser Stelle sei auf die Arbeit von Emil Post hingewiesen, der (zu Recht) als Mitentdecker der grundlegenden Ergebnisse der Berechenbarkeit gilt, die jedoch leider zu spät veröffentlicht wurde, um als Mitentdecker der Lösung des Entscheidungsproblems zu gelten . Er war sicherlich an der Ausarbeitung der sogenannten Church-Turing-These beteiligt .

Post wurde durch sehr philosophische Überlegungen motiviert, nämlich die theoretischen Einschränkungen der menschlichen Rechenfähigkeit, oder sogar präzise Antworten auf konsequente Weise zu erhalten. Er entwickelte ein System, das jetzt als postkanonische Systeme bezeichnet wird und dessen Details unwichtig sind. Er behauptete, es könne zur Lösung aller Probleme verwendet werden, die durch Manipulation von Symbolen gelöst werden könnten . Interessanterweise betrachtete er Geisteszustände explizit als Teil des "Gedächtnisses", so dass es wahrscheinlich ist, dass er sein Rechenmodell zumindest als ein Modell des menschlichen Denkens in seiner Gesamtheit ansah.

Das Entscheidungsproblem betrachtet die Möglichkeit, mit einem solchen Berechnungsmittel den Theorem eines im System der Principia Mathematica ausdrückbaren Satzes zu bestimmen . Aber das PM war ein System, das explizit entworfen wurde, um alle mathematischen Überlegungen und, zumindest zu der Zeit, als die Logik noch in Mode war, alle menschlichen Überlegungen darstellen zu können!

Es ist daher nicht verwunderlich, die Aufmerksamkeit eines solchen Systems auf die postkanonischen Systeme selbst zu lenken, so wie der menschliche Verstand über die Werke von Frege, Russel und den Logikern der Jahrhundertwende ihre Aufmerksamkeit auf das Denkvermögen gelenkt hatte des menschlichen Geistes selbst.

Es ist an dieser Stelle klar, dass die Selbstreferenz oder die Fähigkeit von Systemen, sich selbst zu beschreiben, in den frühen 1930er Jahren ein eher natürliches Thema war. Tatsächlich hoffte David Hilbert, die mathematischen Überlegungen selbst auf den Prüfstand zu stellen, indem er eine formale Beschreibung der gesamten menschlichen Mathematik lieferte, die sich dann mathematisch als konsequent herausstellen ließ!

Sobald der Schritt erreicht ist, ein formales System zu verwenden, um über sich selbst zu urteilen, ist es ein Sprung und ein Sprung weg von den üblichen selbstreferenziellen Paradoxien (die eine ziemlich alte Geschichte haben ).

Da alle Aussagen in Principia in gewissem metaphysischen Sinne als "wahr" angenommen werden und die Principia ausdrücken kann

Programm pgibt Ergebnis truebei Eingabe zurückn

Wenn ein Programm existiert, um alle Sätze in diesem System zu bestimmen, ist es ganz einfach, das Paradox des Lügners direkt auszudrücken:

Dieses Programm lügt immer.

kann ausgedrückt werden durch

Das Programm gibt pimmer das Gegenteil von dem zurück, was die Principia Mathematica sagt p.

Die Schwierigkeit besteht darin, das Programm zu erstellen p. Aber an diesem Punkt ist es ziemlich natürlich, den allgemeineren Satz zu betrachten

Das Programm gibt pimmer das Gegenteil von dem zurück, was der PM sagt q.

für einige willkürlich q. Aber es ist einfach p(q)für jeden zu bauen q! Berechnen Sie einfach, welche PM die Ausgabe vorhersagt, und geben Sie die gegenteilige Antwort zurück. Wir können nicht einfach ersetzen qdurch , pobwohl zu diesem Zeitpunkt, da pnimmt qals Eingabe und qnicht (es braucht keine Eingabe). Lassen Sie uns unser Satz ändern , damit p tut take - Eingang:

Das Programm pgibt das Gegenteil von dem zurück, was PM sagt q(r).

Arg! Aber jetzt pbraucht man 2 Eingaben: qund r, während es qnur 1 nimmt. Aber warte: Wir wollen pan beiden Stellen sowieso rkeine neue Information, sondern eben wieder die gleiche Information, nämlich q! Dies ist die kritische Beobachtung.

So bekommen wir endlich

Das Programm pgibt das Gegenteil von dem zurück, was PM sagt q(q).

Vergessen wir dieses dumme "PM sagt" Geschäft und wir bekommen

Das Programm p(q)gibt das Gegenteil von dem zurück, was zurückgegeben q(q)wird.

Dies ist ein legitimes Programm, vorausgesetzt, wir haben ein Programm, das uns immer mitteilt, was q(q)zurückkehrt . Aber jetzt , da wir unser Programm haben p(q), können wir ersetzen qdurch pund unseren Lügner Paradox bekommen.

Cody
quelle