La mquina de Turing

Jos M. Sempere Departamento de Sistemas Informticos y Computacin Universidad Politcnica de Valencia

David Hilbert (1862, Rusia 1943, Alemania)

Matemtico que aport diversos resultados de carcter fundamental (i.e. espacios de Hilbert) En 1900 durante el Segundo Congreso Internacional de las Matemticas en Paris formul su famosa lista de 23 problemas esenciales para el progreso en las matemticas. Destacamos el problema nmero 23 que fue un detonante en el progreso en las ciencias de la computacin. Podemos expresarlo como sigue

Existe alguna formalizacin efectiva de las matemticas ? Es decir, existe algn sistema que permita expresar cualquier proposicin matemtica en forma simblica y que habilite su demostracin mediante un puro clculo ?

Kurt Gdel (1906, Aust.Hungria 1978, USA)

Matemtico. Su principal rea de estudio se centra en los sistemas axiomticos de las matemticas influenciado por el trabajo de Russell En 1932 publica su resultado ms notable: El Teorema de Incompletitud En cualquier sistema axiomtico de las matemticas existen proposiciones que no pueden demostrarse como ciertas o falsas

Alonzo Church (1903, USA 1995,USA)

Matemtico. Su principal rea de estudio se centra en la lgica matemtica, la teora de la recursin y la informtica terica (theoretical computer science). En 1930 crea el -clculo que fundamenta algunos de los paradigmas de programacin actuales. Fue supervisor de doctorado de Kleene y Turing. Su resultado ms celebrado es el conocido como Teorema de Church (1936): No existe un procedimiento de decisin para el clculo proposicional completo

Stephen Kleene (1909, USA 1994, USA)

Matemtico. Su principal rea de estudio se centra en la teora de los algoritmos y las funciones recursivas. Propone una definicin sencilla y fundamental de las funciones recursivas que ayudaron a una mejor comprensin de los sistemas axiomticos de primer orden de Gdel. Sus resultados ms notables permitieron establecer qu funciones podan ser computables y tambin permitieron establecer grados en las funciones no computables (i.e. la Jerarqua Aritmtica)

Emil Post (1897, Polonia 1954, USA)

Matemtico. Demostr la completitud y consistencia del cculo proposicional propuesto por Russell y Whitehead en sus Principia Mathematica. Post descubri con antelacin algunos de los resultados que ms tarde publicaran Gdel, Church y Turing. En 1936 propone la mquina de Post que incluye la nocin de programa en un autmata. En 1947 demuestra como irresoluble el problema de palabras de un semigrupo propuesto por Thue en 1914 dando lugar al famoso Problema de la Correspondencia de Post.

Alan Turing (1912, Inglaterra 1954, Inglaterra)

Matemtico. Sus reas de trabajo son mltiples e incluyen los estudios de algunos resultados de Russell y Gdel en relacin con el problema 23 de Hilbert. En 1936 publica su famoso trabajo sobre decidibilidad en el que propone su ms notable modelo matemtico: la mquina de Turing Durante la II Guerra Mundial, Turing trabaj en Bletchley Park para la Escuela Estatal de Cdigos y Cifras . Su trabajo ms notable durante esta poca fue el criptoanlisis de los cdigos de la mquina Enigma alemana. Dise una mquina que resolvi con xito tal problema: la bomba de Turing En 1950 public su trabajo sobre Mquinas que Computan e Inteligencia, proponiendo el famoso test de Turing para discernir si un computador puede llegar a ser inteligente.

La mquina de Turing: El modelo determinista (I) Turing:

a1 a2 a3 a4 a5 a6 B B

cinta de lectura/escritura cabeza de cinta control finito q

Un movimiento de la mquina depende del estado del control finito y del smbolo analizado por la cabeza de cinta Un movimiento de la mquina implica: (a) Cambiar el estado del control finito (b) Escribir un smbolo en la celda analizada (c) Mover la cabeza de cinta una celda a la izda. o a la dcha.

