Was wissen wir über eingeschränkte Versionen des Halteproblems?

16

( UPDATE : Hier wird eine besser formulierte Frage gestellt , da die Kommentare für die akzeptierte Antwort unten zeigen, dass diese Frage nicht genau definiert ist.)


Der klassische Beweis für die Unmöglichkeit des Halteproblems hängt davon ab, einen Widerspruch aufzuzeigen, wenn versucht wird, den Algorithmus der Halteerkennung auf sich selbst als Eingabe anzuwenden. Weitere Informationen finden Sie im Hintergrund unten.

Der aufgezeigte Widerspruch gilt aufgrund eines selbstreferenziellen Paradoxons (wie der Satz "Dieser Satz ist nicht wahr"). Aber wenn wir solche Selbstreferenzen strengstens verboten haben (dh die Tatsache akzeptiert haben, dass solche Selbstreferenzen nicht zum Stillstand gebracht werden können), mit welchem ​​Ergebnis verbleiben wir dann? Ist das Problem des Anhaltens für den verbleibenden Satz nicht selbstreferenzierender Maschinen zum Anhalten entschlossen oder nicht?

Die Fragen sind:

Wenn wir eine Teilmenge aller möglichen Turing-Maschinen betrachten, die nicht selbstreferenzierend sind (dh sich selbst nicht als Eingabe nehmen), was wissen wir über das Problem des Anhaltens für diese Teilmenge?

AKTUALISIEREN

Vielleicht ist eine bessere Neuformulierung dessen, wonach ich suche, ein besseres Verständnis dessen, was eine entscheidbare Menge definiert. Ich habe versucht, den klassischen Unentscheidbarkeitsbeweis zu isolieren, da er keine Informationen über die Unentscheidbarkeit enthält, außer in den Fällen, in denen Sie HALT für sich selbst ausführen.

Hintergrund: Unter der Annahme eines Widerspruchs, dass es eine Turing-Maschine , die über die Eingabe M entscheiden kann, die eine Codierung für eine Turing-Maschine ist, und X , ob M ( X ) anhält oder nicht . Betrachten Sie dann eine Turing-Maschine K , die M und X nimmt und Q verwendet , um zu entscheiden, ob M ( X ) anhält oder nicht, und dann das Gegenteil tut, dh K hält an, wenn M ( X ) nicht anhält und nicht anhält, wenn M ( X )QMXM(X)KMXQM(X)KM(X)M(X)hält an. Dann demonstriert einen Widerspruch, da K anhalten sollte, wenn es nicht anhält, und nicht anhält, wenn es anhält.K(K)K

Motivation: Ein Kollege arbeitet an der formalen Verifizierung von Softwaresystemen (insbesondere, wenn das System bereits auf Quellcodeebene getestet wurde und wir es für seine kompilierte Version vorenthalten möchten, um Compilerprobleme zu neutralisieren), und in seinem Fall kümmert er sich um a Spezieller Satz eingebetteter Steuerungsprogramme, von denen wir sicher sind, dass sie nicht selbstreferenzierend sind. Ein Aspekt der Überprüfung, die er durchführen möchte, ist, ob garantiert wird, dass das kompilierte Programm anhält, wenn der eingegebene Quellcode nachweislich beendet wird.

AKTUALISIEREN

Basierend auf den Kommentaren unten erkläre ich die Bedeutung von nicht selbstreferenzierenden Turing-Maschinen.

Ziel ist es, sie als die Menge zu definieren, die nicht zu dem im Beweis gestellten Widerspruch führt (vgl. "Hintergrund" oben). Es könnte wie folgt definiert werden:

Unter der Annahme, dass es eine Turing-Maschine , die das Halteproblem für einen Satz von Turing-Maschinen S entscheidet , ist S in Bezug auf Q nicht selbstreferenzierend, wenn es alle Maschinen ausschließt, die Q auf S aufrufen (direkt oder indirekt). (Das bedeutet natürlich, dass Q kein Mitglied von S sein kann .)QSSQQSQS

Um zu klären, was unter indirektem Aufrufen von auf S zu verstehen ist:QS

Das Aufrufen von auf S wird durch eine Turing-Maschine Q mit einem Satz von Zuständen und bestimmten möglichen Anfangseingaben auf dem Band (die einem Mitglied von S entsprechen ) bezeichnet, wobei der Kopf anfänglich am Anfang dieser Eingabe steht. Eine Maschine W ruft Q auf S "indirekt" auf, wenn es eine (endliche) Folge von Schritten gibt, die W unternehmen würde, um ihre Konfiguration "homomorph" zur Anfangskonfiguration von Q ( S ) zu machen .QSQSWQSWQ(S)

UPDATE 2

Aus der folgenden Antwort geht hervor, dass es unendlich viele Turing-Maschinen gibt, die dieselbe Aufgabe ausführen, und daher nicht eindeutig ist. Wir ändern die obige Definition, indem wir sagen, dass Q keine einzelne Turing-Maschine ist, sondern die (unendliche) Menge aller Computer die gleiche Funktion (HALT), wobei HALT die Funktion ist, die entscheidet, was eine Turing-Maschine bei einer bestimmten Eingabe anhält.QQ

UPDATE 3

Die Definition des Turing Machine Homomorphismus:

A TM A ist homomorph zu TM B, wenn der Übergangsgraph von A homomorph zu dem von B ist, im üblichen Sinne von Homomorphismen von Graphen mit markierten Knoten UND Kanten. Ein Übergangsgraph (V, E) eines TM ist derart, dass V = Zustände, E = Übergangsbögen zwischen Zuständen sind. Jeder Bogen ist mit (S, W, D) gekennzeichnet. S = Symbol auf dem Band und W = Symbol, in das geschrieben werden soll, und D = Richtung, in die sich der Kopf bewegt.

M. Alaggan
quelle
5
"die verbleibende Menge von nicht selbstreferenzierenden" Bevor ich diese Menge sinnvoll diskutieren kann, möchte ich eine Definition von "selbstreferenzierend". Ich denke jedoch, dass es schwierig sein wird, das zu definieren?
Sam Nead
1
Es gibt Studien zu nachweislich stoppenden Programmen (diese Klasse umfasst jedoch nicht alle stoppenden Programme). Im Grunde sind sie ein Paar Programme und ein Beweis dafür, dass es anhält. Wenn ich mich beispielsweise nicht irre, lässt Agda nur Programme zu, die anhalten. Ich denke, dass Leute, die an Logik und Programmiersprachen arbeiten, mehr dazu zu sagen haben.
Tsuyoshi Ito
1
QS
2
Dies wirft eine interessante Frage auf: Sind alle Unberechenbarkeitsnachweise (Unentscheidbarkeitsnachweise) auf Cantors Diagonalisierungsmethode zurückzuführen? Gibt es einen Unentscheidbarkeitsbeweis, der nicht direkt oder indirekt auf der Diagonalisierungsmethode beruht?
Mohammad Al-Turkistany

Antworten:

9

Ich denke, es wird ein bisschen mehr Arbeit erfordern, um zu einer "genau definierten" Frage zu gelangen. Dies ist insbesondere problematisch:

Das Aufrufen von Q auf S wird durch eine Turing-Maschine Q mit einem Satz von Zuständen und bestimmten möglichen Anfangseingaben auf dem Band (die einem Mitglied von S entsprechen) bezeichnet, wobei der Kopf anfänglich am Anfang dieser Eingabe steht. Eine Maschine W ruft Q auf S "indirekt" auf, wenn es eine (endliche) Folge von Schritten gibt, die W unternehmen würde, um ihre Konfiguration "homomorph" zur Anfangskonfiguration von Q (S) zu machen.

Ein Problem ist, dass es unendlich viele Turingmaschinen gibt, die dieselbe Funktion berechnen. Im Standardargument für die Diagonalisierung kann ich die Q-Unterroutine einfach durch eine andere Entscheidung für HALT ersetzen, da es unendlich viele davon gibt. Oder eine Funktion, die HALT berechenbar entspricht. Daher ist mir nicht ganz klar, wie Sie Ihren Begriff der "indirekten Anrufung" definieren sollen.

Eine andere Frage könnte sein: Für welche Sätze von Turing-Maschinen ist das Halteproblem entscheidbar? Hier gibt es eine Fülle von Antworten: ressourcenbeschränkte TMs (z. B. nur f (n) Leerzeichen verwenden, wobei f eine bestimmte berechenbare Funktion ist), TMs, die in bestimmter Weise betriebsbeschränkt sind (z. B. Lesekopf bewegt sich nur in eine Richtung), usw Eine andere interessante Frage ist jedoch, ob die Zugehörigkeit zu dieser eingeschränkten Menge entscheidbar ist oder ob Sie sich auf "Versprechen von Problemen" beschränken müssen, bei denen Sie nur eine korrekte Antwort auf eine "versprochene" Teilmenge von Eingaben garantieren, diese jedoch nicht verifizieren Mitgliedschaft.

