Festlegen des Satzes aller Turing-Maschinen, die höchstens anhalten

8

Lassen L={<M>|M hält bei jedem Eingang an x höchstens in 200|x| Schritte }.

Ist Lentscheidbar? Erkennbar?

Angesichts dieser Mitgliedschaft in L behauptet etwas über MDas Verhalten auf einer unendlichen Anzahl von Saiten scheint mir äußerst unwahrscheinlich LKönnte beides sein. Ich habe gezeigt, dass Co-L ist Turing-erkennbar (glaube ich): Sie können einen Enumerator erstellen, der jeden testet M1,M2,, für jedes s1,s2, und emittiert M wenn es einige nicht akzeptiert s höchstens in 200|x| Schritte.

Da co-L ist auch erkennbar List nicht erkennbar oder entscheidbar. Das kann ich mir nicht vorstellenList entscheidbar. Es kann jedoch definitiv nicht auf das Stoppproblem reduziert werden, noch kann der Satz von Rice darauf angewendet werden (da die fragliche Qualität die Qualität des Stoppens in einer bestimmten Anzahl von Schritten ist, können wir uns nicht entscheiden, ob wir entscheiden können, ob es sich um ein anderes handelt beliebige Eigenschaften).

Es scheint mir, dass der beste Weg ist, das zu zeigen LLassen Sie mich etwas erkennen, das nicht wiederzuerkennen ist, da die einzigen Probleme, die es löst, solche sind, bei denen ich über unendliche Sätze von Zeichenfolgen laufen muss. Aber ich kann mir nicht vorstellen, was das sein könnte. Ich dachte, dass Co-HALT vielleicht funktionieren würde, aber ich kann nie beweisen, dass ein TM bei einer Eingabe niemals stehen bleibt.

Ich stecke fest. In welche Richtung soll ich gehen?

Patrick Collins
quelle
& frage mich, ob es eine Möglichkeit gibt, dies mit Standard-Sprachkursen in Verbindung zu bringen, z. B. CSLs usw.?
vzn

Antworten:

6

Die Sprache ist tatsächlich entscheidbar, aber der Beweis ist ziemlich kompliziert und verwendet Argumente mit sich kreuzenden Sequenzen. Weitere Informationen finden Sie in diesem Dokument.

Wenn Sie sich ändern 200|x| zu einer schneller wachsenden Funktion, wie z |x|log|x| (plus eine Konstante), dann wird die Sprache durch Standardreduktionsargumente unentscheidbar.

Shaull
quelle
2

Diese Antwort ist falsch. Ich lasse es hier, da diese Art von Argument der natürliche Weg ist und für schneller wachsende Funktionen funktioniert, wie in Shaulls Antwort erwähnt.

Hinweis: Lassen Sie Msei eine Maschine ohne Eingabe. Definieren Sie eine neue MaschineM wie folgt: bei Eingabe x, M simuliert M zum f(|x|) Schritte, wo f(t) ist eine Funktion, die gegen unendlich tendiert, so dass die Simulation weniger als dauert 200tSchritte. WennM hält dann immer an Mwechselt zu einer Endlosschleife. Wann istML?

Yuval Filmus
quelle
Sie können die Simulation nicht unbedingt rechtzeitig durchführen f(t). Insbesondere wissen wir nicht, wie man mit linearem Overhead simuliert.
Shaull