La mquina de Turing: El modelo determinista (II) Turing: M = (Q, , , , q0, B, F) : Q Q {L, R}

descripcin instantnea

a1 a2 a3 a4

a5 a6 B B

q = a1 a2 a3 q a4 a5 a6

descripcin instantnea

a1 a2 B a4 a5 a6 B B

q = a1 a2 B a4 a5 a6 q B

a1 a2 B a4 a5 a6 B B

q = q a1 a2 B a4 a5 a6

transiciones entre descripciones instantneas a1 a2 B a4 a5 a6 B B

q
a1 a2 B Y a5

D1 = a1 a2 B q a4 a5 a6
a6 B B

p
a1 a2 B Y a5 a6

D2 = a1 a2 B Y p a5 a6
B B

p D1 D1 M M

D3 = a1 a2 p B Y a5 a6 D2 sii (q, a4) = (p, Y, R) D3 sii (q, a4) = (p, Y, L)

transiciones entre descripciones instantneas

* M es la clausura reflexiva y transitiva de la relacin M Di * Di+k sii M (a) Di = Di+k (b) Di+1 Di+2 ... Di+k-1 1k

Di M Di+1 M Di+2 M ... M Di+k-1 M Di+k

Condicin de parada

Una mquina de Turing M estar en movimiento siempre que pueda aplicar una transicin de la funcin o no realice ningn movimiento a la izquierda del lmite de la cinta. Asumimos que en la funcin nunca se definen movimientos a partir de estados finales.
Descripcin instantnea inicial

w
w1 w2 w3 ... ...

q0 w
wn B B

q0
Lenguaje aceptado por la mquina M

M = (Q, , , , q0, B, F)

L(M) = { w * : q0 w

* q , q F, * } M

Ejemplo 1

L(M) = { 0n1n : n 1 }

M = ({q0, q1, q2, q3, q4}, {0, 1}, {0, 1, X, Y, B}, , q0, B, {q4})

0 q0 q1 q2 q3 q4 (q1,X,R)

1 -------

X ------------(q0,X,R) -------------

Y (q3,Y,R) (q1,Y,R) (q2,Y,L) (q3,Y,R) -------

B ------------------(q4,B,R) -------

(q1,0,R) (q2,Y,L) (q2,0,L) -------------------------------

La mquina de Turing como calculadora de funciones Trabajamos con funciones parciales enteras f : Zn Zm
Codificacin de los valores de dominio y rango

Dada la tupla de valores enteros positivos (x1, x2, ..., xn) Definimos la funcin de codificacin binaria cod(x1, x2, ..., xn) = 0x1 1 0x21 ... 1 0xn cod(1,2,3) = 01001000 cod(2,0,3) = 0011000
M como calculadora de funciones

cod(0,3) = 1000 cod(0,0) = 1

M = (Q, {0,1}, , , q0, B, ) M calcula la funcin f : Zn Zm sii M para tras la computacin q0 cod(x1, x2, ..., xn) * q = cod(f(x1, x2, ..., xn)) M

Ejemplo 2

m n si m n resta(m, n) =

0 si m < n M = ({q0, q1, q2, q3, q4, q5, q6}, {0, 1}, {0, 1, B}, , q0, B, )
0 q0 q1 q2 q3 q4 q5 q6 (q1,B,R) (q1,0,R) (q3,1,L) (q3,0,L) (q4,0,L) (q5,B,R) ------1 (q5,B,R) (q2,1,R) (q2,1,R) (q3,1,L) (q4,B,L) (q5,B,R) ------B ------------(q4,B,L) (q0,B,R) (q6,0,R) (q6,B,R) -------

Lenguajes y funciones computables Un lenguaje diremos que es

recursivamente enumerable si existe una mquina de Turing M tal que L(M) = L. Define la clase Lr.e. recursivo si existe una mquina de Turing M tal que L(M)=L y M para ante cualquier entrada. Define la clase Lrec Lrec Lr.e.

