maquina de turing

Tema 2:
MÁQUINAS DE TURING

Definición
Intuitiva:
Construcción lógica → Dispositivo mecánico: cinta infinita, dividida en
celdas, con un cabezal de lectura/escritura que se mueve sobre dicha
cinta, avanzando una celda cada vez.
Analogía: humano con un papel cuadriculado infinito, con lápiz y goma,
que puede escribir/leer un símbolo en cada cuadrícula cada vez.

Mov. Izda.

/25))
QCONTROL
DE
ESTADOS

CINTA
Mov. Dcha.

Cabeza lectura/escritura

1

Definición
Formal:
Séptupla: (Γ, Σ, b, Q, qo, f, F)
donde:
Γ: alfabeto de símbolos de cinta
Σ ⊂ Γ : alfabeto de símbolos de entrada
b ∈ Γ, b ∉ Σ : símbolo blanco. Indica que la celda está vacía.
Q: conjunto de estados (finito).
qo ∈ Q: estado inicial
F ⊂ Q: conjunto de estados finales
f: función de transición,correspondencia de Q x Γ → Q x Γ x {I,D,P}

Definición
Operaciones que realiza:
a) Estando en un estado p, lee un símbolo en la celda sobre la que se
encuentra la cabeza.
b) Pasa a un nuevo estado
c) Escribe un nuevo símbolo en la cinta (que reemplaza al
anteriormente leído, salvo que se escriba el mismo)
d) Mueve la cabeza de L/E a izda., dcha o se para.

2

DefiniciónCaracterísticas de la Cinta:
•

cinta infinita

•

puede contener un carácter por celda

•

se puede leer de ella

•

se puede escribir en ella

•

se considera con ∞ blancos a la derecha e izquierda

•

se puede desplazar a izda, dcha, una celda cada vez, o parar

Esquema MT
CINTA

... 1 # 1 0 0 1 # 0 1
Posición de la
cabeza lectora

qo

Símbolos del
alfabeto de cinta, ΓEstado inicial

3

Función de Transición
f: función de transición, en una tabla de doble entrada
Q x Γ → Q x Γ x {I,D,P}
Γ→
↓Q
Estado, símbolo, movimiento

Algunas celdas de la tabla vacías: transiciones no posibles.

Ejemplo
MT que duplica el número de 1´s que hay en la cinta
MT =({1,x}, b, {p,q,r,s}, p, f, {s})
Γ→
1
↓Q
qxD
→p
q
r

q1D

x

b

pxI

rbD

qxDpxI

r1D

sbP

s

4

Ejemplo. Funcionamiento
Estado P: cuando encuentra un 1, lo cambia por x y pasa a Q
* Mientras encuentra x, los ignora, sigue en P e izquierda. f(p,x) → (p,x,I)
∗ Cuando encuentra 1, escribe x, pasa a Q y derecha. f(p,1) → (q,x,D)
∗ Cuando encuentra un b, lo ignora, pasa a r y derecha. f(p,b) → (r,b,D)
Estado Q: añade una x a la cadena de entrada, sobre elprimer b que aparece a la
derecha de la misma.
* Mientras encuentra x y 1, los ignora, sigue en Q y derecha.
f(q,x) → (q,x,D)
f(q,1) → (q,1,D)
∗ Cuando encuentra un b, escribe x, pasa a p e izquierda. f(q,b) → (p,x,I)
Estado R: se encarga de transformar todas las x en 1’s, cuando ya lo ha hecho, el
problema ha quedado resuelto y la MT pasa la estado final y se para.
*Cambia los x’s queencuentra por 1’s, sigue en R y derecha.
f(r,x) → (r,1,D)
∗ Cuando encuentra un b, lo deja, pasa al estado final, S y para la MT.
f(r,b) → (s,b,P)

Restricciones a la MT
La MT definida anteriormente es un MT genérica. Se
pueden definir, sin embargo, MT con restricciones.
Estas restricciones:
• No afectan a la potencia de cálculo
• Se aplican a:
→ alfabeto cinta: MT binaria
→ estructura de lacinta: MT limitada
→ movimientos

5

Restricciones a la MT.
MT con alfabeto binario
• Teorema:
dada una MT genérica (las vistas hasta ahora), existe
una MT equivalente a ella, con alfabeto binario.

Restricciones a la MT.
MT con alfabeto binario
• Cada símbolo ∈Γ en una MT sin restricciones, se representará mediante
un número binario de n cifras.
• En un instante t la MT estará enun estado qi, lee un símbolo aj, pasa a qk,
escribe a1 y realiza un movimiento U ∈ {I, D, P}.
• En la MT(2:

f(qi, aj) → (qk, a1, U)
∗ Los símbolos tendrán una codificación binaria: b(aj) y b(a1)
∗ La transición podrá verse de la forma:
0

0

qio
1

qi

0
1

qio0
qio1
qi10

qi1
1

(qi,b(aj)) → (qij, b(aj), U)
El estado qij recuerda que partió
de qi y ha leído la...