Wie überwinden Modelle der Hyperberechnung das Halteproblem?

Hypercomputation bezieht sich auf Berechnungsmodelle, die mit Turing-Maschinen nicht simuliert werden können. (Hypercomputer sind physikalisch nicht unbedingt realisierbar!) Einige Hypercomputer haben Zugriff auf eine Ressource, mit der das Halteproblem für Standard-Turing-Maschinen gelöst werden kann. Nennen Sie dies eine "Supermacht": Ein Hypercomputer mit einer Supermacht kann entscheiden, ob eine Standard-Turing-Maschine terminiert.

Welche Arten von "Supermächten" verwenden Hypercomputer?

Die These von Ed Blakey schafft einen formalen Rahmen, um einige der wichtigsten Arten von Ressourcen zu klassifizieren, die für Hypercomputing verwendet werden. Es wird jedoch nicht versucht, einen umfassenden Überblick über die Supermächte zu geben. Ich bin nicht an einer Liste von Hypercomputern interessiert (es gibt eine nette Liste im Wikipedia-Artikel), sondern daran zu verstehen, welche "spezielle Sauce" jedes Modell verwendet, vielleicht als eine einzigartige Art von Ressource angesehen.

Diese Frage ist inspiriert von Wie grundlegend ist Unentscheidbarkeit? . Auch ist im Zusammenhang Was würde es bedeuten , Church-Turing - These zu widerlegen? Was zu vielen interessanten Diskussionen geführt hat, und gibt es derzeit Berechnungsmodelle mit der Möglichkeit, leistungsstärker als Turing Machines zu sein? .

In der Arbeit Über die Multiplikationsfähigkeit von Maschinen mit wahlfreiem Zugriff wurde von Hartmanis bewiesen, dass, wenn wir eine Einheitskosten-Multiplikationsanweisung in einem RAM (MRAM genannt) hinzufügen, für dieses Modell P = NP gilt. Außerdem sind die im MRAM-Modell in Polynomialzeit festgelegten Sprachen genau die Sprachen in PSPACE.

Wie in der Veröffentlichung angegeben, zeigen diese Ergebnisse, dass die Multiplikation dieselbe Komplexität aufweist wie die Addition, wenn P = PSPACE.

Ein verwandteres Ergebnis, von dem ich gehört habe, ist, dass wir unentscheidbare Probleme lösen können, wenn wir einen Divisionsbefehl mit unendlicher Genauigkeit in einem RAM hinzufügen. Das Papier, das dieses Ergebnis belegt, konnte ich jedoch nicht finden. Wenn jemand damit vertraut ist, bitte kommentieren und ich werde die Antwort aktualisieren.

Sie haben also festgestellt, dass TMs nicht jedes Problem lösen können! Der allererste Schritt, den Turing unternommen hat und der sehr logisch ist (obwohl nicht trivial, wenn man den damaligen Computerzustand berücksichtigt), waren Orakel.

Informell fügen Sie Ihrer Maschine ein neues Black-Box-Modul hinzu, das das Problem, das Ihre Maschine nicht lösen kann, "irgendwie" lösen kann, sagen wir das Problem des Anhaltens. Natürlich sind Orakel nur eine mathematische Abstraktion und es gibt kein Geheimnis hinter ihrem Innenleben. Persönlich sehe ich keine Möglichkeit, mit einem Orakel ein Modell zu entdecken, das die These von Church-Turing widerlegt.

• Zeit und Raum manipulieren

Da das Problem beim Beheben des Halteproblems darin besteht, dass Sie wissen, wann die Maschine anhalten wird, können Sie es beheben, indem Sie die Maschine in einer anderen als unserer Raumzeit laufen lassen. Aus meinen Quellen, als ich einen Bericht über Modelle schrieb, die effizient lösen können$NP$Theoretische Physiker glauben, dass diese Bedingungen in der Nähe des Randes der Schwarzen Löcher erfüllt sind. Dazu muss sich der Computer ganz in der Nähe des Schwarzen Lochs befinden, aber nicht in seinem Ereignishorizont (damit er nicht eingezogen wird). Dann tauchen Sie in das Schwarze Loch ein und Sie können die gesamte unendliche Zeitleiste Ihrer Maschine in endlicher Zeit überprüfen. Dies bedeutet wahrscheinlich, dass Sie in das Schwarze Loch gezogen werden. Ich denke, es wird nicht implementiert und getestet, auch wenn wir ein Schwarzes Loch erreichen könnten. Dies ist alles informell, Sie beginnen, einen theoretischeren Ansatz der Physik aus dem Wikipedia-Artikel über die Malament-Hogarth_Spacetime zu lesen . Ein nützliches Zitat ist auch der Artikel. Ermöglicht die allgemeine Relativitätstheorie einem Betrachter, eine Ewigkeit in einer endlichen Zeit zu betrachten?

• Zenos Maschine könnte jedes Problem in 2 Sekunden lösen, aber es ist eine mathematisch hypothetische Konstruktion, bei der jeder Schritt die Hälfte der Zeit davor und der erste 1 Sekunde dauert. Es bietet keine reale Lösung, die Sie implementieren könnten.

Es gibt andere Modelle, die ich kenne, aber ich denke, sie erweitern einfach die hier vorgestellten Ideen oder sind rein mathematische Konstruktionen. Sie sind also eher "nette Tricks" als etwas, das die These von Church-Turing widerlegen könnte.

Nicht genau das, worum Sie gebeten haben, aber Scott Aaronson hat einen Artikel, der hier schön über Turing-Maschinen mit Zeitreisefähigkeit, aber Selbstkonsistenzanforderungen (dh Sie können nicht zurückkehren, um die Vergangenheit zu ändern. Sie können die Zukunft beobachten) erklärt , aber es muss mit der Gegenwart vereinbar sein).