Konstruktiver Beweis der Entscheidbarkeit einer endlichen Menge im Halting-Problem-Stil, die keine Tabellensuche verwendet

7

Ich versuchte , zu beweisen , dass die folgende rekursive Sprache ist: für , eine positive ganze Zahl: , woΣ={0,1}k

Lk=HTM,εΣk
HTM,ε={MM is a TM that halts on an empty input}

Es ist leicht zu beweisen, weil endlich ist, aber ich habe dies nicht bemerkt und versucht, es zu beweisen, indem ich ein Decider TM dafür gefunden habe. Ich dachte, da die Codierung des TM die Länge hat, kann es nicht mehr als Zustände haben, und indem es für Schritte auf epsilon ausgeführt wird, wenn es bis dahin anhält, dann akzeptieren Sie anderweitig ablehnen. Mir wurde gesagt, dass es falsch ist - ist es eine falsche Lösung. Wie kann ich dies mit dieser Methode beweisen (und nicht mit der Art und Weise, wie ich erwähnt dass endlich ist)?Lkk2k2kLk

scifie
quelle
3
Ich habe mir erlaubt, Ihren Beitrag in LaTex-Form zu bearbeiten. Wenn ich Ihre Absicht falsch verstanden habe, können Sie sie gerne auf Ihre ursprüngliche Form zurücksetzen. Ich habe auch vorgeschlagen, es wieder zu öffnen. Mal sehen, wie das geht. Willkommen auf der Seite.
Rick Decker
Da unentscheidbar ist, kann es nicht durch eine rekursiv aufzählbare Vereinigung entscheidbarer Mengen dargestellt werden. Daher gibt es unentscheidbare unendliche (und co-unendliche) Teilmengen von . Daher müssen Sie die Endlichkeit in irgendeiner Weise verwenden. Sie fragen: "Wie zeige ich die Entscheidungsfähigkeit mit der Endlichkeit auf weniger offensichtliche Weise?". Ich bin mir nicht sicher, in welchem ​​Sinne das eine hilfreiche Frage für Sie ist. HTM,εHTM,ε
Raphael
@ Raphael: ist die Vereinigung der MengenHTM,ϵ{MM is aTM that halts within t steps on ϵ input} für positive ganze Zahlen t. DeshalbHTM,ϵist "eine rekursiv aufzählbare Vereinigung entscheidbarer Mengen".
@ RickyDemer Stimmt, danke. Mein Argument funktioniert nur für Nicht-Halbentscheidbarkeit (oder?).
Raphael

Antworten:

10

Es gibt keine allgemeine Möglichkeit, ein Decider TM für zu finden Lk

Sie haben Recht damit Lk ist rekursiv, weil es eine Teilmenge der endlichen Menge ist Σkes ist auch endlich.

Sie möchten lieber einen Entscheider TM für finden Lkund Sie schlagen einige Techniken vor. Ohne auf die Details dieser Techniken einzugehen und zu erklären, warum sie nicht funktionieren, haben Sie keine Chance, jemals Erfolg zu haben.

Das erste, was Sie bemerken sollten, ist, dass das Endlichkeitsargument Ihnen sagt, dass es einen Entscheider TM gibt Mk für die Sprache Lk, aber es sagt Ihnen nicht, was dieses TM ist. Es ist ein Beispiel für einen nicht konstruktiven Beweis: Sie beweisen, dass ein Entscheider existiert, aber Sie können nicht sagen, um welchen es sich handelt.

Nehmen wir nun an, dass gegeben kSie haben eine Prozedur P(k) einen solchen Entscheider zu finden Mk für die Sprache Lk(anstatt nur zu beweisen, dass es existiert). Dann gegeben jede TuringmaschineMdann gibt es eine ganze Zahl k so dass |M|=k, damit MΣk. Dann können Sie das Verfahren anwendenP um einen Entscheider TM zu finden Mk das kann bestimmen, ob MLk. So haben Sie eine Möglichkeit zu entscheiden, ob das TMM wird bei leerer Eingabe angehalten. Und das funktioniert für jedes TMM. Dies ist jedoch nicht möglich, da nicht entschieden werden kann, ob ein bestimmtes TM vorliegtM wird bei leerer Eingabe angehalten.

Also das Verfahren P kann nicht existieren.

Da suchen Sie nach einem allgemeinen Weg, um den Entscheider TM zu finden Mk, können Sie nicht erfolgreich sein, weil diese Methode genau eine Prozedur wie wäre P.

Beachten Sie, dass dieser Beweis immer noch die (sehr entfernte) Möglichkeit lassen kann, einen Entscheider für bestimmte Werte von zu finden k, aber Sie müssten die betroffenen Werte genau identifizieren, und die Methode würde nicht für alle Werte von funktionieren k. Ich rate Ihnen nicht, es zu versuchen.

babou
quelle
Die einzige Möglichkeit, es als rekursiv zu betrachten, besteht darin, das Argument der Zeugen zu verwenden.
Jon Prime
Ich habe versucht, dies auf diese Weise zu beweisen, da ich wahrscheinlich nicht sehr gut verstanden habe, wann ich solche Argumente über die Anzahl möglicher Konfigurationen und Zustände verwenden sollte: zum Beispiel die Frage, ob L100 = {<M> | ist M auf epsilon verwendet nicht mehr als 100 Stellen auf dem Band.} Rekursiv wird durch Ausführen des TM für | Q | · 100 · | Gama | ^ 100 + 1 Schritte bewiesen. Kann jemand bitte erklären, wann solche Argumente angemessen sind - in welchen Arten von Fragen, vielleicht ein paar Beispiele dafür, wann solche Argumente verwendet werden können und wann nicht?
Jon Prime
3
Ich denke, man kann niemals sagen, dass es nur einen Weg gibt, ein Ergebnis zu beweisen. Alles was ich sagen kann ist, dass jeder Beweis, der für alle Werte von funktioniertkwird notwendigerweise ein nicht konstruktiver Beweis sein, der Ihnen nicht sagt, was der Entscheider TM ist.
Babou
2
In Bezug auf Ihren Versuch ist es ein bisschen verwirrt. Die Größe von <M> entspricht genau der Größe eines Programmtextes. Es hängt nicht davon ab, wie viel Speicher das Programm tatsächlich verwendet. Für TM ist es tatsächlich die Beschreibung des TM in einem sehr abstrakten Sinne, so dass eine sehr kurze Beschreibung einem äußerst komplexen TM entsprechen kann. Die Größeksagt Ihnen nicht, wie viel Speicher verwendet wird. Argumente, die auf der Größe des Speichers basieren, sind komplexer (exponentielle Anzahl von Konfigurationen) und erfordern eine begrenzte Größe des Speichers, was hier nicht der Fall ist.
Babou
Ein allgemeiner konstruktiver Beweis muss kein berechenbares (!) Verfahren auslösen P. Zum Beispiel die kanonische Beweis ist in einer Art und Weise konstruktiv: table-Lookup, dh hartcodieren das Ergebnis für alle Eingänge inLk. Natürlich kann es keinen Algorithmus zum Erstellen dieser Tabelle geben (für unendlich allek) aus den von Ihnen genannten Gründen.
Raphael
6

Sie können Ihren Beweis mit der Busy-Beaver-Funktion "reparieren". LassenBk ist die maximale Anzahl von Schritten, die eine Turingmaschine mit Beschreibungsgröße höchstens hat kwird vor dem Anhalten ausgeführt, wenn die leere Eingabe gegeben wird. Wenn du weißtBk (oder auch nur eine Obergrenze Bkdas heißt, einige TkBk) dann können Sie die Halteprobleme für Turingmaschinen mit Beschreibungsgröße lösen k (und die leere Eingabe) durch Ausführen der angegebenen Maschine für bis zu Bk (oder Tk) Schritte. Wenn es zu diesem Zeitpunkt nicht anhält, wissen Sie, dass es niemals anhält.

