Turingmaschine + Zeitdilatation = Halteproblem lösen?

15

Es gibt relativistische Raumzeiten (z. B. MH-Raumzeiten; siehe Hogarth 1994), in denen eine Weltlinie unendlicher Dauer in der Vergangenheit eines endlichen Beobachters enthalten sein kann. Dies bedeutet, dass ein normaler Beobachter auf eine unendliche Anzahl von Rechenschritten zugreifen kann.

Vorausgesetzt, es ist möglich, dass ein Computer unendlich lange perfekt funktioniert (und ich weiß, das ist eine große Frage): Man könnte einen Computer HM konstruieren, der sich entlang dieser unendlichen Weltlinie bewegt und das Halteproblem für ein gegebenes M berechnet. Wenn M anhält , HM sendet ein Signal an den endlichen Beobachter. Wenn der Beobachter nach einer unendlichen Anzahl von Schritten kein Signal erhält, weiß der Beobachter, dass M eine Schleife bildet, wodurch das Halteproblem gelöst wird.

Bisher klingt das okay für mich. Meine Frage ist: Wenn das, was ich bisher gesagt habe, richtig ist, wie ändert dies den Beweis von Turing, dass das Problem des Anhaltens nicht zu entscheiden ist? Warum scheitert sein Beweis in diesen Zeiten ?

Gänseblümchen
quelle
Möglicherweise relevant: researchgate.net/publication/… .
Martín-Blas Pérez Pinilla
1
Wird der Beobachter unendlicher Dauer Zugang zu unendlicher Energie haben, um seine unendlichen Rechenschritte durchzuführen? (Kann alternativ ein Testgerät für Halteprobleme reversibel formuliert werden? Ich würde es nicht glauben.)
user253751
Auf jeden Fall relevant: chiark.greenend.org.uk/~sgtatham/infinity.html
Jules
@immibis: Ja, das tut es! Ich habe das am College studiert.
Joshua
Beachten Sie, dass es ein weit verbreitetes Missverständnis ist, dass eine sich drehende Maschine, die nicht anhält, eine Schleife ausführen muss. Dies impliziert eine Art wiederholten Zustand oder das gleiche immer und immer wieder zu tun. Tatsächlich können wir entscheiden, ob eine Maschine dieses Verhalten aufweist oder anhält, wenn sie eines der beiden ausführt. Die lästigen Maschinen, die uns durcheinander bringen, sind nicht die schleifenhaften, sondern die, die chaotisch in einem fast zufälligen Muster herumwirbeln und sich jeglicher Regelmäßigkeit widersetzen.
Exfret

Antworten:

25

Beachten Sie, dass Turings Beweis ein mathematischer und kein physikalischer ist. Innerhalb des Modells einer Turingmaschine Turing definiert, hat sich die Unentscheidbarkeit des Halteproblems bewährt und ist eine mathematische Tatsache. Daher wird Turings Beweis in den Raumzeiten nicht "scheitern", er wird einfach nichts über das Verhältnis des Halteproblems und der Zeitdilatation beweisen.

Was Sie jedoch wahrscheinlich wissen möchten, ist, ob eine "Zeitdilatations-Turing-Maschine" das Problem des Anhaltens lösen kann.

Wenn Sie den Einfluss der Zeitdilatation auf eine Turing-Maschine untersuchen möchten, müssen Sie ein formales Modell angeben, anhand dessen wir formal verstehen können, was es für eine Turing-Maschine bedeutet, die Zeitdilatation zu nutzen. Leider ist dieses Format nicht für die Bereitstellung eines solchen formalen Modells geeignet (es sei denn, jemand anderes hat eine Abhandlung darüber geschrieben), da die Erstellung des Modells viel zu umfangreich ist.

Es ist jedoch nicht unwahrscheinlich, dass eine Formalisierung tatsächlich das Problem des Stillstands lösen kann. Diese Arbeit von Scott Aaronson, Mohammad Bavarian und Giulio Gueltrini untersucht Rechenmodelle unter der Annahme, dass sogenannte Closed-Time-like-Loops existieren, und gelangt zu dem Schluss, dass das Stopp-Problem tatsächlich innerhalb dieses Modells berechenbar ist.

