Könnte das Problem des Anhaltens „gelöst“ werden, indem zu einer Beschreibung der Berechnung auf höherer Ebene übergegangen wird?

21

Ich habe kürzlich eine interessante Analogie gehört, die besagt, dass Turings Beweis für die Unentscheidbarkeit des Stopp-Problems Russells Barbier-Paradoxon sehr ähnlich ist.

Also wunderte ich mich: Mathematiker schafften es schließlich, die Mengenlehre konsistent zu machen, indem sie von Cantors naiver Feldformulierung zu einem komplexeren Axiomensystem übergingen (ZFC-Mengenlehre) und dabei wichtige Ausschlüsse (Restriktionen) und Ergänzungen machten.

Wäre es vielleicht möglich, eine abstrakte Beschreibung der allgemeinen Berechnung zu finden, die leistungsfähiger und aussagekräftiger als Turing-Maschinen ist und mit der man entweder einen existenziellen Beweis oder sogar einen Algorithmus zur Lösung des Halteproblems erhalten könnte eine beliebige Turingmaschine?

H2CO3
quelle
1
Willkommen bei Computer Science Stack Exchange. Bitte lesen Sie cs.stackexchange.com/tour.if , falls Sie dies noch nicht getan haben. --- Was haben Sie für ein leistungsfähigeres Modell als TM versucht? Was blockiert dich?
Babou
2
@babou Im Gegenteil, du brauchst ein weniger leistungsfähiges Modell.
Yuval Filmus
2
@YuvalFilmus Nun, das OP fragt nach einem stärkeren Modell, nicht nach einem schwächeren. --- Mit Entschuldigung an H2CO3 ... Meine Frage war eigentlich ein Scherz, da es eine Standardfrage ist, wenn Leute ihre Hausaufgaben als Frage einreichen. Das war hier natürlich nicht angebracht, da niemand erwartet, dass Sie ein solches Modell finden würden. Ich hoffe du nimmst es nicht zu sauer.
Babou
1
Vielleicht möchten Sie etwas über Hypercomputation lesen. De.wikipedia.org/wiki/Hypercomputation .
Eric Towers

Antworten:

15

Sie können nicht wirklich vergleichen. Die naive Mengenlehre hatte Paradoxe, die durch die ZFC-Mengenlehre beseitigt wurden. Die Theorie muss auf Konsistenz hin verbessert werden, da eine Grundannahme der wissenschaftlichen Arbeit darin besteht, dass Konsistenz erreichbar ist (andernfalls wird die Umgestaltung zu einem Zufallsgeschäft). Ich nehme an, Mathematiker haben damit gerechnet, dass es möglich sein muss, und haben daran gearbeitet, das Problem zu lösen.

Bei der Berechnungstheorie und dem Halteproblem gibt es eine solche Situation nicht. Es gibt kein Paradoxon, keine Inkonsistenz. Es ist einfach so, dass es keine Turing-Maschine gibt, die das TM-Stopp-Problem lösen kann. Es ist einfach ein Satz, kein Paradoxon.

So kann es sein, dass ein Durchbruch in unserem Verständnis des Universums zu Rechenmodellen führt, die über das hinausgehen, was wir uns jetzt vorstellen können. Das einzige derartige Ereignis in einer sehr schwachen Form, das im TM-Bereich verbleibt, war möglicherweise das Quantencomputing. Abgesehen von diesem sehr schwachen Beispiel, das eher die Komplexität betrifft (wie lange dauert es?) Als die Berechenbarkeit (ist es machbar?), Bezweifle ich, dass irgendjemand auf diesem Planeten eine Ahnung hat, dass eine Berechenbarkeit über TM hinaus zu erwarten ist.

Darüber hinaus ist das Stopp-Problem eine direkte Folge der Tatsache, dass Turing-Maschinen durch einen endlichen Text, eine Folge von Symbolen, beschreibbar sind. Dies gilt tatsächlich für unser gesamtes Wissen (soweit wir wissen), und deshalb sind Sprache und Bücher so wichtig. Dies gilt für alle unsere Techniken zur Beschreibung von Beweisen und Berechnungen.

