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

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

L_{k} = H_{T M, ε} \cap Σ^{k}

$L_k= H_{\mathrm{TM},\varepsilon}\cap \Sigma^k$

H_{T M, ε} = {⟨ M ⟩ ∣ M is a TM that halts on an empty input}

$H_{\mathrm{TM},\varepsilon}=\{\langle M\rangle\mid M \text{ 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)? $L_k$ $k$ $2^k$ $2^k$ $L_k$

computability turing-machines proof-techniques scifie
quelle

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.

H_{T M, ε}

$H_{\mathrm{TM},\varepsilon}$

H_{T M, ε}

$H_{\mathrm{TM},\varepsilon}$

Raphael

@ Raphael: ist die Vereinigung der Mengen

H_{T M, ϵ}

$H_{\mathrm{TM},\epsilon}$

{⟨ M ⟩ ∣ M is aTM that halts within t steps on ϵ input}

$\{\langle M\rangle \mid M \text{ is aTM that halts within } t \text{ steps on $\epsilon$ input}\}$ für positive ganze Zahlen

t

$t$ . Deshalb

H_{T M, ϵ}

$H_{\mathrm{TM},\epsilon}$ ist "eine rekursiv aufzählbare Vereinigung entscheidbarer Mengen".

@ RickyDemer Stimmt, danke. Mein Argument funktioniert nur für Nicht-Halbentscheidbarkeit (oder?).

Raphael

Antworten:

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

Sie haben Recht damit $L_k$ ist rekursiv, weil es eine Teilmenge der endlichen Menge ist $\Sigma^k$ es ist auch endlich.

Sie möchten lieber einen Entscheider TM für finden $L_k$ und 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 $M_k$ für die Sprache $L_k$ , 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 $k$ Sie haben eine Prozedur $\mathcal P(k)$ einen solchen Entscheider zu finden $M_k$ für die Sprache $L_k$ (anstatt nur zu beweisen, dass es existiert). Dann gegeben jede Turingmaschine $M$ dann gibt es eine ganze Zahl $k'$ so dass $|\langle M\rangle|=k'$ , damit $\langle M\rangle\in \Sigma^{k'}$ . Dann können Sie das Verfahren anwenden $\mathcal P$ um einen Entscheider TM zu finden $M_{k'}$ das kann bestimmen, ob $\langle M\rangle\in L_{k'}$ . So haben Sie eine Möglichkeit zu entscheiden, ob das TM $M$ wird bei leerer Eingabe angehalten. Und das funktioniert für jedes TM $M$ . Dies ist jedoch nicht möglich, da nicht entschieden werden kann, ob ein bestimmtes TM vorliegt $M$ wird bei leerer Eingabe angehalten.

Also das Verfahren $\mathcal P$ kann nicht existieren.

Da suchen Sie nach einem allgemeinen Weg, um den Entscheider TM zu finden $M_{k'}$ , können Sie nicht erfolgreich sein, weil diese Methode genau eine Prozedur wie wäre $\mathcal 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

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 funktioniert

k

$k$ wird notwendigerweise ein nicht konstruktiver Beweis sein, der Ihnen nicht sagt, was der Entscheider TM ist.

Babou

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öße

k

$k$ sagt 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

$\mathcal{P}$ . Zum Beispiel die kanonische Beweis ist in einer Art und Weise konstruktiv: table-Lookup, dh hartcodieren das Ergebnis für alle Eingänge in

L_{k}

$L_k$ . Natürlich kann es keinen Algorithmus zum Erstellen dieser Tabelle geben (für unendlich alle

k

$k$ ) aus den von Ihnen genannten Gründen.

Raphael

Sie können Ihren Beweis mit der Busy-Beaver-Funktion "reparieren". Lassen $B_k$ ist die maximale Anzahl von Schritten, die eine Turingmaschine mit Beschreibungsgröße höchstens hat $k$ wird vor dem Anhalten ausgeführt, wenn die leere Eingabe gegeben wird. Wenn du weißt $B_k$ (oder auch nur eine Obergrenze $B_k$ das heißt, einige $T_k \geq B_k$ ) 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 $B_k$ (oder $T_k$ ) 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 $B_k$ kann nicht berechenbar sein. In der Tat keine berechenbare Funktion $T_k$ befriedigt $T_k \geq B_k$ für alle $k$ . Mit anderen Worten, für jede berechenbare Funktion $f(k)$ ist es der Fall, dass $B_k > f(k)$ für unendlich viele $k$ . Grob gesprochen, $B_k$ wächst schneller als jede berechenbare Funktion.

In der Tat kann man das durch Diagonalisierung zeigen $B_k$ wächst schneller als jede berechenbare Funktion: für jede berechenbare $f(k)$ es gibt $K$ so dass $B_k > f(k)$ für alle $k \geq K$ . 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 bauen

n

$n$ gibt an, dass nach anhält

2^{2^{n}}

$2^{2^n}$ Schritte (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

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

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

Antworten:

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

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