Diskrete Eidechse
quelle
4
Vielleicht ist es auch nützlich, dass der Formalismus einer "Hyper-Turing-Maschine" als eine Turong-Maschine, die eine unendliche Anzahl von Schritten in einer endlichen Zeitspanne ausführen kann, in der Tat ein allgemeiner Formalismus ist. Möglicherweise finden Sie dort viele nützliche Informationen.
Cort Ammon - Reinstate Monica
10

Die Turing-Maschine ist ein formales mathematisches Rechenmodell, sie reagiert nicht auf physikalische Einschränkungen und kümmert sich nicht um relativistische Effekte. Dies bedeutet, dass Turings Beweis nicht fehlschlägt, da die Standarddefinition der Turing-Maschine nicht einmal den Begriff "Raumzeit" enthält.

Sie können versuchen, ein anderes, von der Relativität inspiriertes Berechnungsmodell zu definieren. Auch hier handelt es sich nur um ein formales Objekt, und die Frage, ob es das Halteproblem lösen kann oder nicht, liegt im Bereich der Mathematik und hängt von Ihrer spezifischen Definition ab. Die wahre Frage ist nun jedoch, ob dieses neue Modell tatsächlich relativistische Effekte richtig erfasst, dh unsere Physik wirklich widerspiegelt und in unserer Welt implementiert werden kann?

Sie können eine solche Diskussion über die Quantenberechnung sehen. Wir haben eine formale Definition von "Quanten-Turing-Maschinen", und ihre exakte Rechenleistung bleibt ein offenes Problem in der Mathematik (obwohl sie dem Halteproblem nicht einmal nahe kommt). Dennoch kann man argumentieren, dass diese Definition unser Verständnis der Quantenphysik nicht wirklich widerspiegelt und eine bessere benötigt wird. Es gibt Argumente , die darauf hindeuten, dass solche Maschinen nicht einmal gebaut werden können, weshalb ihre genaue Kraft keinen Einfluss auf die (starke) These von Church-Turing hat.

Zurück zu deiner Frage. Es gibt eine formale Vorstellung von einer unendlichen Zeit-Turing-Maschine , aber damit sie sich auf die Church-Turing-These auswirkt, muss sie in der Praxis existieren. Sie könnten in Scotts interessiert sein Papier , das einen Abschnitt über Berechnungen unter Verwendung relativistische Effekte hat, obwohl es scheint, dass naive Argumente aussichtslos sind (in dem Sinne , dass sie unpraktisch sind, als Zeitkosten durch Energiekosten ersetzt wird).

Ariel
quelle
1
Re. "... damit sich das auf die Church-Turing-These auswirkt, muss es in der Praxis existieren." - Sind Turingmaschinen nicht auch idealisierte Maschinen, die es in der Praxis nicht gibt?
Daisy
1
In der Tat spiegelt es nur unsere Intuition wider (oder versucht es zumindest), was eine "Computermaschine" ist. Aus diesem Grund ist die Church-Turing-These eine These und kein mathematischer Satz. Es wird nur informell behauptet, dass Turing-Maschinen die wahre Rechenleistung einfangen, die in unserer Welt existiert.
Ariel
Mein Punkt ist: Warum muss eine unendliche Zeit Turing-Maschine in der Praxis existieren, um eine Auswirkung auf die CTT zu haben, wenn es in der Praxis auch keine Standard-Turing-Maschinen gibt?
Daisy
1
Eine Formulierung der Church-Turing-These lautet: Jedes in unserer Welt realisierbare Rechenmodell übersteigt nicht die Leistung der Turing-Maschine. Die These selbst ist relativ zu einem Bodenmodell (nämlich der Turing-Maschine) definiert.
Ariel
Ich habe eine Folgefrage gestellt, weil ich die Behauptung, dass eine praktische Quantenturing-Maschine nicht gebaut werden kann, auch nach Durchsicht der Folien nicht wirklich verstehe. (2. Mal, um diesen Kommentar zu posten, zeigt jetzt auf QC.SE anstelle von CS.SE)
BurnsBA
7

