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

( 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 $Q$$M$$X$$M(X)$$K$$M$$X$$Q$$M(X)$$K$$M(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 .)$Q$$S$$S$$Q$$Q$$S$$Q$$S$

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

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 .$Q$$S$$Q$$S$$W$$Q$$S$$W$$Q(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.$Q$$Q$

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.

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.

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.)