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 ?
quelle
Antworten:
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.
quelle
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).
quelle
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.
quelle
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
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.
quelle
Zitat aus Pony, Crunches, Whimpers und Shrieks:
quelle