Selbst wenn wir einen Weg finden würden, die Art und Weise zu erweitern, wie wir rechnen, sagen wir mit den T + -Maschinen. Entweder würde es bedeuten, dass wir einen Weg gefunden haben, Wissen auszudrücken, das über das Schreiben eines endlichen Dokuments hinausgeht. In diesem Fall fällt das Ganze aus meiner Zuständigkeit (ich behaupte, absolute Inkompetenz) und wahrscheinlich aus der eines anderen. Oder es wäre immer noch in endlichen Dokumenten ausdrückbar. In diesem Fall hätte es ein eigenes Problem mit dem Anhalten von T + -Maschinen. Und Sie würden die Frage erneut stellen.

Tatsächlich existiert diese Situation umgekehrt. Einige Maschinentypen sind schwächer als Turing-Maschinen, z. B. Linear Bounded Automata (LBA). Sie sind zwar ziemlich leistungsfähig, aber es kann genau wie bei TM gezeigt werden, dass LBA das Halteproblem für LBA nicht lösen kann. Aber TM kann es für LBA lösen.

Schließlich können Sie sich leistungsfähigere Rechenmodelle vorstellen, indem Sie Orakel einführen. Dies sind Geräte, die Antworten auf bestimmte Probleme geben können und von einem TM für Antworten aufgerufen werden können, die jedoch physisch leider nicht existieren. Ein solches Orakel-erweitertes TM ist ein Beispiel für die T + -Maschine, die ich oben betrachtet habe. Einige von ihnen können das TM-Halteproblem lösen (abstrahiert, nicht wirklich), aber sie können ihr eigenes Halteproblem nicht lösen, auch nicht abstrahiert.

babou
quelle
Unter der Annahme, dass ZFC konsistent ist, ist es immer noch unvollständig, dh es gibt Sätze, die wir weder beweisen noch widerlegen können, und dies hängt eng mit der Unlösbarkeit des Halteproblems zusammen. Wenn das Halten lösbar wäre, könnten wir alle Sätze beweisen oder widerlegen. Dies ist Mathematik, und dies ist keine zu lösende Inkonsistenz, sondern auch ein Theorem (Gödel)
Hernan_eche
@ Hernan_eche Nun ... ja und ... was ...? Wenn Sie der Meinung sind, dass Inkonsistenz nicht schlimmer als Unvollständigkeit ist, ist dies Ihr persönliches Urteil. Ich bezweifle, dass die meisten Mathematiker zustimmen würden. Sie mögen vielleicht kein TM, das nicht terminiert. Aber möchten Sie, dass sie immer mit Ja oder Nein bei derselben Eingabe beendet werden? Was würdest du von der Antwort halten? Und wenn Sie Nichtdeterminismus denken ... überlegen Sie es sich zweimal.
Babou
Ich möchte nur klarstellen, dass Informatik und Mathematik dieselben Probleme haben, um zu vermeiden, dass die Leser die Antwort falsch interpretieren, als ob die Grundprobleme der Mathematik mit ZFC gelöst würden, und dass das Problem des Anhaltens nur ein Problem der Informatik wäre. Das ist nicht der Fall. Es gibt eine Eins-zu-eins-Entsprechung zwischen Unvollständigkeit und Stillstandsproblem, es ist dasselbe Problem. Ich denke nicht, dass Unvollständigkeit schlechter oder besser ist als Inkonsistenz, aber ich denke, dass Unvollständigkeit zu Inkonsistenz wird, wenn Sie Systeme höherer Ordnung aufbauen wollen.
Hernan_eche
17

Nun, Sie können immer eine Turing-Maschine in Betracht ziehen, die mit einem Orakel für das gewöhnliche Problem des Anhaltens der Turing-Maschine ausgestattet ist. Das heißt, Ihre neue Maschine verfügt über ein spezielles Band, auf das Sie die Beschreibung einer normalen Turing-Maschine und deren Eingabe schreiben und fragen können, ob diese Maschine bei dieser Eingabe anhält. In einem einzigen Schritt erhalten Sie eine Antwort, mit der Sie weitere Berechnungen durchführen können. (Es spielt keine Rolle, ob es sich um einen einzelnen Schritt handelt oder nicht: Es würde ausreichen, wenn garantiert würde, dass er sich in einer endlichen Anzahl von Schritten befindet.)