Mark Reitblatt
quelle
QH
So einfach ist das nicht. Ihre Definition ist jetzt paradox, da Sie nach einem berechenbaren HALT suchen. Ist dies jedoch berechenbar, entspricht jede berechenbare Funktion dieser Funktion. Wenn Ihr Eingabesatz jedoch semi-computable problems (TMs) enthält, besteht ein Widerspruch, da Sie ein Entscheidungsverfahren für dieses Problem erhalten, wenn Sie das Stopp-Problem für ein solches TM bestimmen.
Mark Reitblatt
1) Bedeutet ein nicht berechenbarer HALT nicht Unentscheidbarkeit? Ich ging davon aus, dass ein solches berechenbares HALT existiert, in der Hoffnung auf Widerspruch. 2) Ich bin nicht mit dem Konzept vertraut, dass alle berechenbaren Funktionen berechenbar gleichwertig sind. Ich habe Sie zitiert und damit gemeint, dass es sich um eine Funktion handelt, die das HALT-Problem löst. Anscheinend ist λx.1 berechenbar, entscheidet aber nicht über HALT. Korrigieren Sie mich, wenn ich mich bitte irre. In Bezug auf die halb berechenbaren Probleme kann HALT unendlich viele Schritte unternehmen, die immer noch nicht zum Widerspruch im ursprünglichen Beweis führen, dass HALT nicht entscheidbar ist.
M. Alaggan
1) Richtig. Das Problem besteht jedoch darin, Ihren Begriff der "Nicht-Selbstreferenzierung" zu definieren. Entweder ist es eine schwache Einschränkung, die Diagonalisierung erlaubt, wie ich argumentiert habe, oder es ist eine starke Einschränkung, die alles beseitigt. 2) Es ist ganz einfach. "Rechnerisch gleichwertig" bedeutet in etwa, dass es eine berechenbare Zuordnung von einem zum anderen gibt, die die Antworten beibehält. Aber wenn ich eine Antwort berechnen kann, kann ich schummeln und die Zuordnung trivial machen. 3) Wenn die TM, die HALT entscheidet, nicht selbst endet, ist dies keine Entscheidung für HALT.
Mark Reitblatt
Etwas anderes, etwas verwirrendes ist die Verschmelzung von TM mit dem von ihnen berechneten Entscheidungsproblem. Es ist nicht normal, von einer rechnerisch gleichwertigen TM zu sprechen. Vielmehr können die von ihnen berechneten Funktionen äquivalent (oder gleich) sein. Das Problem ist, dass der Versuch, zu sagen, dass ein TM kein anderes TM simuliert, im Allgemeinen schwer zu definieren ist, ohne dass etwas Konkretes angegeben wird, um die von ihnen berechneten Funktionen zu trennen. Beispielsweise kann ein Log-Space TM kein TM simulieren, das ein EXP-Space-Problem löst.
Mark Reitblatt
9

Wenn ich Ihre Motivation richtig verstehe, handelt es sich anscheinend eher um ein Problem mit der "Compiler-Korrektheit" als um ein Problem mit dem "eingeschränkten Anhalten". Sie haben eine Eigenschaft (Terminierung), die Sie für ein Programm auf Quellcodeebene Prog getestet haben und die Sie dann auf den kompilierten Code erweitern möchten, um dieselbe Eigenschaft von compiled (Prog) zu erhalten . Der Compiler kann jedoch (im Allgemeinen) beliebig viele Dinge tun, z. B. eine vollständig ausgeführte Laufzeit implementieren (z. B. die JVM), das abschließende Programm in einen JVM-Bytecode kompilieren und dann eine ausführbare Datei ausgeben, die die JVM startet und den kompilierten Bytecode eingibt.

In der Praxis ist es wahrscheinlich durchaus möglich, das implizite Wissen, das Sie über die Funktionsweise Ihres Compilers haben, zu nutzen, um eine Überprüfungsprozedur zu implementieren, die beweist, dass kompilierte Programme bei korrekten Quellprogrammen korrekt sind (in der Tat verwenden viele automatische Überprüfungswerkzeuge für Programme implizites Wissen des Algorithmus-zu-Code "Compiler" in den Köpfen der Programmierer). Im Allgemeinen sehen Sie jedoch wahrscheinlich ein Problem der Compiler-Korrektheit. Soweit ich weiß, gibt es zwei klassische Möglichkeiten.

Eine Möglichkeit besteht darin, einen Compiler zu haben, der das Programm Prog als Eingabe nimmt und den Proof beendet (Prog) und die Ausgaben kompiliert (Prog) und beendet (kompiliert (Prog)) - letzterer ist ein Proof, der dann unabhängig von den anderen doppelt geprüft werden kann der Compiler. Das klassische Papier dazu ist Necula and Lees Design und Implementierung eines zertifizierenden Compilers , glaube ich.

Alternativ können Sie eine Tatsache über die Funktion compiles () beweisen - dass immer, wenn compiles () eine abschließende Eingabe liefert, diese eine abschließende Ausgabe erzeugt. Eine leicht zugängliche Einführung in diese Art, über die Korrektheit von Compilern nachzudenken, ist der CACM-Artikel von Xavier Leroy, Formale Verifikation eines realistischen Compilers .

(PS: Ich hoffe, diese Antwort ist hilfreich. Ich erkenne, dass sie ein bisschen von der von Ihnen gestellten Frage abweicht. Lassen Sie mich also wissen, ob ich weit von der Basis entfernt bin und / oder etwas wiederhole, das Sie bereits wissen.)

Rob Simmons
quelle
Danke für die tolle Antwort. Dies wäre auf jeden Fall nützlich für meinen Kollegen. Ich bin jedoch (unabhängig von meinem Kollegen) mehr an den theoretischen Implikationen für den Beweis des Halteproblems interessiert. Wenn wir den widersprüchlichen Fall loswerden, was wissen wir dann noch über die Entscheidbarkeit des Halteproblems?
M. Alaggan