Wird jede rekursive Sprache von einer sterblichen Turingmaschine erkannt?

Wir sagen, dass eine Turing-Maschine tödlich ist, wenn $M$ $M$ für jede Startkonfiguration anhält (insbesondere können der Bandinhalt und der Anfangszustand beliebig sein). Wird jede rekursive Sprache von einer sterblichen Turing-Maschine erkannt? (dh wenn es ein TM gibt, das akzeptiert , gibt es auch ein tödliches TM, das akzeptiert ) $L$ $L$

computability Marcin Kotowski
quelle

Können Sie Verweise auf die Mortal Turing Machines geben? Danke :)

Tayfun Pay

Wie kommt es, dass der Ausgangszustand beliebig sein kann? Ist eine tödliche Turing-Maschine nicht nur ein TM, das bei jeder Eingabe anhält?

Philip White

@Marcin: Interessieren Sie sich für Maschinen, die bei allen Konfigurationen anhalten, auch bei unendlichen, oder nur für solche, die bei allen endlichen Konfigurationen anhalten ?

Joshua Grochow

Ich denke, er meint endliche Startkonfigurationen. Richtig?

Philip White

@Philip: Stellen Sie sich die Maschine in einem beliebigen Zustand und in einer beliebigen Konfiguration vor und führen Sie die Berechnung ab diesem Punkt nach den üblichen Regeln vorwärts aus.

Joshua Grochow

Antworten:

Hier sind zwei Ergebnisse, die in Charles E. Hughes "Unentscheidbarkeit der endlichen Konvergenz für Verkettungs-, Einfüge- und Bounded-Shuffle-Operatoren" zitiert wurden :

Satz 3 : Die Klasse der sterblichen Turingmaschinen ist genau die Klasse der Turingmaschinen mit konstanter Laufzeit.

st für alle Erstkonfigurationen , stoppt in nicht mehr als Schritten $ConstT = \{ M \mid \exists s$ $C$ $M$ $s$ $\}$

Ich denke also , dass wir folgendes ableiten: Da eine tödliche Turingmaschine , lassen die entsprechende konstante Zeit TM und seine Laufzeit sein. Die von über dem Alphabet erkannte Sprache ist genau: $M$ $M', s$ $M$ $\Sigma = \{0,1\}$

{x y ∣ | x | \leq s \land M^{'} akzeptiert x in nicht mehr als s Schritten, y \in {0, 1}^{*}}

$\{ xy \mid |x| \leq s \land M' \text{ accepts } x \text{ in no more than s steps}, y \in \{0,1\}^* \}$

Die Klasse der Sprachen, die von sterblichen Turing-Maschinen erkannt wird, ist also eine angemessene Untergruppe der Klasse der regulären Sprachen. Zum Beispiel können Sie mit jeder konstanten Zeit TM täuschen. $L = \{(0|1)^*1^*\}$

Interessant wird es, wenn wir versuchen, zu entscheiden, ob eine Turing-Maschine tödlich ist, weil wir mit willkürlichem (endlichem) Anfangsband und Zustand konfrontiert sind.

Satz 4 : Die Menge der sterblichen Turing-Maschinen ist rekursiv aufzählbar.

Marzio De Biasi
quelle

Ich denke, dort ist. Wir müssen für jedes L und M, das es akzeptiert, festlegen, dass alle seine Züge auf einem Band aufgezeichnet werden und nach jedem "Hauptschritt" überprüft wird, ob alle seine Schritte bis zu diesem Punkt wirklich gültig waren. Im Folgenden gebe ich eine Skizze darüber, wie eine solche Maschine hergestellt werden sollte (die einige kleinere Fehler enthalten könnte, aber die Hauptidee sollte in Ordnung sein).

Man bezeichne eine Maschine, die L durch T akzeptiert. Nun beschreiben wir M. Zuerst kopieren wir x auf ein separates Speicherband. Wann immer T sich dann bewegt, schreiben wir es nach x auf dieses Speicherband. Danach kopieren wir den gesamten Inhalt der Bänder von T in einige zusätzliche Arbeitsbänder und prüfen, ob T von der Startkonfiguration nach den auf dem Speicherband aufgezeichneten Schritten wirklich in seinen aktuellen Zustand gelangen würde. Wenn nicht, halten wir an. Wenn ja, fahren wir fort.

domotorp
quelle

Während ich meine Antwort schreibe, lese ich deine ... was das Gegenteil sagt :-) ... vielleicht interpretiere ich falsch, was eine Saite ist, die von einer sterblichen Turing-Maschine akzeptiert wird?

Marzio De Biasi

@MarzioDeBiasi: Der in diesem Papier berücksichtigte Begriff des Sterblichen erfordert einen Maschinenstopp in einer endlichen Anzahl von Schritten, selbst wenn er mit einer unendlichen Menge willkürlicher Daten auf seinem Band gestartet wird. Aber ich denke, Domotorps Konstruktion funktioniert höchstens für endliche Konfigurationen. Zum Beispiel wird in einer Konfiguration mit einer Eingabe unendlicher Länge das M von domotorp in einer unendlichen Folge des Kopierens der Eingabe unendlicher Länge auf das separate Speicherband abgefangen ...

Joshua Grochow

Ja, der Unterschied ist, dass ich angenommen habe, dass jeder Bandinhalt endlich ist und wir wissen, wo die Grenzen liegen. Ansonsten sind sterbliche TMs nur konstant, wie Sie schreiben.

Domotorp