Máquina de Turing

Una máquina de Turing T sobre Σ es una tripla T = (K, q₀, I) donde K es un conjunto finito de estados, q₀ ∈ K es el estado inicial, e I es una función parcial I : K × (Σ ∪ {#}) → (Σ ∪ {#}) × {R, L} × K.

Instrucción

Una instrucción es una quíntupla (qᵢ, s, t, D, qⱼ) tal que:
· qᵢ, qⱼ ∈ K (estados)
· s, t ∈ Σ ∪ {#} (símbolos)
· D ∈ {R, L} (dirección)
· I(qᵢ, s) = (t, D, qⱼ)

Combinación final

Una pareja (qᵢ, s) es una combinación final si no aparece al comienzo de ninguna instrucción. La máquina se detiene al leer s en estado qᵢ.

De Castro Korgi §6.1 · slides §1–5

Polynomial:

Process:

Result: