Una Máquina de Turing (MT)

Una Máquina de Turing (MT)

M = (Q, ∑, Г, q0, T,B, δ)

Máquinas de Turing

Dónde:

1. Q es un conjunto finito de estados.

2. ∑ es el alfabeto de entrada.

3. Г es el alfabeto de la cinta, que incluye a

4. q0 ∈ Q es el estado inicial.

5. B ∈ Γ es el símbolo blanco (el símbolo B no puede hacer parte de ∑) aparece en todas las casillas excepto en aquellas que contienen los símbolos de entrada.

6. T ⊆ Q conjunto de estados finales.

7. δ es la función de transición tal que:

δ : Q × Γ → Q × Γ × {I , D}

δ(q, X ) = (p, Y, {I , D})

δ es una función parcial, es decir, No puede estar definida en algunos elementos del dominio.

Una cadena de entrada w es aceptada por una MT M si el computo que se indica la configuracion inicial q0w termina en una configuracion instant´anea w1pw2, p es un estado de aceptacion, en la cual M se detiene completamente. El lenguaje L(M ) aceptado por una MT M se define como: L(M ) = {w ∈ Σ : q0w `∗ w1pw2, p ∈ T }

M se para en w1pw2 Si la cadena de entra- da en una m´aquina M pertenece a L(M ), la m´aquina M siempre se detiene.

...