Una funcin es computable si puede ser calculada por una mquina de Turing.
El conjunto de funciones computables coincide con el de las funciones recursivas Si una funcin es computable parcial, la mquina que la calcula puede no parar, o parar con una salida indefinida, para aquellos valores en los que la funcin no est definida.

Tcnicas de construccin de mquinas de Turing (I)

Almacenamiento en el control finito Se dota al control finito de una memoria finita capaz de almacenar informacin limitada. (a) Almacenamiento de una tupla de k estados estado [q1, q2, ..., qk] k q0 = [q0, q0, ..., q0] (b) Almacenamiento de una tupla de k smbolos

M = (Q , , , , q0, B, F)

M = (Q k, , , , q0, B, F) estado [qi, a1, ..., ak]

q0 = [q0, B, ..., B] (c) Almacenamiento de otra informacin ltimo movimiento aplicado, primer smbolo de la cadena de entrada, etc.

Tcnicas de construccin de mquinas de Turing (II)

Pistas mltiples (multipistas) La cinta almacena en cada celda un vector k dimensional de smbolos a los que se accede simultneamente.

M = (Q, Bk-1, k, , q0, B, F)

w1 B B w2 B B ------wn B B B B B pista 1 pista 2 pista k

q0

: Q k Q k {L, R} cadena inicial de entrada w = [w1,B, ..., B] [w2, B, ..., B] ... [wn, B, ..., B]
B = [B, B, ..., B]

Tcnicas de construccin de mquinas de Turing (III)

Subrutinas Una subrutina es un subconjunto de movimientos de la funcin que se puede utilizar igual que en algunos lenguajes de programacin. Paso de control Se utiliza almacenamiento en el control finito [qact, qin, qfin] Paso de variables Se utiliza almacenamiento en control finito o bien multipistas Recursividad Una subrutina puede llamarse a s misma La pila de recursividad puede habilitarse en una pista

Modificaciones equivalentes al modelo determinista bsico (I)

Cinta infinita en ambos sentidos w B B w1 w2 ... wn B

q0 M = (Q, , , , q0, B, F) Configuracin instantnea q es el contenido de cinta desde el smbolo no blanco ms a la izquierda hasta el smbolo no blanco ms a la derecha Carga inicial q0w w se carga en cualquier porcin de la cinta con la cabeza situada en su smbolo ms a la izquierda

Teorema Para cualquier mquina de Turing M1 con cinta infinita en ambos sentidos existe otra equivalente M2 con cinta limitada por la izquierda w B B w1 w2 ... wn B M1

q0
w1 w2 B ... ... wn B B B

M1 = (Q, , , 1, q0, B, F)
pista superior U pista inferior D

M2

q0

M2 = (Q{U,D} {q1}, B, ({}), 2, q1, [B,B], F{U,D}) 2(q1, [x,B]) = ([qi,U], [y, ], R) sii 1(q0, x) = (qi, y, R) 2(q1, [x,B]) = ([qi,D], [y, ], R) sii 1(q0, x) = (qi, y, L)

Modificaciones equivalentes al modelo determinista bsico (II)

Mquina multicinta B B w1 w2 ... wn B cinta 1

x1

x2

...

xm

cinta 2

y1

y2

...

yj

cinta k

q M = (Q, , , , q0, B, F) : Q k Q k {L, R}k

Mquina multicinta Un movimiento de la mquina multicinta depende del estado del control finito y de los smbolos analizados por cada cabeza de cada cinta Un movimiento de la mquina multicinta implica: (a) Cambiar el estado del control finito (b) Escribir un smbolo en cada una de las celdas analizadas (c) Mover cada cabeza de cinta una celda a la izda. o a la dcha. de forma independiente descripcin instantnea

1 q 1 # 2 q 2 # ... # k q k
carga inicial q0w# Bq0B# ... #Bq0B w se carga en la cinta 1 y el contenido del resto de las cintas es blanco Para el clculo de funciones, el valor de la funcin se almacena en la cinta 1

Teorema Para cualquier mquina de Turing M1 con k cintas existe otra equivalente M2 con una sola cinta B B B w1 w2 B x2 B y2 B ... ... ... ... ... ... B B B wn B xm-1 B yj-2 B w1 x1 y1 B B xm w2 x2 y2 ... ... ... wn xm yj B B B cinta 1 (dos pistas) cinta 2 (dos pistas) cinta 1 cinta 2

cinta k
M1 = (Q, , , 1, q0, B, F)

~
x1 B y1 B

~
yj-1 B yj

cinta k (dos pistas)

M2

Teorema Para cualquier mquina de Turing M1 con k cintas existe otra equivalente M2 con una sola cinta

M1 = (Q, , , 1, q0, B, F) M2 = (Qk{0, ..., k}, B2k-1, ( {~})2k, 2, q1, B, F k0 ) q1 = [q0, B, ..., B, 0] B = [B, ..., B]

Para iniciar la simulacin de un movimiento de M1, la mquina M2 se sita en el smbolo marcado ms a la izquierda. La simulacin de un movimiento de M1 consiste en recorrer la cinta de izquierda a derecha almacenando los smbolos marcados y de derecha a izquierda moviendo las marcas de los smbolos y cambiando los smbolos anteriormente marcados.

Modificaciones equivalentes al modelo determinista bsico (III)

Mquina no determinista

M = (Q, , , , q0, B, F) : Q P(Q {L, R}) (q,a) = {(p1, a1, z1), ..., (pm, am,zm)} zi {L,R}

Llamamos grado de indeterminismo de la mquina M a la aridad mxima de la funcin (el nmero mximo de elecciones que la mquina pueda tener en cualquier configuracin) Las transiciones entre descripciones instantneas originan la definicin de los rboles de computacin

rboles de computacin

M = (Q, , , , q0, B, F) grado de indeterminismo n aridad del rbol n w * q0 w 1 q1 1 11 q11 11 2 q2 2 1p q1p 1p

M acepta w si existe un camino desde la raz hasta una hoja con estado final

j qj j j1 qj1 j1 jm qjm jm

p pF

q qF

Teorema Para cualquier mquina de Turing M1 no determinista existe otra equivalente M2 determinista

M1 = (Q1, , 1, 1, q1, B, F1)

(grado de indeterminismo n)

M2 = (Q2, , 2, 2, q2, B, F2)

Dada una cadena w, para comprobar si w es aceptada por M1 basta con recorrer en anchura su rbol de computacin. Si w es aceptada se llegar a una descripcin instantnea de aceptacin. Una secuencia de computacin ser una secuencia finita de dgitos enteros i1 i2 ... im donde ij {1, .., n}. Cada dgito indica la posible eleccin de movimiento que se efecta en M1 (ej. 12232 significa elegir el movimiento 1, luego el 2, luego el 2, luego el 3 y luego el 2). Una secuencia de computacin es factible si todos y cada uno de sus movimientos se pueden aplicar en la mquina M1. Una secuencia de computacin factible es de aceptacin si el ltimo estado al que llega la mquina M1, de acuerdo con la secuencia, es un estado final. En cado contrario la secuencia de computacin factible es de rechazo.

El orden lexicogrfico de las secuencias de computacin posibilita el recorrido en anchura del rbol de computacin.

q0 w i0 i1

Si w es aceptada por M1 existe una secuencia de computacin que conduce a M1 hacia un estado de aceptacin: i0 i1 i2 ... in M2 genera todas las posibles secuencias de computacin hasta encontrar aqulla que conduce a M1 hacia un estado de aceptacin. Si no existe, entonces M2 nunca para. cinta de entrada w secuencia de computacin cinta de trabajo

1 q1 1 2 q2 2

n qn n in p pF M2

Modificaciones equivalentes al modelo determinista bsico (II)

Mquina off-line w1 w2 w3 ... wn $ cinta 1 (slo lectura, limitada) cinta 2

x1

x2

...

xm

y1

y2

...

yj

cinta k

q M = (Q, , , , q0, B, F)

Teorema Para cualquier mquina de Turing M1 off-line existe otra equivalente M2 con una sola cinta

La mquina M2 puede efectuar la misma simulacin que en el caso multicinta pero limitando los movimientos de la cinta 1 a la izquierda de o a la derecha de $ y reescribiendo siempre los mismos smbolos ledos en esa cinta

La tesis de Church-Turing
Cualquier modelo de computacin que intente capturar el concepto de lo que es computable debe ser equivalente a la mquina de Turing La nocin intuitiva de funcin computable puede ser identificada con la de funcin recursiva parcial Otros modelos de computacin formulados a lo largo del tiempo Sistemas de Post -clculo Mquina RAM Mquinas cunticas Clculo basado en el ADN, etc. Un modelo de clculo permite hipercomputacin si es capaz de resolver algunos problemas que las mquinas de Turing establecen como indecidibles (Ej. mquinas de Turing con orculos, redes de Siegelman, etc.)

La mquina de Turing como enumeradora de conjuntos

Una mquina de Turing generadora es una mquina de Turing multicinta con una cinta de salida de slo escritura. La mquina no necesita cadena de entrada y pierde el concepto de aceptacin/rechazo e incluso el de parada

M = (Q, , , , q0, B, )
# w1 # w2 # ...# wn # ...

wi * G(M) = {w1 , w2 , ..., wn , ... }

Lema Todo lenguaje generado por una mquina de Turing M1 es recursivamente enumerable Basta con construir una mquina de Turing multicinta M2 que acepte el lenguaje generado por M1
w

M1

M2

M2 simula a M1 y, cada vez que se genera una cadena wi, la compara con la cadena de entrada w. Si coinciden, para y acepta y en caso contrario sigue simulando a M1. L(M2) = G(M1)

Lema Todo lenguaje recursivamente enumerable puede ser generado por una mquina de Turing. Sea L = L(M1) un lenguaje recursivamente enumerable

M1
Bastar con construir una mquina de Turing M2 que genere slo aquellas cadenas que M1 acepte. Problema: cmo se pueden establecer todas las cadenas que acepta M1 si existe el problema de la parada ?

Hecho 1: Dado un alfabeto el conjunto infinito de cadenas de * es enumerable y el orden lexicogrfico identifica cada entero con una cadena Ejemplo = {a,b} * = { , a, b, aa, ab, ba, bb, aaa, aab, ... }

Hecho 2: El conjunto infinito formado por los pares de enteros positivos es enumerable

0 1 2 ... i ...

0 (0,0) (1,0) (2,0) ... (i,0) ...

1 (0,1) (1,1) (2,1) ... (i,1) ...

2 (0,2) (1,2) (2,2) ... (i,2) ...

... ... ... ... ... ... ...

j (0,j) (1,j) (2,j) ... (i,j) ...

... ... ... ... ... ... ...

Se pueden construir subrutinas en mquinas de Turing que generen * y los pares de enteros (i,j)

* (i,j) wi
cinta de salida

G(M2) = L(M1)

M2
(1) (2) (3) (4) (5)

M1

Generar (i,j) Generar wi Copiar wi a una cinta Simular M1 ante wi durante j movimientos Si M1 acepta, escribir wi en la cinta de salida de M2. En caso contrario ir a (1)

Lema Todo lenguaje generado por una mquina de Turing M1 en orden lexicogrfico es recursivo Para la siguiente construccin excluiremos el caso de que el lenguaje sea finito. En este ltimo caso se puede construir una mquina que acepte slo las cadenas del lenguaje y que para el resto pare y rechace (se puede hacer por casos finitos) Si el lenguaje es infinito basta con construir una mquina de Turing multicinta M2 que acepte el lenguaje generado por M1 y que pare ante cualquier entrada. Sirve la misma construccin que para el caso de los lenguajes recursivamente enumerables con la siguiente salvedad: M2 simula a M1 y, cada vez que se genera una cadena wi, la compara con la cadena de entrada w. Si coinciden, para y acepta y, en caso contrario, si wi > w para y rechaza y si wi < w genera la siguiente cadena. La condicin de parada queda garantizada por ser el lenguaje infinito. L(M2) = G(M1)

