Maquinas turing

M´quinas de Turing
a

En este cap´
ıtulo se presenta la M´quina de Turing (MT) que es el modelo
a
de aut´mata con m´xima capacidad computacional: la unidad de control
o
a
puede desplazarse a izquierda o a derecha y sobre-escribir s´
ımbolos en la
cinta de entrada.

6.1.

M´quinas de Turing como aceptadoras de
a
lenguajes

Una m´quina de Turing (MT), M = (Q, q0 , F, Σ, Γ, ¯, δ),consta de siete
a
b
componentes:

1. Q es el conjunto (finito) de estados.

2. q0 ∈ Q es el estado inicial.

3. F es el conjunto de estados finales o de aceptaci´n, ∅ = F ⊆ Q.
o

Σ es el alfabeto de entrada.

4.

5.

Γ es el alfabeto de cinta, que incluye a Σ, es decir, Σ ⊆ Γ.

6. b ∈ Γ es el s´
¯
ımbolo “blanco” (el s´
ımbolo ¯ no puede hacer parte del
b
alfabeto deentrada Σ).

7. δ es la funci´n de transici´n de la m´quina:
o
o
a

δ : Q × Γ −→ Q × Γ × {←, →}

1

´
CAP´
ITULO 6. MAQUINAS DE TURING

δ es una funci´n parcial, es decir, puede no estar definida en algunos
o
elementos del dominio. La flecha ← denota desplazamiento a izquierda
mientras que → denota desplazamiento a la derecha. La transici´n
o

δ(q, a) = (p, b, D)

significa: estandoen el estado q, escaneando el s´
ımbolo a, la unidad
de control borra a, escribe b y se mueve en el estado p, ya sea a la
izquierda (si el desplazamiento D es ←) o a la derecha (si D es →).

Una m´quina de Turing M procesa cadenas de entrada w ∈ Σ∗ colocadas
a
sobre una cinta infinita en ambas direcciones. Para procesar una cadena de
entrada w, la unidad de control de M est´ en el estadoinicial q0 escaneando
a
el primer s´
ımbolo de w. Las dem´s celdas o casillas de la cinta contienen el
a
s´
ımbolo blanco b.
¯

o
Descripci´n o configuraci´n instant´nea. Es una expresi´n de la forma
o
o
a

a1 a2 · · · ai−1 qai · · · an

donde los s´
ımbolos a1 , . . . , an pertenecen al alfabeto de cinta Γ y q ∈ Q.
Esta expresi´n representa el estatus actual del c´mputo:
o
o···

a1

a2

ai−1

···

ai

···

an

q

Es decir, la descripci´n instant´nea a1 a2 · · · ai−1 qai · · · an indica que la uni-
o
a
dad de control de M est´ en el estado q escaneando el s´
a
ımbolo ai . Se supone
que las casillas en las que no aparecen aes contienen el s´
ımbolo blanco, b.
¯
Ejemplos concretos de descripciones instant´neas son:
a

aabq2 baaa
q5 ababbaab¯¯aabq0 bba
bb

La configuraci´n o descripci´n instant´nea inicial, o simplemente configu-
o
o
a
raci´n inicial, es
o
q0 w

´
6.1. MAQUINAS DE TURING COMO ACEPTADORAS DE LENGUAJES

siendo w la cadena de entrada, la cual se coloca en cualquier parte de la
cinta de entrada.

Paso computacional. El paso de una descripci´n instant´nea a otra, por
o
a
medio de una transici´n definidapor δ, se denomina un paso computacional
o
y se denota por
u1 qu2 ⊣ v1 pv2 .

Aqu´ u1 , u2 , v1 , v2 ∈ Γ∗ y p, q ∈ Q. Un ejemplo concreto es
ı

abbaq2 ba ⊣ abbq1 aca

en la cual la m´quina utiliz´ la transici´n δ(q2 , b) = (q1 , c, ←).
a
o
o

La notaci´n
o

significa que M puede pasar de la descripci´n instant´nea u1 qu2 a la des-
o
a
cripci´n instant´nea v1 pv2 en cero, uno om´s pasos computacionales.
o
a
a

C´mputos especiales. Durante el c´mputo o procesamiento de una ca-
o
o
dena de entrada hay dos situaciones especiales que se pueden presentar:

1.

El c´mputo termina porque en determinado momento no hay transi-
o
ci´n definida.
o

2.

El c´mputo no termina; esto es lo que se denomina un “bucle infinito”.
o
Esta situaci´n se representa con lanotaci´n
o
o

∗

u1 qu2 ⊣ v1 pv2

∗

u1 qu2 ⊣ ∞

la cual indica que el c´mputo que se inicia en la descripci´n ins-
o
o
tant´nea u1 qu2 no se detiene nunca.
a

Un detalle para tener en cuenta es que las transiciones con s´
ımbolo b,
¯
δ(q, ¯) = (p, s, D), no son las mismas transiciones λ usadas para aut´ma-
b
o
tas en cap´
ıtulos anteriores. Una transici´n λ en un...