Da das Stoppproblem nicht entscheidbar ist, wissen wir, dass die Funktion Bkkann nicht berechenbar sein. In der Tat keine berechenbare FunktionTk befriedigt TkBk für alle k. Mit anderen Worten, für jede berechenbare Funktionf(k)ist es der Fall, dass Bk>f(k) für unendlich viele k. Grob gesprochen,Bk wächst schneller als jede berechenbare Funktion.

In der Tat kann man das durch Diagonalisierung zeigen Bk wächst schneller als jede berechenbare Funktion: für jede berechenbare f(k) es gibt K so dass Bk>f(k)für alle kK. Dies wurde zuerst von Rado bewiesen .


Yuval Filmus
quelle
Die maximale Anzahl von Schritten zu finden, die ein TM der Größe ausführen kann, bevor es definitiv in eine Schleife geht, ist genau das, was ich beweisen wollte - ich wollte argumentieren, dass ein TM die Größe K hat, als die maximale Anzahl von Zuständen, die es haben kann codiert ist 2 ^ k und meine Logik war (und sag mir, wenn ich falsch liege) - wenn bei einem bestimmten Eingang ein TM mit m Zuständen mindestens m + 1 Züge macht (dh einen Zustand wiederholt), wird es definitiv eine Schleife.
Scifie
Und in Bezug auf Ihren Vorschlag, die maximale Anzahl von Schritten zu finden, die eine Turing-Maschine mit einer Beschreibungsgröße von höchstens k vor dem Anhalten ausführt, sollte nicht mehr als 2 ^ k sein, wie ich vorgeschlagen habe?
Scifie
Leider liegst du falsch. Was Sie schreiben, gilt für endliche Automaten, nicht jedoch für Turing-Maschinen, deren Status ein Band enthält. Nehmen Sie es als Übung, eine Turingmaschine mit zu bauenn gibt an, dass nach anhält 22nSchritte (grob).
Yuval Filmus
@ Yuval Filmus, das ist falsch - TMs Zustände hängen nicht mit dem Band zusammen. TMs-Zustände werden mit Q bezeichnet und es handelt sich um eine endliche Menge. Wie ist es mit seinem Band verbunden? Das Band dient zur Eingabemanipulation und gehört nicht zu den Zuständen eines TM.
Scifie
@scifie Der Status enthält alles, was Sie zur Beschreibung der aktuellen Situation des Geräts benötigen. Dazu gehören der eigentliche Status (worauf Sie sich beziehen), die Position des Kopfes und der Inhalt des Bandes.
Yuval Filmus
4

Der Hauptfehler besteht darin, dass Sie davon ausgehen, dass die Anzahl der Zustände, die ein TM hat, seine Laufzeit (vor der Beendigung) in irgendeiner Weise begrenzt. Das ist falsch.

In diesem Fall gibt es universelle Turing-Maschinen , also endlich beschriebene TMs, die jedes Verhalten zeigen können , von schnellem Beenden über einen beliebig langen Lauf bis hin zu Schleifen, wenn die richtige Eingabe erfolgt.

Aus technischer Sicht werden universelle TMs normalerweise so beschrieben, dass sie zwei Parameter verwenden, eine TM-Codierung und die Eingabe, um sie zu simulieren. Es ist einfach, sie zu einem Parameter zusammenzuführen, daher gibt es tatsächlich unäre universelle TMs.

Insbesondere ignorieren Sie die Eingabe des codierten TM, die beliebig groß (und verschlungen) sein kann. Der tatsächliche Zustand eines TM ist das Produkt aus Kontrollzustand und Bandinhalt, sodass ein einfaches kombinatorisches Argument, das auf der Anzahl der Kontrollzustände allein basiert, nicht ausreicht. Insbesondere befindet sich ein TM nicht in einer unausweichlichen Schleife, wenn es zum zweiten Mal einen Zustand besucht.

Raphael
quelle
Heh, es stellt sich heraus, dass meine Antwort hier nicht zutrifft, da wir nur eine feste (leere) Eingabe betrachten. Die Laufzeit ist in diesem Fall begrenzt, vgl. Yuvals Antwort.
Raphael