Lema Todo lenguaje recursivo puede ser generado por una mquina de Turing en orden lexicogrfico. Sea L = L(M1) un lenguaje recursivo. La mquina M1 para ante cualquier entrada * wi

M1

M2

M1

Bastar con construir una mquina de Turing M2 que genere, en orden lexicogrfico slo aquellas cadenas que M1 acepta. M2 genera las cadenas de * en orden lexicogrfico. La cadena wi se somete al anlisis de M1. Si M1 acepta wi entonces M2 la escribe en su cinta de salida. M2 slo genera las cadenas de L y adems lo hace en orden lexicogrfico.

Caracterizacin de los lenguajes recursivos y recursivamente enumerables (utilizacin de esquemas)

Lenguajes recursivamente enumerables

S (w L(M))

<L> (<w1#w2# ...)

aceptora L=L(M)

generadora L=G(M)

Lenguajes recursivos S (w L(M))

M
N (w L(M)) aceptora L=L(M)

<L>o.l. (<w1#w2# ...)

generadora L=G(M)

Mquinas restringidas equivalentes al modelo bsico

Mquinas binarias

M = (Q, {0,1}, {0,1,B}, , q0, B, F)

Teorema Si L (0+1)* es recursivamente enumerable entonces L es aceptado por una mquina de Turing binaria Sea L = L(M1) con M1 = (Q1, {0,1}, , 1, q1, B, F1). Construiremos M2 = (Q2, {0,1}, {0,1,B}, 2, q2, B, F2) de forma que L = L(M2) Cada smbolo de se puede codificar con un cdigo binario de k smbolos. Q2 = Q1 {0,1,B}k F2 = F1 Bk q2 = [q1, B,B, ..., B]

w
w1 w2 cod(w1) k celdas wp cod(wp) = {a1, a2, , an } k = log2 n cod(ai) {0,1}k

M2
M2 lee la cadena de entrada w y escribe su cdigo en otra cinta. A partir de ese momento la simulacin de M1 se efecta de la siguiente forma:
(1) Leer k celdas de la cinta con la entrada codificada y almacenar sus smbolos en el control finito. (2) Escribir el cdigo del nuevo smbolo de acuerdo con la funcin 1 (3) Cambiar al nuevo estado de acuerdo con la funcin 1 (4) Moverse al comienzo del siguiente cdigo por la derecha o por la izquierda de acuerdo con la funcin 1

Mquinas de Turing y lenguajes de tipo 0

Una gramtica de tipo 0 se define por la tupla G=(N,T,P,S) donde las producciones de P son de la forma (NT)+ (NT)*

Teorema L es un lenguaje recursivamente enumerable sii L=L(G) donde G es de tipo 0.

Relacin con la jerarqua de Chomsky

L3 L2 L1 L0 = Lr.e.

Autmatas de memoria limitada linealmente y lenguajes de tipo 1

Una gramtica de tipo 1 se define por la tupla G=(N,T,P,S) donde las producciones de P son de la forma (NT)+ (NT)* || || S sii S no aparece en la parte derecha de ninguna otra produccin

Un autmata de memoria limitada linealmente (ALL) es una mquina de Turing no determinista monocinta que satisface las dos siguientes condiciones (1) El alfabeto de entrada incluye los limitadores y $ (2) El ALL no mueve su cabeza de cinta fuera de los limitadores ni escribe sobre ellos Se define la clase LALL

Teorema L es un lenguaje sensible al contexto (de tipo 1) sii L es aceptado por un ALL
Relacin con la jerarqua de Chomsky

L3 L2 L1 = LALL Lrec L0 = Lr.e.