Zurück

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.

... # # # # # # ... Zustand q₀ wₓ A terminiert A terminiert nicht Bei welchen Eingabefolgen wₓ terminiert die Turingmaschine? Ordne die vier Eingabefolgen per Drag&Drop den Boxen „A terminiert“ bzw. „A terminiert nicht“ richtig zu. w₁ = ababa w₂ = aaaaa w₃ = bbbbb w₄ = aaaab
Terminierung einer Turingmaschine