Bei diesem Ansatz gibt es jedoch zwei Probleme.

  1. Mit einem solchen Orakel ausgestattete Turing-Maschinen können ihr eigenes Stopp-Problem nicht entscheiden: Der Beweis von Turing für die Unentscheidbarkeit des gewöhnlichen Stopp-Problems kann leicht an diese neue Einstellung angepasst werden. Tatsächlich gibt es eine unendliche Hierarchie, die als "Turing-Grade" bezeichnet wird und dadurch entsteht, dass die nächste Hierarchieebene ein Orakel für das Stopp-Problem der vorherigen Ebene darstellt.

  2. Niemand hat jemals vorgeschlagen, wie ein solches Orakel physisch umgesetzt werden könnte. Es ist alles sehr gut als theoretisches Gerät, aber niemand hat eine Ahnung, wie man eines baut.

Beachten Sie auch, dass ZFC in gewissem Sinne schwächer als die naive Mengenlehre und nicht stärker ist. ZFC kann Russells Paradoxon nicht ausdrücken, wohingegen naive Mengenlehre dies kann. Eine bessere Analogie wäre daher die Frage, ob das Problem des Anhaltens für schwächere Rechenmodelle als Turing-Maschinen entscheidbar ist. Zum Beispiel ist das Halteproblem für deterministische endliche Automaten (DFAs) entscheidbar, da DFAs für jede Eingabe garantiert angehalten werden.

David Richerby
quelle
Ich denke, dass sein eigenes Problem des Anhaltens von jeder Familie von Automaten gelöst werden kann, wenn es trivial ist, das heißt, dass entweder alle anhalten oder keiner von ihnen anhält (was in diesem Fall als seltsam angesehen werden kann).
Babou
1
@babou: Was ist mit Automaten, bei denen Maschine 0 für immer eine Schleife durchläuft, Maschine 1 FALSE ausgibt, wenn ihre Eingabe 0 ist, sonst TRUE ausgibt und dann anhält. Alle anderen Maschinen geben FALSE aus und halten dann an. Ist das eine Familie von Automaten, in der Programm 1 das nicht triviale Problem des Anhaltens löst? Oder handelt es sich nicht einmal um eine Automatenfamilie, weil eine Eigenschaft fehlt, zB irgendeine Art von Komposition?
Steve Jessop
@SteveJessop Nun, Sie (und Davis Richerby) haben wahrscheinlich in gewisser Hinsicht recht. Was mich stört, ist, dass dies ein erfundenes Beispiel ist. Sie bauen eine sehr schwache Familie auf, so dass eine Maschine in der Familie eine entscheidende Rolle für die ganze Familie spielt. Aber, wie Sie vermuten (vgl. Ihre Bemerkung zur Zusammensetzung), fehlt möglicherweise eine grundlegende Verschlusseigenschaft, damit das Problem trivialisiert werden kann. Ich habe keine Antwort parat, und ich stimme zu, dass meine Bemerkung eine genauere Beschreibung dessen erfordert, was eine Automatenfamilie ausmacht, aber Ihr Gegenbeispiel lässt mich nicht überzeugt.
Babou
3

Warnung: Eine philosophische / nicht strenge Antwort

Das könnte ein bisschen "philosophisch" werden, aber ich denke, es passt zum Geist Ihrer Frage.

Eine nicht wiederholbare Maschine

Ein Eckpfeiler des Beweises für das Stopp-Problem ist, dass sich eine Turing-Maschine wie eine Funktion verhält: Für den gleichen Eingang gibt es immer den gleichen Ausgang. Wenn Sie diese Eigenschaft entfernen, müssen Sie sich nicht mit dem "allgemeinen" Problem des Anhaltens befassen, da der Computer seine eigenen Eigenschaften erkennen kann. Sie verlieren aber auch viele der wünschenswerten theoretischen Eigenschaften einer solchen Maschine.

Eigenschaften entfernen

Es ist ein bisschen so, als würde man von der Mengen- zur Kategorietheorie übergehen: Man verliert einige der "Paradoxone", indem man die Grenzen verliert. Das Ergebnis ist jedoch viel schwieriger zu handhaben.

In diesem Fall heißt das: Sie hätten keine Ahnung, ob die Maschine Ihnen das "richtige" Ergebnis präsentiert. Sobald Sie immer entscheiden können, welches Ergebnis richtig ist, müssen Sie sich mit einer Art "Stillstandsproblem" befassen, indem Sie die Maschine auf sich selbst anwenden und einen Widerspruch konstruieren. Eine solche Maschine wäre also wahrscheinlich nicht sehr nützlich.

