Terminierung einer Turingmaschine
Wenn eine Turingmaschine A für eine gegebene Eingabefolge w nicht terminiert, spricht man von der Undefiniertheit der Eingabefolge w bezüglich A. Die Turingmaschine terminiert genau dann, wenn in jedem Zustand während des Arbeitsprozesses mindestens eine Regel der Übergangsrelation Δ anwendbar ist und die Turingmaschine in einem Endzustand hält.
Ein Beispiel
Gegeben sei die Turingmaschine A = (Q, Σ, Γ, q0, Δ, F) mit folgender Übergangsrelation Δ:
(q0, b, a, r, q1) | (q1, b, b, r, q1) | (q2, a, a, r, q2) | (q3, b, a, n, qe) | (q4, a, b, n, qe) |
(q0, a, b, r, q2) | (q1, #, #, l, q3) | (q2, #, #, l, q4) |
Für die Eingabefolgen wx, x ∈ {1,2,3,4} soll geprüft werden, ob die gegebene Turingmaschine A terminiert.
Terminierung einer Turingmaschine