Der Beweis von Turing zeigt, dass keine Turing-Maschine das Halteproblem lösen kann, egal wie viel Zeit Sie darauf verwenden. Wenn Ihr Raumschiff Zeitverlängerungen verwendet hat, um einem Computer eine Milliarde Jahre Arbeit zu ermöglichen, kann es Ihnen möglicherweise immer noch nichts Bestimmtes sagen als "Noch nicht".

Anscheinend (Danke, @DiscreteLizard!), Wenn Sie eine Zeitreise haben, die keine Paradoxien verursachen kann, können Sie eine Zeitschleife einrichten , die ein Paradoxon hervorruft, wenn der Computer nicht nachweisen kann, ob die Turing-Maschine anhält. Entweder empfängt es die Antwort aus der Zukunft und sendet sie an sich selbst zurück, oder es läuft für immer (und liefert geschickt eine Quantenüberlagerung zurück, die sich in eine stabile Zeitschleife auflöst). Bevor Sie dies versuchen, sollten Sie sich jedoch sicher sein, dass es sicher ist, ein Zeitreise-Paradoxon auszulösen.

Davislor
quelle
2
"Es gibt noch nicht genügend Daten für eine aussagekräftige Antwort."
Columbia sagt Reinstate Monica
Beachten Sie, dass der Hauptgrund, warum ich Turing-Maschinen in geschlossenen zeitähnlichen Schleifen erwähnte, darin besteht, dass das Modell der Turing-Maschine physisch so verändert wurde, dass das Problem des Anhaltens von dieser Maschine berechnet werden kann. Es scheint, dass andere mehr über Zeitdilatation wissen als ich, aber dieses Beispiel lässt mich zumindest zögern, solche Behauptungen aufzustellen, es sei denn, es wird eine Formalisierung der Zeitdilatation angegeben.
Diskrete Eidechse
@Discretelizard Das war ein toller Beitrag zur Diskussion. Ich bin nicht sicher, ob ich die Absicht des OP vollständig verstehe, aber relativistische Zeitdilatation ist ein echtes Konzept in der modernen Physik, und ich antwortete unter der Annahme, dass er die Standarddefinition des Begriffs verwendete.
Davislor
@Davislor Natürlich ist die Zeitdilatation in der Physik genau definiert . Eine Turingmaschine ist ein mathematisches Objekt. Soweit mir bekannt ist, besteht das Beste, was wir tun können, um beides zu kombinieren, darin, eine „physikalische Analogie“ für eine Turing-Maschine zu erstellen und formal zu zeigen, wie dies mit der Zeitdilatation zusammenwirkt. Dies ist (ein Beispiel dafür), was ich mit einer "Formalisierung" meine. Ich glaube nicht, dass es einen einzigartigen Weg gibt, dies zu formalisieren, und dass die Ergebnisse unterschiedlich ausfallen können, weshalb ich zögere, etwas Bestimmtes darüber zu sagen.
Diskrete Eidechse
Das heißt, es könnte möglich sein, dass die Antwort für jede vernünftige Formalisierung "Nein" lautet, aber eine solche Behauptung liegt zumindest außerhalb meines Fachwissens.
Diskrete Eidechse
5