stefan.schwetschke
quelle
1
Danke, das "nicht wiederholbare Gerät" klingt eigentlich ziemlich interessant. Ich fühle mich nicht kompetent genug, um ein wenig Weisheit über clevere Selbstinspektionsprogramme zu haben (weil sie nach meinem Bauchgefühl immer noch als Turing-Maschinen ausgedrückt werden können), aber ich denke, dass sie für einige Probleme sehr nützlich sein können.
H2CO3
1
Wie würde man ein Beispiel für Nichtwiederholbarkeit geben? Und wie würden Sie in diesem Fall das Anhalten definieren? Eine Hauptschwierigkeit besteht darin, dass Sie, wenn Sie versuchen, ein seltsames, normalerweise gedankenbehaftetes Rechenmodell zu definieren, die Bedeutung des Anhaltens und die Art der Eingabe definieren müssen, die die Entscheidungsmaschine analysieren soll, und möglicherweise einige andere nicht triviale Dinge. Siehe zum Beispiel den Fall des Nichtdeterminismus . Ganz zu schweigen von der Frage, was als Rechenmodell angesehen werden kann (wahrscheinlich keine Ad-hoc-Sammlung von Maschinen).
Babou
1
@ H2CO3 Eine nicht wiederholbare Maschine ist nur eine Art "Gedankenexperiment" darüber, welche Eigenschaft Sie opfern müssen, um aus dem "allgemeinen Stillstandsproblem" herauszukommen (indem Sie einen Widerspruch konstruieren, indem Sie die Maschine sich selbst inspizieren lassen). Sie werden eine Maschine bekommen, die manchmal richtig ist, aber Sie wissen nicht wann. Es ist wie das Programm, das die Lottozahlen für die nächste Woche berechnet. Ich kann Ihnen so ein Programm leicht zur Verfügung stellen. Der schwierige Teil ist für Sie zu entscheiden, welches der vielen Programme, die ich Ihnen geben werde, das richtige ist ...
stefan.schwetschke
2

Das Halteproblem wurde nicht formuliert, um die Beschränkungen von Turingmaschinen auszudrücken, sondern um eine Beschränkung aller Logiksysteme auszudrücken , die unter Verwendung einer endlichen Anzahl von Symbolen ausgedrückt werden können. Sobald ein Logiksystem die Fähigkeit hat, Lösungen für Probleme bestimmter Komplexität auszudrücken, kann es auch Probleme ausdrücken, die es nicht lösen kann. Jede Erweiterung eines Logiksystems, die ausreicht, um Lösungen für alle Probleme auszudrücken, die es zuvor nicht lösen konnte, beinhaltet auch die Fähigkeit, neue Probleme auszudrücken, die es nicht lösen kann.

Bei einer bestimmten "Enhanced Turing Machine" -Spezifikation wäre es möglich, eine "Super-Enhanced Turing Machine" anzugeben, die ein Programm für das ETM untersuchen und melden könnte, ob es anhalten würde, aber das SETM könnte nur Programme für analysieren das ETM - es wäre nicht in der Lage, SETM-Programme zu analysieren. Es gibt keine Möglichkeit, eine Maschine zu definieren, die Programme für sich selbst analysieren und feststellen kann, ob sie anhalten, da durch das Hinzufügen neuer Funktionen neue Anforderungen für einen Selbstanalysator entstehen, und es gibt keine Möglichkeit, die Funktionen an die Anforderungen anzupassen .

Superkatze
quelle
1

Solche Maschinen wurden ins Auge gefasst und werden Super-Turing- Maschinen genannt. Es gibt mehrere Hauptklassen von Super-Turing-Maschinen

  • Reelle Zahlenmaschinen (zB analoge Computer)
  • Turing-Maschinen haben unendlich viel Zeit
  • Nichtdeterministische Turingmaschine

Nicht alle Super-Turing-Maschinen können das Stopp-Problem lösen (insbesondere nicht deterministische Turing-Maschinen nicht). Die konzeptionellen Maschinen wurden jedoch zumindest in Gedankenexperimenten geschaffen.

Cort Ammon - Setzen Sie Monica wieder ein
quelle