Sei . Ich muss entscheiden, ob F entscheidbar oder rekursiv aufzählbar ist. Ich denke, es ist entscheidend, aber ich weiß nicht, wie ich es beweisen soll.
Meine Gedanken
Dieser "50 Schritte" Teil dreht sofort das R- Zeichen für mich. Wenn es für eine bestimmte Eingabe wäre, wäre es entscheidbar. Hier ist es jedoch für jede Eingabe. Wenn ich es auf unendliche Eingaben überprüfe, denke ich, dass das Problem co-RE ist , dh, seine Ergänzung ist akzeptabel.
Vielleicht kann ich die Konfigurationen überprüfen und feststellen, dass alle Konfigurationen nach 50 Schritten nicht zum Akzeptieren führen. Wie mache ich das?
Wenn in nicht mehr als 50 Schritten anhält, sind die Positionen, die auf dem normalerweise unendlichen Band erreichen kann, begrenzt. Somit kann das unendliche Band durch ein endliches simuliert werden. Dies bedeutet, dass das Band von einem endlichen Automaten simuliert werden kann. Daraus folgt, dass eine Turingmaschine , die in nicht mehr als 50 Schritten stoppt, einem endlichen Automaten ähnlich ist .M M M 'M M M M′
Sei die Menge der Zustände von , die Menge der akzeptierenden Zustände und das Alphabet. Dann bauen wir die Menge der Zustände von wie folgt auf: wobei die Position des Lese- / Schreibkopfes über dem Band ist. Wir können die Position auf da die Anzahl der zulässigen Rechenschritte die Anzahl der erreichbaren Positionen begrenzt.M F ⊂ Q Γ Q ' M ' Q ' = { ⟨ n , q , s , p , a ⟩Q. M F⊂ Q Γ Q.′ M′ p { - 50 , . . . , 50 }Q′={⟨n,q,s,p,a⟩|n∈{0,...,50}q∈Q,s∈Γ,p∈{−50,...,50},a≡q∈F} p {−50,...,50}
Ein Zustand des endlichen Automaten bedeutet dann, dass wir uns im Zustand des ursprünglichen Automaten befinden, mit auf dem Band an der Position wo sich auch der Lese- / Schreibkopf befindet positioniert ist, nach dem ten Rechenschritt. Der Zustand ist ein akzeptierender Zustand, wenn .M ' q s p n a ≡ t r u e⟨n,q,s,p,a⟩ M′ q s p n a≡true
Das Transformieren des Übergangsverhältnisses einer Betonwälzmaschine ist etwas aufwändiger, aber für die ursprüngliche Frage nicht erforderlich, da es ausreicht, um zu zeigen, dass der Zustandsraum endlich ist (und wir daher nur jeden Eingang mit einer Länge von höchstens 50 testen können Symbole auf jedem solchen Automaten). Die Idee ist, eine neue Übergangsrelation zu erstellen, die von einem Zustand in einen Zustand in geht der te Rechenschritt, wenn der Übergang in der ursprünglichen Übergangsrelation war.⟨ n + 1 , q ' , s ' , p ' , a ' ⟩ n ⟨ q , s , p ⟩ → ⟨ q ' , s ' , p ' ⟩⟨n,q,s,p,a⟩ ⟨n+1,q′,s′,p′,a′⟩ n ⟨q,s,p⟩→⟨q′,s′,p′⟩
quelle