Ein Einwand ist, dass Sie einen Prozess definiert haben, der eine unendliche Entropie in einer kompakten Region erzeugen kann und dies in einem endlichen Abschnitt der Vergangenheit des Beobachters zu tun scheint. Das bedeutet ein paar Dinge

  • Die Rechenentropie in der Kompaktregion übersteigt den Bekensteingebunden an Entropie (wobei die Grenze proportional zur Oberfläche der Region ist), so dass sie (sofort) in ein Schwarzes Loch zusammenfällt und kein Signal Sie jemals von innen erreichen kann. (Die Kerr-Metrik beschreibt eine MH-Raumzeit. Der unendliche Prozess wird nur beobachtet, wenn der Beobachter in den inneren Ereignishorizont übergeht. Ungeachtet der gegenwärtigen Unsicherheit über die Physik einer solchen Passage hat kein entfernter Beobachter jemals Zugriff auf das Ergebnis der Berechnung - Nur der Beobachter, der im Schwarzen Loch verschwunden ist, hat das Ergebnis. Dies ist keine Beschreibung eines nützlichen Berechnungsprozesses. Um es mit anderen Worten zu sagen: "Wir haben ein Orakel, das die richtige Antwort auf jede Frage liefert, die Sie in konstanter Zeit stellen eine Möglichkeit, dass die Antwort nur in dem Moment existiert, in dem sie zerstört wird, indem sie in ein schwarzes Loch gespült wird. ")
  • Eine Turing-Maschine zerstört jedes Mal Informationen, wenn sie ein Symbol auf einem Band überschreibt. Daher muss nach Landauers Prinzip eine endliche Berechnung auf einer unendlichen Weltlinie, die im vergangenen Lichtkegel der Beobachtung zu einem endlichen Segment komprimiert wurde, beobachtet werden, um unendliche Leistung zu benötigen und zu emittieren Unendliche Hitze während der infinitesimalen Betriebszeit. Das heißt, da ein Halt in endlicher Zeit erreicht wird, wird er aus Sicht des externen Beobachters sofort erreicht, so dass die gesamte Leistung sofort verbraucht und die gesamte Wärme sofort freigesetzt wird. Wenn die Berechnung nicht angehalten wird, verbraucht der kompakte Bereich alternativ kontinuierlich unendliche Energie und gibt unendliche Wärme ab. Nettoergebnis: wieder ein Schwarzes Loch.
  • Alternativ gilt das Landauer-Prinzip nicht für das reversible Rechnen und es gibt ( universelle ) reversible Turing-Maschinen . Eine solche Turing-Maschine erfordert jedoch die Fähigkeit, den gesamten Raum potentieller Rechenzustände abzubilden, der exponentiell in der Größe der verwendeten Bandmenge ist, so dass er schnell in die Bekenstein-Schranke hineinläuft. Am Ende können wir das Hitzeproblem nur vermeiden, indem wir uns auf Bänder mit begrenzter Länge beschränken. Entsprechend haben wir eine Obergrenze für die verwendbare Bandlänge, die durch die Oberfläche der Region mit einer unendlichen Weltlinie gesteuert wird. Wenn Sie dies nicht berücksichtigen und Ihre Berechnung zu viel Band verwendet, erhalten Sie erneut ein schwarzes Loch.

Es ist eine interessante offene Frage, ob und wie diese Einschränkungen für Quantencomputer gelten. Es kann durchaus sein, dass die Komplexität einer von einem Quantencomputer durchführbaren Berechnung durch die Oberfläche des Computers begrenzt ist. Daher müssen wir möglicherweise die Oberfläche eines extremen Quantencomputers verdoppeln, um ein weiteres verwendbares Qubit für die Berechnung zu erhalten. Dies führt schnell zu unpraktisch großen Computern.

Eric Towers
quelle
1

Zitat aus Pony, Crunches, Whimpers und Shrieks:

π
(x1)(x2)(xn)F(xl,x2,,xn)γ1nγ1Aus diesen Arbeiten gewinnt man ein Wissen über den Wahrheitsgehalt der Behauptung. Sobald jedoch gemischte Quantifizierer beteiligt sind, schlägt die Methode fehl. Hogarth (1994) hat jedoch gezeigt, wie kompliziertere Anordnungen in allgemein relativistischen Raumzeiten prinzipiell verwendet werden können, um den Wahrheitswert jeder arithmetischen Behauptung von willkürlicher quantifizierender Komplexität zu überprüfen. In solch einer Raumzeit ist es schwer zu verstehen, wie man die Haltung beibehält, dass wir in der Arithmetik keine klare Vorstellung von der Wahrheit haben.
Martín-Blas Pérez Pinilla
quelle