Máquinas de Turing
Aumentando el poder
Hasta aquí:
•Autómatas finitos (lenguajes regulares), el poder
de cómputo de los sistemas con memoria finita.
Bastante limitados: pueden describir
patrones “simples” en texto.
•Autómatas de pila (lenguajes de libre contexto),
memoria no acotada pero de acceso limitado.
Pueden describir lenguajes de programación, humanos...
Pero ciertamente un computador puede hacer más.
Como reconocer {w=anbncn}, o {w=uu}
Aumentando el poder
n n n
a b c
?
ww ?
lenguajes de libre contexto
n n
a b
ww
lenguajes regulares
a*
a*b*
R
Memoria más accesible
Ahora agregaremos la posibilidad de moverse con
libertad por la memoria (sin ir borrando lo que se lee,
como en el PDA).
•La memoria será una cinta potencialmente infinita,
en la que podemos escribir y leer símbolos.
•Movemos la cinta una posición a la izquierda o a la
derecha, para acceder a otras posiciones de
memoria.
•Alternativamente, podemos pensarlo como que
estamos moviendo un “cabezal” sobre la cinta.
Memoria y unidad de control
Cinta
......
......
Cabezal para leer y escribir
“Unidad de control”
Al igual que antes, la
máquina tiene una
cantidad finita de
estados, que
representamos con un
grafo de transiciones.
Memoria y unidad de control
…
…
•Este esquema de “unidad de control” interactuando
con una memoria de acceso “libre” suena familiar para
un informático, y no es casualidad.
Pero notemos que es una extensión de los modelos de
cómputo anteriores:
•En los AF, no había memoria externa.
•En los PDA, estaba restringida a una pila.
Input en cinta; posición inicial
•Hasta ahora el input lo hemos estado leyendo de una
“cinta” aparte. Ahora no será necesario: podemos
asumir que viene escrito en la cinta.
casillas en blanco
input
......

 w0
w1 w2 ...
wn


......
posición inicial del cabezal
En cada paso,
la máquina
•Lee un símbolo de la cinta
•Escribe un símbolo en la cinta
•Mueve el cabezal a izquierda o derecha
• Actualiza su estado interno
Representando transiciones
lo que leo
q1
lo que
escribo
a  b, L
Nota: también se usa la
notación (a,b,L), en lugar
de ab,L.
el movimiento
del cabezal
(L:left, R:right)
q2
el cambio de estado
de la máquina
Representando transiciones
•Aparte del contenido de la cinta, lo único que
necesitamos para conocer el estado del sistema es la
ubicación del cabezal y el estado de la máquina.
•Por eso se suelen anotar juntos:
......

 a
b
a c
q1
 

......
Representando transiciones
Si la descripción de la máquina incluye un transición
a  b, R
q1
q2
lo que ocurrirá será
Tiempo k
......

 a
b
a c
 

......
 

......
q1
Tiempo k+1
......

 a
b
b c
q2
Representando transiciones
Otro ejemplo, aplicando
  g, L
q1
......

 a
b
q2
a c
 

......

......
q1
......


a
b
b c
q2
g 
Determinismo
Hasta que indiquemos lo contrario, las máquinas de
Turing serán deterministas:
•Para un mismo estado y símbolo en la cinta, sólo
hay una transición posible.
•Nada de transiciones .
a  b, R
q2
q1
a  b, R
q2
a  d,L
q3
q1
b  d,L
q3
Función parcial
Pero a diferencia de los AFD, no exigiremos que
todos los casos estén cubiertos.
Por lo tanto, puede ser que para un cierto símbolo
leído, y cierto estado, no haya ninguna transición.
 Si eso ocurre, la máquina se detiene.
En particular, los estados de aceptación no tienen
transiciones de salida. Por lo tanto, son estados
finales: la máquina acepta y se detiene.
Rechazo o aceptación
Cuando la máquina se ejecuta partiendo con una
palabra w en la cinta, decimos que la máquina
Acepta w:
•si se detiene en algún momento en un estado de
aceptación
Rechaza w:
Cuando no acepta. Esto puede ocurrir:
•si se detiene en algún momento en un estado
que no es de aceptación
•...o si nunca se detiene
Un ejemplo
T=0

a
a
a 
a  a, R
q0
T=1

a
a
T=2

a
a
q0
a 
q0
a 
  , L
q1
Consideremos la máquina de
la arriba, y hagámosla
correr sobre el input aaa.
q0
T=3

a
a
a 
q0
T=4

a
a
a 
q 11
q
Stop y
acepta
Un ejemplo de rechazo
T=0
a  a, R

a b
a 
q0
q0
  , L
q1
La misma máquina pero
con input aba, rechaza.
T=1

a b
a 
q0
Stop y
rechaza
Otro tipo de rechazo
T=0
b  b, L

a  a, R
q0
  , L
a b
a 
q0
T=1

a b
q1
Para ver un caso de
rechazo por loop
infinito, modificamos un
poco la máquina.
a 
q0
T=2

a b
a 
q0
T=4

a b
q0
a 
...etc
Formalmente
Una máquina de Turing queda definida por
M = ( Q, , , , q0, F, )
donde
•Q es un conjunto finito de estados
• es el alfabeto de la cinta
• es el alfabeto leído por la máquina
•\ es el carácter “blanco” de la cinta
(también se usa B, o )
•q0Q es el estado inicial
•F son los estados de aceptación
Formalmente
Una máquina de Turing queda definida por
M = ( Q, , , , q0, F, )
donde
•: QQ{L,R} es la función de transición
Como dijimos antes, se permite que para algunos
pares (q,a) el valor de (q,a) no esté definido.
 Lo podemos interpretar como que en esos casos
(q,a) vale “stop” (y algunos libros lo tratan así).
Descripción instantanea
El sistema se echa a andar con
•el input w* escrito en la cinta
•el resto de la cinta en blanco
•la máquina en estado q0
•el cabezal apuntando al comienzo de w
Por lo tanto, en cualquier momento T la máquina no
habrá visitado aún las casillas que estén a distancia
mayor que T respecto a la posición inicial.
 En todo instante el tramo de la cinta que no está
en blanco es finito.
Descripción instantanea
Eso permite dar una descripción finita del estado del
sistema en un momento dado:
•Sea v el contenido de la cinta desde la posición del
cabezal hasta el último símbolo no blanco.
•Sea u el contenido de la cinta desde el primer símbolo
no blanco hasta la casilla anterior a la del cabezal.
•Sea q el estado interno de la máquina.
u


c
•Entonces anotamos la
v
a
b
q
a 

descripción instantánea o
configuración como uqv.
•Si hay que evitar alguna
confusión, escribimos [u,q,v].
Descripción instantanea
Como antes, escribimos
u q v  u’ p v’
si  lleva el sistema de uqv a u’pv’
•Usamos la misma “” para denotar su clausura
transitiva (aplicación reiterada de ).
Podemos entonces definir el lenguaje aceptado por M
como
L(M) = { w*: q0w  uqv, qF }
Una convención práctica
Llamémosle "área de trabajo"
a la zona de la cinta que no
está en blanco.
área de trabajo


c
...
a 

•Es recomendable no usar el símbolo  dentro del área de
trabajo; así siempre podemos usarlo para identificar los
bordes. Seguiremos ese consejo.
•El área de trabajo puede crecer y crecer, pero en cualquier
momento dado será finita (pues partió siendo finita).
•La descripción instantanea uqv da el contenido del área de
trabajo (uv), el estado interno de la máquina (q) y su ubicación
(entre u y v, apuntando al comienzo de u).
Volvamos al ejemplo: una observación
•Claramente, el lenguaje
aceptado por el ejemplo que
vimos es a*
•Ese es un lenguaje regular.
a  a, R
q0
  , L
•Nótese además que esta MT no escribe.
No es casualidad: no es dificil ver que cualquier
lenguaje regular puede ser aceptado por una MT
que no altera su cinta.
q1
MT para lenguajes regulares
Idea:
•La MT simplemente lee la palabra como lo haría el AFD,
avanzando siempre hacia la derecha.
•Sus estados corresponden a los del AFD.
•Se agrega un estado extra para la aceptación (pues los del
AFD no eran de detención; pierden su condición de estado
de aceptación al pasar a la MT), y para llegar a él se
chequea el fin del input..
Detalles: ejercicio.
De hecho es un ssi:
•Si a la MT le prohibimos escribir, sólo puede aceptar
lenguajes regulares.
Otro ejemplo
Veamos un MT para el lenguaje {anbn}
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
y  y, L
a  a, R
a  a, L
a  x, R
q1
b  y, L
x  x, R
q2
T= 0
 a a b b  
q0
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
y  y, L
a  a, R
a  a, L
a  x, R
q1
b  y, L
x  x, R
q2
T= 1
 x a b b  
q1
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
y  y, L
a  a, R
a  a, L
a  x, R
q1
b  y, L
x  x, R
q2
T= 2
 x a b b  
q1
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
y  y, L
a  a, R
a  a, L
a  x, R
q1
b  y, L
x  x, R
q2
T= 3
 x a
y b  
q2
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
y  y, L
a  a, R
a  a, L
a  x, R
q1
b  y, L
x  x, R
q2
T= 4
 x a
y b  
q2
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
y  y, L
a  a, R
a  a, L
a  x, R
q1
b  y, L
x  x, R
q2
T= 5
 x a
y b  
q0
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
y  y, L
a  a, R
a  a, L
a  x, R
q1
b  y, L
x  x, R
q2
T= 6
 x x
y b  
q1
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
y  y, L
a  a, R
a  a, L
a  x, R
q1
b  y, L
x  x, R
q2
T= 7
 x x
y b  
q1
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
y  y, L
a  a, R
a  a, L
a  x, R
q1
b  y, L
x  x, R
q2
T= 8
 x x
y y  
q2
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
y  y, L
a  a, R
a  a, L
a  x, R
q1
b  y, L
x  x, R
q2
T= 9
 x x
y y  
q2
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
y  y, L
a  a, R
a  a, L
a  x, R
q1
b  y, L
x  x, R
q2
T= 10
 x x
y y  
q0
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
y  y, L
a  a, R
a  a, L
a  x, R
q1
b  y, L
x  x, R
q2
T= 11
 x x
y y  
q3
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
y  y, L
a  a, R
a  a, L
a  x, R
q1
b  y, L
x  x, R
q2
T= 12
 x x
y y  
q3
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
y  y, L
a  a, R
a  a, L
a  x, R
q1
b  y, L
x  x, R
q2
T= 13
 x x
y y  
q4
Para & acepta
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
y  y, L
a  a, R
a  a, L
a  x, R
q1
b  y, L
x  x, R
q2
El segundo ejemplo
Podemos resumir el funcionamiento de esa máquina
de Turing mediante pseudocódigo:
While veo a
•ax
•Avanzar
•by
•Avanzar
•Avanzar
Avanzar (R)
Aceptar
(R) saltando {a,y}, hasta ver b
(L) saltando {a,y}, hasta ver x
(R)
saltando {y} hasta ver 
La gracia: nada nos impide extender la idea
para reconocer {anbncn}.
{anbncn}, pseudocódigo
While veo a
•ax
•Avanzar
•by
•Avanzar
•cz
•Avanzar
•Avanzar
Avanzar (R)
Aceptar
(R) saltando {a,y}, hasta ver b
(R) saltando {b,z}, hasta ver c
(L) saltando {a,y,b,z}, hasta ver x
(R)
saltando {y,z} hasta ver 
Ejercicio:
•Hacer la MT
•Proponer alternativa que use sólo {a,b,c,x,}
como alfabeto en la cinta.
LR:decidido; LRE:aceptado
Decimos que una máquina de Turing M decide un
lenguaje L si M acepta L, y además M siempre se
detiene.
•Los lenguajes que son decididos por alguna MT
se llaman lenguajes recursivos (LR).
•Los lenguajes que son aceptados por alguna MT
se llaman lenguajes recursivos enumerables
(LRE).
Nótese que, por definición, LR  LRE.
Funciones Turing-computables
Otra forma de “usar” una MT es mirando lo que deja
en la cinta cuando se detiene.
•Como la MT es determinista, el estado final de la
cinta está determinado completamente por el
estado inicial: es una función del estado inicial.
Dada una MT M y un input w*, hay dos casos:
•Si M se detiene con configuración upv,
definimos fM(w)=uv.
•Si M nunca se detiene, definimos fM(w)=
(decimos que para w, fM diverge).
Funciones Turing-computables
Config. inicial

w
q0
Config. final


fM (w)
q
Loop ()
Entonces, toda MT M induce una función
fM:**{}
Decimos que una función f es Turing-computable si
existe una MT que la induce.

Funciones Turing-computables
Observaciones:
•Sin perder generalidad, podemos suponer que el
dominio de f está restringido a un dominio D  *.
•Algunos autores exigen que al terminar el
cómputo el cabezal esté en el inicio de f(w).
No es difícil modificar la MT para cumplir
con eso, si hace falta.
•Para efectos prácticos, los argumentos de fM se
suelen codificar en * (i.e., en general no los
escribimos tal cual como los leeríamos nosotros).
Ejemplo: x+y
•Para simplificar, codificaremos números enteros en
sistema unario.
5
decimal
101
binario
11111
unario
Demostremos que la suma de números naturales es
una función computable.
f ( x, y )  x  y
Input: x0y
Output: xy0
Aprovecharemos que x concatenado
con y da x+y, en unario
Ejemplo: x+y
1  1, R
1  1, R



,
L
0

1
,
R
q1
q0
1  1, L
q 2 1  0, L
q3
  , R
q4
T= 0
 1
1 0 1 1

q0
1  1, R
1  1, R



,
L
0

1
,
R
q1
q0
1  1, L
q 2 1  0, L
q3
  , R
q4
T= 1
 1
1 0 1 1 
q0
1  1, R
1  1, R



,
L
0

1
,
R
q1
q0
1  1, L
q 2 1  0, L
q3
  , R
q4
T= 2
 1
1 0 1 1

q0
1  1, R
1  1, R



,
L
0

1
,
R
q1
q0
1  1, L
q 2 1  0, L
q3
  , R
q4
T= 3
 1
1 1
1 1 
q1
1  1, R
1  1, R



,
L
0

1
,
R
q1
q0
1  1, L
q 2 1  0, L
q3
  , R
q4
T= 4
 1
1 1 1 1

q1
1  1, R
1  1, R



,
L
0

1
,
R
q1
q0
1  1, L
q 2 1  0, L
q3
  , R
q4
T= 5
 1
1 1
1 1 
q1
1  1, R
1  1, R



,
L
0

1
,
R
q1
q0
1  1, L
q 2 1  0, L
q3
  , R
q4
T= 6
 1
1 1 1 1

q2
1  1, R
1  1, R



,
L
0

1
,
R
q1
q0
1  1, L
q 2 1  0, L
q3
  , R
q4
T= 7
 1
1 1
1 0 
q3
1  1, R
1  1, R



,
L
0

1
,
R
q1
q0
1  1, L
q 2 1  0, L
q3
  , R
q4
T= 8
 1
1 1 1 0

q3
1  1, R
1  1, R



,
L
0

1
,
R
q1
q0
1  1, L
q 2 1  0, L
q3
  , R
q4
T= 9
 1
1 1
1 0 
q3
1  1, R
1  1, R



,
L
0

1
,
R
q1
q0
1  1, L
q 2 1  0, L
q3
  , R
q4
T= 10
 1
1 1 1 0

q3
1  1, R
1  1, R



,
L
0

1
,
R
q1
q0
1  1, L
q 2 1  0, L
q3
  , R
q4
T= 11
 1
1 1
1 0 
q3
1  1, R
1  1, R



,
L
0

1
,
R
q1
q0
1  1, L
q 2 1  0, L
q3
  , R
q4
T= 12
 1
1 1 1 0

q4
1  1, R
1  1, R
1  1, L



,
L
0

1
,
R
q1
q0
q 2 1  0, L
Parar y
aceptar
q3
  , R
q4
Otro ejemplo: 2x
Esta MT calcula 2x, para x en unario:
1  $, R
1  1, L
1  1, R
q 0    , L q1 $  1, R
  , R
q3
  1, L
q2
Otro ejemplo: 2x
Describamos su
funcionamiento en
pseudocódigo informal:
1  $, R
1  1, L
1  1, R
q 0    , L q1 $  1, R
  , R
•Reemplazar cada 1 por un $.
q3
•REPETIR
•Encontrar el $ de más a la derecha,
cambiarlo a 1.
•Ir al extremo derecho, insertar un 1.
HASTA que no queden $
¿Cómo calcularíamos xy? ¿Y n!?
  1, L
q2
Más cómputos
Si quisiéramos calcular
1
x y
0
x y
f ( x, y ) 
el “pseudocódigo” sería:
•Para cada 1 en x, ir borrándolo y borrando un 1 del y.
•Si en algún momento busco un 1 en y, y no encuentro,
entonces borrar todo y escribir un 1.
•Si eso nunca ocurre, y es x el que se acaba, borrar
todo y escribir un 0.
Ejercicio: construir la MT.
Combinación de máquinas
•Programar MT es engorroso, pero esencialmente
fácil.
•El paradigma resulta sorprendentemente flexible.
•También es notablemente robusto: es posible
agregar muchas “features” (por ejemplo, una segunda
cinta) a una MT sin que su poder de cómputo cambie.
•Veremos varios de esos “features”; con ellos en
mano, es más fácil construir MT más ambiciosas.
Combinación de máquinas
input
MT
output
•En particular, será posible ver cada MT como una
“caja negra”, que se puede usar como subrutina en
otra MT.
x, y
x, y
MT comparadora
MT sumadora
x y
MT borradora
0
x y
x y
Variaciones c/r a las MT estándar
Nuestro modelo estándar:
1 cinta, infinita en ambas direcciones
  a a b a b b c a c a   
cabezal que
escribe y lee
(movimiento es a
izquierda o derecha)
transiciones entre los
estados internos de la
MT son determinísticas
Variaciones c/r a las MT estándar
Algunas variantes:
•Cinta semi-infinita.
•Varias cintas.
•“Cinta” bidimensional.
•Opción de no mover el cabezal.
•Opción de insertar símbolos.
•Transiciones no deterministas.
•MT “offline” (el input queda sin tocar, en su
propia cinta).
•Largo Etc.
Variaciones c/r a las MT estándar
Ninguna de estas variantes altera el poder de
cómputo de las MT.
¿Qué significa eso?
Que los lenguajes que se pueden aceptar o
decidir son los mismos.
En cada caso se demuestra que si MT
estándar M, entonces MT M’ del tipo
modificado que es equivalente, y viceversa.
Variaciones c/r a las MT estándar
¿Qué significa que las máquinas sean equivalentes?
•Si estamos viendo la MT como un reconocedor
de lenguajes, significa dos cosas:
que L(M)=L(M’)
que M se detiene con input w ssi M’ se
detiene con input w.
•Si en cambio vemos la MT como el cómputo de
una función, significa que fM=fM’
(Pues en la opción fM(w)= ya está incluida la
información sobre la detención)
MT con opción “Stay”
Una MT+stay (máquina de Turing con opción “stay”)
es similar a la MT estándar, pero además de poder
mover el cabezal a izquierda o derecha (“L” o “R”),
tiene la opción de dejarlo donde está (“S”).
Por ejemplo, una transición podría ser
q1
a  b, S
q2
y al aplicarla ocurrirán cosas del tipo
  a a b a b b c ...
q1
  b a b a b b c
q2
...
MT con opción “Stay”
Teorema: las MT+stay tienen el mismo poder de
cómputo que las MT estándar.
Demostración: demostraremos que
1. Las MT+stay tienen al menos el poder de
cómputo de las MT estándar.
2. Las MT estándar tienen al menos el poder de
cómputo de las MT+stay.
MT con opción “Stay”
1. Las MT+stay tienen al menos el poder de
cómputo de las MT estándar.
Demostración: directo, pues la MT estándar es un
caso particular de MT+stay.
2. Las MT estándar tienen al menos el poder de
cómputo de las MT+stay.
Para eso, veremos cómo convertir una MT+stay en
una MT estándar, sin alterar su funcionamiento.
MT con opción “Stay”
Para cada transición que use el “S” (stay),
agregamos un estado auxiliar, y reemplazamos la
transición por 1+|| transiciones:
q1
q1
a  b, S
a  b, L
q2
q aux
x  x, R
q2
Una de esas por cada x  
QED
MT con opción “Stay”
q1 a  b , S q 2
q1
T=1
 a a b a 
 a a b a 
q1
q aux
x  x, R
q2
T=2
 b a b a 
q1
T=1
a  b, L
en M, la
MT+stay
q2
T=2
 b a b a 
q aux
T=3
 b a b a 
q2
en M’,
la MT
estándar
Ejercicio: MT con movimiento en dos pasos
A sugerencia del público, ejercicio:
Diremos que una MT es de "dos pasos" si sus opciones
de movimiento son {L, L2, R, R2}, donde L y R se
entienden como antes, L2 mueve el cabezal dos
posiciones hacia la izquierda, y R2 lo mueve posiciones
a la derecha.
EJ: Demostrar que las MT de "dos pasos" tienen el
mismo poder de cómputo de las MT estándar.
De hecho, dado kN, una MT con movimientos {L,
L2,..., Lk, R, R2,...,Rk} también sigue siendo equivalente.
MT con varias “pistas”
Una MT “multitrack” (varias pistas) tiene una única
cinta de memoria, pero esa cinta tiene más de una
pista de información:
  a b a b 
  b a c d 
pista 1
pista 2
Habrá transiciones de la forma
q1
b, a  c, d ; L
q2
MT con varias “pistas”
Claramente las MT multitrack son una generalización
de las MT estándar (basta con ignorar las pistas
adicionales para volver al caso estándar).
  a b a b 
  b a c d 
pista 1
pista 2
•Por otro lado, para simular una MT multitrack con
alfabeto  y k pistas, usando una MT estándar,
basta que tomemos ’ = k.
•Cada casilla de la cinta nueva contendrá lo que
había en las k pistas, en esa posición.
MT con varias “pistas”
M, multitrack
q1
b, a  c, d ; L
  a b a b 
  b a c d 
M’, estándar
q1
q2
T=0
( b , a )  ( c , d ), L
(  ,  ) (  ,  ) ( a , b ) ( b , a ) ( a , c )( b , d ) (  ,  )
q1
q1
  a c a b 
  b d c d 
q2
q2
T=1
(  ,  ) (  ,  ) ( a , b ) ( c , d ) ( a , c )( b , d ) (  ,  )
q2
MT con memoria "interna" finita
Una MT con memoria interna posee una o más variables
cuyo valor se guarda dentro del estado interno (no en la
cinta); cada variable debe tener un rango finito.
Por ejemplo: una MT podría tener las variables
• m1  D1 = {0, 1}
• m2  D2 = {blanco, azul, rojo}
• m3  D3 = {,}
Los valores se pueden consultar y modificar en las
transiciones (si no se modifican, quedan como estaban).
m 2  blanco , a  b ; L ; m 1  1  m 1
q1
q2
MT con memoria "interna" finita
Sin perder generalidad, podemos verlo como que fuese
una sola variable:
m = (m1,m2,m3)  D = D1D2D3
Claramente, es una extensión c/r a las MT estándar.
Pero: no cambia el poder de cómputo. Para simular una
MT con memoria interna mediante una MT estándar, la
idea es:
Reemplazar Q por Q' = QD.
MT con memoria "interna" finita
Q'
estado
interno
=
Q

estado "de
control"
D
variables
internas
La condición sobre valores de variables se convierte
simplemente en condición sobre el estado interno, y la
modificación de valores, en elegir a qué estado paso.
•Es importante que el rango (valores posibles) de las
variables internas sea finito; de lo contrario, Q' quedaría
infinito.
•Nótese que esta extensión también funciona para AFD y
para PDA.
MT con cinta semi-infinita
Una MT con cinta semi-infinita tiene una cinta que
es infinita en una sola dirección: en lugar de
...
 a a b a b b c a c a   ...
se tiene
# a b a c  
.........
•Aquí el # marca el fin de la cinta (como el "$" que
marcaba el fondo de la pila en los PDA).
•Algunos textos (p.ej. el Hopcroft) usan este tipo de MT
como "estándar".
MT con cinta semi-infinita
# a b a c  
.........
A diferencia de las modificaciones previas, esta no
es una "generalización", sino una "restricción"
respecto a nuestras MT estándar.
Las restricciones pueden restringir el poder de
cómputo (por ejemplo, si la MT no puede escribir, su
poder se reduce al de los AFD).
Sin embargo, esta restricción particular no cambia
el poder de cómputo:
MT con cinta semi-infinita
Es directo ver que toda MT con cinta semi-infinita
puede ser simulada por una MT estándar:
simplemente no usamos la cinta a la izquierda.
En dirección contraria: necesitamos probar que
dada una MT estándar, la podemos simular en una
con cinta semi-infinita.
MT con cinta semi-infinita
Fijamos un punto de referencia en nuestra cinta
infinita (puede ser la posición de inicio del cabezal).
.........

a b
c

e
d

.........
"Doblamos" la cinta infinita en torno a ese punto,
dejando una cinta semi-infinita de dos pistas:
lado derecho
lado izquierdo
# d
# c
e



b
a


.........
MT con cinta semi-infinita
lado derecho
lado izquierdo
# d
# c
e



b
a


.........
•Los movimientos L, R se invierten si estamos "abajo".
•Al pasar por el punto de referencia, "viramos".
•Aplicamos el método previo para pasar a una única cinta.
•Para saber si hay que mirar arriba o abajo, guardamos
una variable en memoria interna ("arriba", "abajo").
MT con marcas en la cinta
Podemos agregar a la MT la posibilidad de poner y
quitar marcas en la cinta (aparte del símbolo contenido
en la celda).
.........

a b
c
d
e


.........
Y luego podemos usar la marca para reconocer la celda.
La condición es que la variedad de marcas sea finita:
por ejemplo, M={,,} (donde  es "sin marca").
¿Cómo hacemos esto con una MT estándar?
 Reemplazamos  por ' =   M
MT con Insert/Delete
Una MT con insert puede hacer transiciones del tipo
q1
.........

a  dup , L
 a
b
q2
a c
 
.......

q1
.........

 a
b
a
a c
 
q1
(Duplica la celda, y se sitúa a la izquierda).

.......
MT con Insert/Delete
Una MT con delete puede hacer transiciones del tipo
q1
.........

a  del , L
 a
b
q2
a c
 

.......
q1
.........

 a
b
c
 

q1
(Borra la celda, y se sitúa a la izquierda).
.......
MT con Insert/Delete
Ambas operaciones se pueden implementar en una MT
estándar:
Para duplicar:
•Marcamos la celda
•Avanzamos hasta el final del área de trabajo
•Retrocedemos copiando cada celda en la siguiente
•...hasta llegar a la celda marcada.
Para borrar:
•Marco la celda y copia en ella el valor de la celda vecina.
•Sigo copiando hasta llegar al final del área de trabajo
•Me devuelvo hasta la celda marcada.
MT con varias cintas
Unidad de
control
Cinta 1

a b c 
Cinta 2

e
f g 
•A diferencia de la máquina "con varias pistas" que
vimos antes, en la MT "multicinta" cada cinta tiene su
propio cabezal.
•Las transiciones miran ambas cintas, y deciden
escritura y movimiento en ambas cintas.
MT con varias cintas
Cinta 1
T=1

Cinta 2
a b c 

e
q1
T=2

f g 
q1
a g c 

e d g 
q2
q2
q1
( b , f )  ( g , d ), L , R
q2
MT con varias cintas
¿Cómo podemos simular una MT multicinta, usando una
MT estándar?
Lo que haremos será simularla usando una MT con una
cinta, pero varias pistas (y esa ya sabemos que es
equivalente a la estándar).
Idea:
Por cada cinta de la MT multicinta, ponemos dos pistas:
•Una con los datos
•Otra que indica dónde está el cabezal.
MT con varias cintas
Cinta 1

a b c 
a b c
0 1 0
e f g h
0 0 1 0
 Cabezal de la
MT multipista
Cinta 2

e
f
g
h 
Cinta 1
"Cabezal" de la cinta 1
Cinta 2
"Cabezal" de la cinta 2
MT con varias cintas
Para simular un paso de la MT
multicinta, la MT multipista
hace lo siguiente:
a b c
0 1 0
e f g h
0 0 1 0
•Sitúa su cabezal a la izquierda de todos los "cabezales".
•Avanza hacia la derecha hasta ver todos los "cabezales", y
guardando en variables internas el símbolo apuntado por cada
uno de ellos.
•Aplica la regla de la MT multicinta, y guarda en variables
internas los nuevos símbolos y los movimientos de cada cinta.
•Avanza a la izquierda, aplicando eso a cada cinta a medida que
va encontrando los cabezales.
MT con varias cintas
Por lo tanto, toda MT multipista se puede simular con
una MT estándar, y viceversa.
Observaciones:
•Obviamente esta construcción es poco práctica: la
máquina multipista requiere muchos pasos para
simular cada paso de la máquina multicinta.
•Sin embargo, por ahora no nos interesa la
velocidad.
•Lo que interesa: es que lo computable (lenguajes,
funciones) no cambia.
MT multidimensionales
En una MT multidimensional, en lugar de tener una cinta
infinita (que se puede ver como una función Z),
tenemos un plano, volumen, o algo de dimensión mayor
(que se pueden ver como funciones Z2, Z3, etc).
y
En dimensión 2, los
movimientos serán

L,R,U,D (agregamos
 c a
up y down).
x

b

 El poder de cómputo tampoco
aumenta (pero no lo demostraremos!).
MT no-deterministas
En una MT no determinista,
existe más de una transición
posible a partir de una
configuración dada.
T=1
 a b c 
a  b, L
q2
q1
a  c, R
q3
q1
Opción 1
T=2
 b b c 
q2
Opción 2
 c b c 
q3
MT no-deterministas
Como de costumbre, el lenguaje asociado a una MT nodeterminista será el conjunto de palabras para las
cuales existe alguna cadena de decisiones que conduce
a un estado de aceptación.
Nuevamente se tiene la equivalencia: todo lenguaje
aceptado por una MT no-determinista, es aceptado por
una MT estándar (determinista).
Hay varias construcciones posibles; aquí solo
bosquejaremos una. Sea M la MT no-determinista, y
veamos como construir M' estándar, equivalente a M.
MT no-deterministas
Idea: a la usanza de los viejos sistemas operativos,
simularemos una máquina paralela usando una máquina
secuencial.
En la cinta habrá una serie (finita) de áreas de trabajo,
cada una con la posición de su "cabezal" marcada.
......

$
área 1
$
área 2
$

......
En cada vuelta, M' recorrerá todas las áreas,
ejecutando una iteración de M en cada una de ellas.
MT no-deterministas
......
......

$
 $ área 1a
área 1
$
$
área 2
área 1b
$
$

......
área 2 $ 
Cada vez que toque "adivinar" un paso, el área de
trabajo se bifurcará (usamos un "insert"), y ahora
habrá un área por cada opción.
Si en algún momento en alguna versión del área de
trabajo M llega a aceptar el input, M' lo aceptará.
......
MT offline
Una MT offline tiene dos cintas: el input, que sólo se
lee, y otra para trabajar.
Cinta de entrada
a b c
c $
sólo lectura
Unidad de control
lectura/escritura
Cinta de trabajo
  g d e  
Claramente, el poder de cómputo tampoco cambia.
LLC  LRE
•Ya vimos que los lenguajes regulares pueden ser
aceptados por MT (y sin siquiera escribir en la cinta).
•Para ver que los lenguajes de libre contexto son
aceptados por MT, tomamos un PDA cualquiera...
Input
Estados
internos
PDA
Pila
...y lo podemos ver
como una MT nodeterminista con
dos cintas:
•una de sólo lectura
(con el input)
•la otra (la pila)
inicialmente vacía.
Jerarquía de lenguajes
•Sabíamos que los lenguajes regulares eran un caso
particular de los lenguajes de libre contexto; ahora
vemos que los de libre contexto son caso particular de
los recursivos.
•Vimos un lenguaje ( {anbncn} ) que es recursivo pero no
es LLC.
•E hicimos notar que recursivo  recursivo enumerable
(es decir, que ser decidido por una MT implica ser
aceptado por una MT).
•Tenemos entonces las siguientes inclusiones:
Jerarquía de lenguajes
Lenguajes
Lenguajes recursivos
enumerables (r.e.)
Lenguajes recursivos
Lenguajes de libre
contexto
Lenguajes
regulares
•Pronto veremos
ejemplos concretos
que muestran que
cada una de estas
inclusiones es
propia.
Dos teoremas sobre complementos
Teorema: L es recursivo ssi LC es recursivo.
Demostración:
•Usamos la misma MT, pero cambiamos sus estados
de aceptación: F' = Q \ F.
Teorema: Si L es r.e. y LC es r.e., entonces L es
recursivo.
Demostración:
•Dado un input w, ejecutamos simultáneamente las
MT de L y de LC (un paso a la vez para cada una).
•Tarde o temprano una de las dos se tiene que
detener, y sabremos si wL.
Enumeración
Dijimos que un conjunto es numerable si es finito, o si
tiene el cardinal de los números naturales (N). Para
evitar confusión le llamaremos a eso contable.
Ejemplos de infinitos contables:
•Z (enteros)
•Q (racionales)
•Z (pares ordenados de enteros)
•2Z (números pares)
Ejemplos de infinitos no contables:
•R (reales)
•[0,1] (o cualquier intervalo con más de 1 elemento)
•P(N) (cjto. formado por los subconjuntos de N).
Enumeración
Por lo general para demostrar que un conjunto es
contable lo que se hace es describir un procedimiento
de enumeración.
Sea L un conjunto de palabras. Definiremos un
procedimiento de enumeración para L como una
máquina de Turing que:
•no recibe ningún input
•genera todas las palabras de L
•cada palabra es generada en tiempo finito
Podemos suponer que hay una cinta de trabajo, y otra
en la cual escribir las palabras de L.
Enumeración
......
  

w1
área de trabajo
#
w2
#

w3

# 

 
......
......
Es útil pensar en la cinta de salida como una "impresora",
donde la MT va agregando palabras.
Que la MT enumere L significa que:
•wL, tw en que w es impresa.
•Si w es impresa, wL.
Enumeración
OJO:
Diremos que un lenguaje es enumerable (con "e") si
hay una MT que lo enumere.
Si un conjunto (en particular, un lenguaje) es
enumerable, entonces necesariamente es contable (de
hecho, cualquier lenguaje es contable).
Sin embargo, lo contrario no es necesariamente
cierto: puede que un conjunto sea contable y sin
embargo no exista una MT que lo enumere.
Enumeración
Sea  un alfabeto (es decir, un conjunto finito
cualquiera). Entonces * es un conjunto infinito
enumerable. ¿Por qué?
 Hay que describir una forma de enumerar las
palabras de *
No toda idea es buena. Tomemos ={a,b} como ejemplo.
•Una idea que no funciona es listarlas en orden
alfabético (poniéndole algún orden alfabético a ):
como hay infinitas palabras que parten con a, jamás
llegaremos a listar las que parten con b.
Enumeración
•En cambio, sí podemos enumerar * si primero
listamos todas las palabras de largo 0, luego las de
largo 1, luego las de largo 2, etc.
•Dentro de las de un mismo largo, podemos seguir
orden alfabético.
 # a # b # aa # ab # ba # bb # aaa #...
A este tipo de orden (en longitud creciente, y orden
alfabético dentro de la misma longitud) se le llama
orden canónico.
Enumeración
Teorema: L* es recursivo enumerable ssi existe
una MT que lo enumera.
Demostración:
() Existe una MT ME que enumera L, y queremos
crear una MT MA que acepte L.
MA:
•Recibe un input w, y lo deja intacto en una cinta.
•Usa dos cintas más para echar a correr ME.
•Cada vez que ME imprime una palabra, MA la
compara con w. Si es igual, acepta w y se detiene.
De lo contrario, continúa.
Enumeración
Teorema: L* es recursivo enumerable ssi existe
una MT que lo enumera.
Demostración:
() Existe una MT MA que acepta L, y queremos
crear una MT ME que enumere L.
Tentación: que ME vaya listando las palabras de *
en orden canónico, y ejecutando MA para cada una,
para ver acaso están en L (e imprimiéndolas, cuando
la respuesta es sí).
Problema: para alguna palabra MA puede no detenerse,
y ME se quedará pegada (y nunca seguirá listando).
Enumeración
Teorema: L* es recursivo enumerable ssi existe
una MT que lo enumera.
Solución a eso: Construimos ME para que funcione
de acuerdo al siguiente algoritmo:
•Para k=0,1,2,...
•Listar las primeras k palabras (del orden
canónico): w1,...,wk
•Para cada wi,
•Ejecutar MA con input wi durante k pasos.
•Si MA aceptó wi, imprimir wi.
QED
Enumeración
Teorema: L* es recursivo enumerable ssi existe
una MT que lo enumera.
Teorema: L* es recursivo ssi existe una MT que
lo enumera en orden canónico.
Demostración: ejercicio.
Otros ejercicios: construir MT para enumerar:
• {anbn, n>0}
•los números naturales, en binario
•los números enteros, en decimal
Codificación
Para efectos de enumerar, pero también para efectos
de calcular funciones, y/o decidir propiedades,
necesitamos convertir el input en un string.
Sólo así puede ser input para una MT
Eso puede requerir una codificación no trivial, pero en
principio es siempre posible (con información digital).
Después de todo, los mp3, avi, jpg, son precisamente
información convertida a strings.
Lo importante es precisar qué codificación se usa.
Luego nuestra MT se ocupará de entenderla.
Codificación
Ejemplo: codificar un grafo dirigido.
Una opción: codificar la cantidad
de nodos, y la matriz de
adyacencia, en que Aij=1 si hay
arco de i a j, Aij=0 si no.
A
A 0
B 0
C 0
B
1
1
1
C
1
0
0
A
B
C
111#011010010
Cantidad de nodos
(en unario)
Matriz de
adyacencia
Codificación
Ejemplo: codificar un grafo dirigido.
Otra opción: codificar la cantidad
de nodos, y luego los arcos.
A
111#1#11#11#11#1#111#111#11
Cantidad de
nodos (en
unario)
(A,B) (B,B)
(A,C)
Ejercicios:
•codificar AFD
•codificar GLC
(C,B)
B
C
Codificación
Algo más complicado: las propias máquinas de Turing.
Podemos codificar en unario los símbolos de  y los
estados de Q (usaremos el contexto para evitar
ambigüedad). También los movimientos del cabezal: 1
para L, 11 para R.
símbolos
codificación
estados
a
b
c
d
1
11
111
1111
q1
q2
q3
q4


Codificación
Codificando una transición:
 ( q1 , a )  ( q 2 , b , L )
1 # 1 # 11 # 11 # 1
Codificando las transiciones:
 ( q1 , a )  ( q 2 , b , L )
1 # 1 # 11 # 11 # 1
 ( q 2 , b )  ( q3 , c , R )
##
11 # 1 1 # 111 # 111 # 11
Codificación
Podemos codificar la máquina entera dando:
[cantidad
[cantidad
[lista de
[lista de
de estados] #
de símbolos en ] #
transiciones] #
estados que son de aceptación]
Y tendremos un lenguaje LMT sobre el alfabeto {#,1},
formado por todas las posibles MT.
Codificación
LMT es un lenguaje recursivo:
•podemos construir una MT que vaya generando las
palabras de {#,1}* en orden canónico
•para cada una, chequeará si es una MT válida
(basta ver que siga el formato que describimos) y
los números calcen
•si es válida, imprime la palabra; si no, la ignora.
LMT se puede enumerar, y más aún, se puede
enumerar en orden canónico.
Codificación
Se deduce que existen lenguajes que no son r.e. (es
decir, no son aceptados por ninguna MT):
•Fijemos el alfabeto, .
•Como vimos, * es un infinito contable.
 P(*) es un infinito no contable: es decir, existe
una infinidad no contable de lenguajes distintos.
•Las MT sobre el alfabeto  son un conjunto
enumerable, ergo contable.
 No puede haber una MT (distinta) para cada
lenguaje. ¡No alcanzan!
Un lenguaje fuera de LRE
Sin embargo, podemos ser un poco más explícitos:
usaremos el método diagonal de Cantor para
construir:
•un lenguaje que no es r.e.
•un lenguaje que es r.e., pero no recursivo
Consideremos el alfabeto  = {a}.
Consideremos también las MT que aceptan
lenguajes sobre . Son enumerables: llamémoslas
M1, M2, M3, ...
Un lenguaje fuera de LRE
Cada L(Mi) es un conjunto de palabras de la forma an.
Podemos entonces hacer una "tabla" infinita anotando
qué palabras están en qué lenguajes.
a
1
a
2
a
3
a
4

L(M 1)
0
1
0
1

L(M 2 )
1
0
0
1

L(M 3 )
0
1
1
1

L(M 4 )
0
0
0
1




L
Definamos el
lenguaje L como
{ ak: ak L(Mk) }
Un lenguaje fuera de LRE
Por construcción, LC (ojo, el complemento de L) no
coincide con L(Mk) para ningún k.
 LC no es recursivo enumerable
a
1
a
2
a
3
a
4

L(M 1)
0
1
0
1

L(M 2 )
1
0
0
1

L(M 3 )
0
1
1
1

L(M 4 )
0
0
0
1




L
Un lenguaje en LRE, pero no recursivo
Por otro lado, L sí es recursivo enumerable.
Demostración: Podemos contruir una MT que lo
acepta, de la siguiente forma:
•Dado un input w=ak, identificamos el valor de k.
•Usando la MT que enumera las M1, M2,...,
encontramos Mk.
•Echamos a correr Mk, dándole el input w.
•Si se detiene y acepta, aceptamos w.
Un lenguaje en LRE, pero no recursivo
•L es recursivo enumerable.
•LC no es recursivo enumerable.
Por lo tanto, L no es recursivo :
•Si lo fuera, LC sería recursivo también.
•Pero en tal caso sería r.e.
 contradicción
¿Dónde quedan?
Lenguajes
Lenguajes recursivos
enumerables (r.e.)
Lenguajes recursivos
Lenguajes de libre
contexto
Lenguajes
regulares
LC
L
•LC no es recursivo
enumerable.
•L es recursivo
enumerable pero no
recursivo.
Máquina de Turing Universal
Turing, luego de definir el formalismo general y
mostrar MT que implementan diversas funciones,
define una MT muy especial: una máquina de Turing
universal (MTU).
La MTU recibe como input:
•La descripción de una máquina de Turing M
cualquiera.
•Una palabra w.
Máquina de Turing Universal
input w
MT <M>
U
M con input w
La MTU simula la máquina M, con input w. Por
lo tanto, lo que hubiese hecho M a partir de
w, lo hará la MTU.
Máquina de Turing Universal
No es difícil construir una
MTU usando tres cintas:
Cinta 1
1 # 1 # 11 # 11 # 1
Descripción de M
Máquina
de Turing
Universal
Cinta 2
 0 1 1 ...
Cinta de M
Cinta 3
p
Estado (interno) actual de M
Problema de membresía
Esta noción de MT simulando otras MT es poderosa.
En particular, sirve para demostrar la existencia de
problemas indecidibles.
Problema de membresía:
•Input: una MT M, y una palabra w
•Problema: ¿M acepta w?
Teo.: el problema de membresía es indecidible.
Demo.: por contradicción. Supongamos que el
problema de membresía es decidible.
Problema de membresía
En tal caso, existirá una MT (llamémosla B) que
resuelve el problema:
M
w
SÍ
B
¿M acepta w?
NO
M acepta w
M rechaza w
Problema de membresía
Escojamos en particular una M que acepte un lenguaje
L(M) que no es recursivo (ya vimos que eso existe).
M no siempre se detiene.
Usando la descripción de esa M en B, construyamos la
siguiente máquina:
M
w
SÍ
aceptar w
NO
rechazar w
B
¿M acepta w?
Problema de membresía
Esta máquina recibe w y responde (siempre) acaso w
está en L(M).
En ese caso L(M) sería recursivo: contradicción.
La máquina B no puede existir.
El problema de membresía es indecidible.
M
w
SÍ
aceptar w
NO
rechazar w
B
¿M acepta w?
QED
Problemas / lenguajes
Nota: hablaremos indistintamente de lenguajes y
problemas. ¿Motivo?
•A todo lenguaje le corresponde un problema.
•A todo problema de decisión (sí/no) le
corresponde un lenguaje (eso lo imponemos, porque
el concepto de “problema” no está definido!).
Ejemplo:
•Problema: ¿es N primo?
•Lenguaje: L={n:n es primo}, ¿NP?
Problemas / lenguajes
Ejemplo:
•Problema: sean G1 y G2 dos gramáticas de libre
contexto. ¿Generan el mismo lenguaje?
•Lenguaje: L={ (G,G'): G y G' son GLC, y L(G)=L(G') }.
¿ (G1 ,G2)  L?
Observación:
L es recursivo  “¿wL?” es decidible
Por ejemplo: si definimos La = { <M,w>: M describe una
MT, w es una palabra, y M acepta w },
lo que acabamos de demostrar es que La no es recursivo.
Problema de membresía
Veamos otra demostración de la indecidibilidad del
problema de membresía, que no usa resultados previos.
A partir de B, definamos una máquina C que hace lo
siguiente:
•Recibe una descripción de máquina <M>
•Le entrega a B el par <M>,<M>, de modo que B
responderá acaso M acepta <M>.
•Si B responde que sí, C rechaza; si B responde que
no, C acepta.
Problema de membresía
C
 M 
 M 
 M 
SÍ
B
¿M acepta <M>?
NO
rechazar
aceptar
¿Qué pasa si a C le entregamos <C> ?
•Si C acepta <C>, B dice que sí, luego C rechaza <C>.
•Si C rechaza <C>, B dice que no, luego C acepta <C>.
 Contradicción!!
Problema del alto
El problema indecidible más conocido es el “problema
del alto” o “problema de detención” (halting problem).
Input: una MT M, y una palabra w.
Problema:
¿se detiene alguna vez M, si parte con input w?
Teo.: el problema del alto es indecidible.
Demostración:
•Similar a la primera que hicimos para La.
•Supongamos que M con L(M) r.e., pero no recursivo.
•Supongamos que “H” decide el problema del alto.
Problema del alto
M
NO
H
w
¿M se detiene
al partir con w?
Rechazar w
SÍ
M
Correr M
con input w
Aceptar w
Rechazar w
Entonces esta máquina decidiría L(M)  contradicción!!!
¿Qué acabamos de hacer?  Reducción
Reducción:
"reducir un problema P a un problema Q"
significa que si tenemos una MT para Q, tenemos
una MT para P.
Acabamos de reducir el problema de membresía de una
MT no recursiva al problema del alto:
Si tuvieramos una MT para el alto, podríamos
decidir un problema que es (por definición!)
indecidible..
Ojo: la próxima semana veremos una noción de reducción
que requiera además ser "barata"; pero en esta sección
sólo nos interesa que exista alguna reducción.
¿Qué acabamos de hacer?  Reducción
Reducción:
"reducir un problema P a un problema Q"
significa que si tenemos una MT para Q, tenemos
una MT para P.
se reduce a
P
Solución de P
permite crear
Q
Solución de Q
•P no es más difícil que Q
•Q es al menos tan difícil como P
¿Qué acabamos de hacer?  Reducción
P
se reduce a
Q
Si P es indecidible, Q también lo es:
•De lo contrario, usando Q decidiríamos P, y
tendríamos una contradicción.
Para demostrar que un problema Q es indecidible, la
técnica habitual es:
•Tomar algún problema P que ya sabemos indecidible
•Reducirlo a Q.
¿Qué acabamos de hacer?  Reducción
P
se reduce a
Q
Por otro lado, si Q es decidible, P también lo es (es la
contrarrecíproca de lo anterior).
Para demostrar que un problema P es decidible, lo
podemos reducir a un Q que ya sabemos que es decidible.
Alternativamente [más usual] podemos describir
directamente un algoritmo decida P.
Otra reducción: problema de acceso
Problema de acceso a un estado ("A"):
•Input: Una máquina de Turing M, una palabra w, y
un estado q de M.
•Problema: ¿Partiendo con input w, pasa alguna vez
M al estado q?
Teorema: el problema A es indecidible.
Demostración: reduciremos el problema del alto ("H")
al problema A.
Problema de acceso a un estado
Modus operandi:
•Suponer que tenemos una MT para A.
•Pensar cómo usar eso para obtener una MT para H.
•Mostrar la construcción (o explicar en detalle
suficiente el algoritmo).
Entonces, asumimos que existe
M
w
q
MT que
decide A
sí
M pasa a q, al
partir de w
no
M no pasa a q, al
partir de w
Problema de acceso a un estado
y queremos
M
w
MT que
decide H
sí
M se detiene, al
partir de w
no
M no se detiene,
al partir de w
El truco: modificamos M para que, justo al detenerse,
pase a un estado especial (nuevo).
Problema de acceso a un estado
Dada una máquina M, que tenía varios estados de
detención (que, recordemos, no tienen transiciones
salientes!), creamos M':
•Agregamos transiciones hacia un nuevo estado q.
•Ese estado será el nuevo (y único) estado de detención.
M
M
q
estados de
detención
estado
nuevo
Problema de acceso a un estado
M' pasa al estado q  M se detiene
 Para resolver H con input (M,w), podemos
transformar M en M' y aplicar A con input (M',w,q).
M
M
q
estados de
detención
estado
nuevo
Problema de acceso a un estado
La máquina que decidiría H sería entonces:
M
generar M'
M
q
w
MT que
decide A
sí
sí
no no
w
Hemos reducido H a A.
Como H es indecidible, A también debe serlo.
Ejercicios
Problema del alto con cinta vacía:
Input: una MT M.
Problema: Si M se ejecuta con input vacío (cinta
inicialmente en blanco), ¿se detiene alguna vez?
Ejercicio: demostrar que este problema es indecidible.
Hint: reducir el problema del alto.
Vacuidad de lenguaje:
Input: una MT M.
Problema: ¿L(M)=?
Ejercicio: demostrar que este problema es indecidible.
Hint: reducir el problema de membresía.
Teorema de Rice
Diremos que una propiedad relativa al lenguaje
reconocido por una máquina de Turing es trivial si es
cierta para todas las MT, o para ninguna.
Teorema (Rice): cualquier propiedad no trivial de
los lenguajes de las MT es indecidible.
Demostración: en las próximas transparencias, pero
sólo para los curiosos, y para que no pelen. Pero no es
muy intuitiva, así que pueden saltársela sin daño.
Teorema de Rice: demostración
Esquema de la demostración del teorema de Rice:
•Sea T el conjunto de todas las MT cuyo lenguaje
cumple la propiedad no trivial.
•Sea M una MT con lenguaje . Sin perder
generalidad, podemos suponer que MT (de lo
contrario, trabajamos con TC).
•Sea M1 una MT que sí está en T.
•Mostraremos que si T es decidible, entonces el
problema del alto ("H") lo es.
Teorema de Rice: demostración
Dados M y w, para los que queremos resolver el
problema del alto,
 construimos M', una máquina que, dado un input x,
hace lo siguiente:
•Ejecuta M con input w
•Si M aceptó w:
•Ejecuta M1 con input x
Si M1 aceptó x, aceptar.
Si M1 rechazó x, rechazar.
(Si al ejecutar
M(w), o M1(x),
alguna no se
detiene, entonces
M' tampoco se
detiene.)
Teorema de Rice: demostración
M'(x):
•Ejecuta M con input w
•Si M aceptó w:
•Ejecuta M1 con input x
Si M1 aceptó x, aceptar.
Si M1 rechazó x, rechazar.
Si M no se detiene con w:
 M' rechaza cualquier x
 L(M')=
 M'  T
Si M se detiene con w:
 M' acepta x  M1 acepta x
 L(M')=L(M)
 M'  T
Si pudiéramos decidir la propiedad T, podríamos
decidir el problema del alto.
Teorema de Rice: uso
El teorema mismo no hay que saltárselo, pues es muy
poderoso.
Por ejemplo: existen MT que tienen lenguajes finitos,
y existen MT que tienen lenguajes infinitos.
Ser finito es una propiedad no trivial del
lenguaje asociado a las MT.
Es indecidible el problema de determinar acaso
el lenguaje asociado a una MT es finito.
También será indecidible acaso el lenguaje de una MT
es regular, acaso contiene dos palabras del mismo
largo, etc etc.
Funciones no computables
Una función es [Turing-]computable ssi existe una MT
que las calcula. Si no existe ninguna, es no-computable.
¿Ejemplo de función no computable? Fácil:
•L={ <M,w>, donde M describe una MT, w es input}
•f:L{0,1} definida como f(<M,w> ) = 1 si M se
detiene al partir con input w, 0 si no.
•Si una MT calculara f, resolvería el problema del
alto.
Ocurrirá lo mismo con cualquier problema indecidible:
su función indicatriz es no computable.
Funciones no computables
Veamos un ejemplo más
interesante: la función/juego
de los castores atareados
(busy beaver).
Propuesto por Tibor Radó en 1962: dado k y n,
diseñar una máquina de Turing estándar M con n
estados (sin contar el de detención), y cinta de k
símbolos, tal que:
•M se detenga al iniciarse con cinta en blanco.
•Tarde lo más posible en detenerse.
Funciones no computables
Nótese que la cantidad de máquinas posibles, para
k y n dados, es finita.
Siempre existe una máquina que gana el juego.
Podemos definir BB(n,k) como la cantidad de
pasos que demora esa máquina en detenerse.
Teorema: BB(n,k) es una función no computable.
Demostración: ejercicio!
Hint: reducir el problema de detención con cinta
en blanco.
Funciones no computables
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...
01
Start
qstop
BB(1,2) = 1
el caso que más se ha estudiado es k=2, ={0,1}
Funciones no computables
01,R
Start
A
01,L
B
11,R
H
11,L
BB(2,2) = ?
•Esta máquina tarda 6 pasos en detenerse; por lo
tanto, BB(2,2)  6.
•De hecho, está demostrado que BB(2,2)=6 (esta
máquina alcanza el máximo).
Funciones no computables
•Es una función que crece más rápido
que cualquier función computable.
•BB(1,2) = 1
•BB(2,2) = 6
•BB(3,2) = 21
•Encontrar MT que batan records de BB
es una labor necesariamente creativa
(pues sabemos que no existe algoritmo
para construirlas!).
•BB(4,2) = 107
•BB(5,2) = desconocido
Mejor hasta la fecha: 47.176.870 (Marxen & Buntrock, 1989)
•BB(6,2) = desconocido
Mejor hasta la fecha: > 1021.132 (Pavel & Kropitz, 2010)
Motivos para la tesis de Church-Turing
Un punto que dejamos pendiente: ¿será razonable
hacer la ecuación “algoritmo=MT” ?
Hay varios argumentos para hacerlo.
•En primer lugar, la intuición que se gana luego de
“programar” varias MT es que se puede hacer
“cualquier cosa” con ellas.
•Además, el poder de cómputo de las MT de Turing
vuelve y vuelve a aparecer, aunque tratemos de
irnos por otros lados.
MT y PDAs “aumentados”
Por ejemplo: puede parecer un poco brusco el salto desde
los LLC y los PDA, a las máquinas de Turing.
Sin embargo:
•Definamos los "autómatas de cola", como autómatas
finitos a los que en lugar de agregarles una pila, les
agregamos una cola.
•Definamos los "2PDA", autómatas finitos a los que en
lugar de agregarles una pila, les agregamos 2 pilas.
Ejr.: cada una de esas clases es equivalente a las MT.
Gramáticas generales
Dijimos que una gramática, en su forma más general,
admitía producciones de la forma
abbacXaYb  bbabXX
Xa  baa | Y
A diferencia de la GLC, en el caso general no hay
restricción sobre el lado izquierdo de las producciones.
Al derivar una palabra, se usan las reglas para ir
reemplazando lo que está a la izquierda por lo que esté
a la derecha.
Gramáticas generales
Ejemplo: una gramática para un lenguaje que no es de
libre contexto.
S  XYZS | 
XY  YX
YZ  ZY
XZ  ZX
Xa
Yb
Zc
Teorema [no veremos la demo.]: un lenguaje es recursivo
enumerable ssi existe una gramática que lo genera.
Otros modelos de cómputo
•Por distintos lados (gramáticas, autómatas con cola,
autómatas con dos pilas, MT) se llega a la misma clase
de lenguajes (el mismo poder de cómputo).
•Al agregar más cosas (más cintas, más pilas, no
determinismo, etc etc), los lenguajes decidibles, los
lenguajes aceptables, las funciones computables,
siguen siendo los mismos.
•No es difícil ver cómo se puede simular un
computador con una MT. Incrédulos, leer
http://appsrv.cse.cuhk.edu.hk/~andrejb/csc3130/notes/09N16.pdf
(o
algún otro texto mostrando como simular random access
machines en MT).
Otros modelos de cómputo
 Todos los otros modelos de computo que se han
inventado, a lo largo del último siglo, han resultado
ser equivalentes (o inferiores) al poder de cómputo
de las máquinas de Turing.
¿Cómo tendría que ser un modelo de cómputo para
sobrepasar a las MT?
 Para empezar, no podríamos simularlo en un
computador, ni en ninguna máquina digital (si se
pudiera, lo podríamos simular en una MT de Turing).
Tesis de Church -Turing
La tesis de Church-Turing (por
Alan Turing y Alonzo Church, su
director de tesis) consiste en la
afirmación de que las MT
reflejan correctamente la noción
intuitiva de algoritmo.
Ojo: ¡¡¡no es un teorema!!! (No podría serlo, pues la
noción de "algoritmo" no tiene otra definición).
•Es una "suposición", validada por los años.
•En informática cuando se dice "existe un algoritmo..."
estamos diciendo "existe una máquina de Turing..."
Hardware y software
Un programa P, (o un algoritmo, o una MT), pueden
ser vistos como la descripción de una máquina.
•Si construimos físicamente la máquina, entonces
lo estamos convirtiendo en hardware.
•Si usamos una máquina para simular el
funcionamiento de P, lo estamos usando como
software.
Hardware y software
Si el programa P es capaz de recibir la descripción de
cualquier algoritmo, y ejecutarlo, entonces corresponde
a una máquina de Turing universal.
•Si lo convertimos en hardware, el resultado es un
computador.
•Si usamos una máquina para simular su
funcionamiento, P es una máquina virtual.
Nótese que como es posible ejecutar P en esa
máquina, la máquina misma es también una MTU:
simula a P, que a su vez ejecuta cualquier algoritmo!
Hardware y software
Moraleja:
Un computador es la implementación
física de una máquina de Turing
universal.
Notas:
•Todo PC tiene memoria finita ; sin embargo está pensado en
términos de memoria ilimitada. De lo contrario, sería un AFD !!
•La arquitectura de los PC usuales no refleja la estructura de
una MTU; la equivalencia es conceptual.
MT y lenguajes de programación
En principio, la forma de demostrar que algo tiene el
poder de las MT es demostrar que cualquier MT
puede ser simulada.
Sin embargo, eso es equivalente a probar que se
puede simular una MT universal .
 Si podemos simular cualquier MT, entonces en
particular podemos simular una MTU.
 Si podemos simular una MTU, la podemos usar
para simular cualquier otra.
MT y lenguajes de programación
Un lenguaje de programación capaz de simular una
MT universal se dice Turing-completo.
Todo lenguaje de programación decente lo es!!!
Turing-completos:
•C, C++, Java, Lisp, Python, Visual Basic....
•Menos obvios: LaTeX, Postscript, el
preprocesador de C++...
MT y lenguajes de programación
 Si X es un lenguaje de programación Turingcompleto, al decir "existe un algoritmo" podríamos
haber dicho "existe un programa en X".
Se desprende que todos los lenguajes de
programación son equivalentes en poder de cómputo:
resuelven los mismos problemas, reconocen los
mismos lenguajes, calculan las mismas funciones.
[Lo que puede haber son diferencias en eficiencia,
legibilidad, portabilidad, etc, etc, etcetc]
MT y lenguajes de programación
Es bueno que un lenguaje sea Turing-completo:
•Si no lo fuera, habría algoritmos que no
podríamos implementar.
El lado malo :
•Los lenguajes Turing-completos heredan la
indecidibilidad: hay muchas preguntas sobre
programas que un programa no puede contestar.
MT y lenguajes de programación
¿Qué significa que “hereden” la indecidibilidad de los
problemas?
•No es difícil hacer una función en Java, digamos
“simulaMT(String M, String w)”, que reciba una
descripción de una MT en el string M, y la ejecute a
partir del input w. [En esencia, simulaMT será una MTU,
pero hecha en Java].
•Supongamos que tenemos una función H(String func,
String args), también en Java, que resuelve el problema
del alto, versión Java:
•func es el código fuente de una función en Java
•args es una cadena de argumentos para esa función.
•H retorna true ssi func(args) termina alguna vez.
MT y lenguajes de programación
Como una MTU puede simular un PC, en particular
puede simular un PC que esté corriendo cualquier
código que se compiló en Java (por ejemplo, H).
Una MT MH podría entonces resolver el problema del
alto:
dados M, w (descripción de una MT y un input,
respectivamente), se los pasa a una MT que simula
la ejecución de
H(simulaMT, [M,w])
Si H da true, MH acepta; si H da false, MH rechaza.
MT y lenguajes de programación
Ni siquiera necesitamos
pasar por las MT:
Ahora ejecutamos:
void funcionRara(String s)
{
if ( H(s,s) )
while ( 1==1 ) { }
}
rara = “void funcionRara(String s) \n { \n \n if
(H(s,s)) \n while ( 1==1 ) { } \n }”;
funcionRara(rara);
•Si H(rara,rara)=true, funcionRara no termina  H miente !
•Si H(rara,rara)=false, funcionRara termina  H miente !
 H no puede existir.
MT y lenguajes de programación
Y no sólo el problema del alto: un montón de problemas
más (el teorema de Rice ya provee muchos):
•Dado un programa P en C, y una palabra w, ¿alguna
vez P escribe w en stdout?
•Dado un documento en PostScript, ¿termina alguna
vez de imprimir?
•Dado un programa P, ¿Cuánta memoria necesitará?
•Dado un programa P, ¿borrará mi disco duro?
MT y lenguajes de programación
No existe algoritmo general para esos problemas.
La idea común es: “los programas no pueden
analizar programas”.
La razón de fondo: las contradicciones de la autoreferencia.
•Para algunas tareas puntuales es preferible usar
lenguajes que no padezcan de estos problemas, y en que
podamos saber de antemano qué usan, qué hacen, etc.
•Pero el precio a pagar es alto: lo que se puede
programar es muy poco!
Complejidad Computacional
(¡un poco!)
Complejidad computacional: recuerdo
Hasta aquí nos ha interesado ver acaso un lenguaje
puede o no ser reconocido (o, equivalentemente,
acaso un problema es decidible o no).
Ahora nos interesa la eficiencia: dado un lenguaje
[problema], ¿cuántos recursos se necesitan para
reconocerlo [decidirlo]?
Recursos:
•Tiempo
•Espacio [memoria]
Complejidad computacional
•Olvidemos lo imposible
(indecidible).
•Dentro de lo posible,
distinguiremos entre lo
tratable (“fácil”) y lo
intratable (“difícil”).
•Ese es el corte
grueso: en realidad hay
una cebolla de muchas
capas.
Indecidibles
Intratables
Decidibles
Tratables
Complejidad computacional: recuerdo
Recordemos lo que en EDA y otros cursos debieron
ver:
•La diferencia en consumo de recursos entre dos
programas puede depender de muchos factores
(hardware, sistema operativo, detalles del código,
optimización al compilar,...).
•Pero para datos suficientemente masivos, la
diferencia crucial para que uno le gane al otro estará
dada por el algoritmo: un algoritmo “rápido” tarde o
temprano le ganará a uno “lento”.
Complejidad computacional
¿En qué sentido “rápido” y “lento”?
•El tiempo que tardan lo vemos en función del
"tamaño" de los datos de entrada, n.
•Ese n puede ser la cantidad de elementos que tengo
que ordenar, la cantidad de números que tengo que
multiplicar, etc, etc.
•Buscamos una cota superior a ese tiempo, en
términos de una función f(n)
 será una garantía de la eficiencia del algoritmo.
Complejidad computacional
1
2
3
4
5
6
7
8
9
10
11
4
1
16
81
256
625
1296
2401
4096
6561
10000
14641
n
4
16
64
256
1024
4096
16384
65536
262144
1048576
4194304
n
n
4
Esa f(n) marca la diferencia!
•Para un mismo n, el tiempo
que tarda el algoritmo puede
variar  consideramos el
peor caso.
•Se piensa en términos
asintóticos, con n grande
(tendiendo a infinito).
Notación big-O
Sean f y g dos funciones no negativas y no decrecientes
sobre los enteros positivos. Escribimos:
f(n) = O(g(n))
y decimos que f(n) es de orden “a lo más”, o orden "big
o" de g(n), si existen constantes c > 0 y M tales que:
f(n)  c g(n)
nM
Es decir, para n suficientemente grande, f(n)/g(n) está
acotado por una constante
 f no crece más que g
Notación big-O
Ejemplos:
•f(n)=1+2+3+...+n es O(n2)
•f(n)=log(n!) es O(n log n)
Ideas:
1+2+3+…+n=n(n+1)/2
n+n+n+…+n= n·n = n2
log(n!) = log(n·(n-1)·(n-2)·····2·1))
= log(n)+ log(n-1)+…+log(2)+log(1)
 log(n)+ log(n) +…+log(n)+log(n)=n·log n
Notación big-O
Algunas cosas que saber:
Si f(n)=O(s(n)) y g(n)=O(r(n)), entonces:
•f(n)+g(n) = O(max{s(n),r(n)})
•f(n)·g(n) = O(s(n)·r(n))
•Exponencial siempre crece más rápido que polinomial.
•Un polinomio crece como su término de mayor grado.
•Algunos órdenes típicos, en orden
(valga la redundancia):
O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(n3) < O(2n)
(constante, logarítmico, lineal, “eneloguene”, polinomial de
distintos grados, exponencial)
Big- y Big-
De manera análoga al Big-O, se define el Big-:
f(n) es de orden “a lo menos”, o orden "big " de
g(n), si existen constantes c > 0 y M tales que:
f(n)  c g(n)
nM
...así que en ese caso tenemos una cota inferior del
crecimiento del tiempo.
Big-: decimos que f(n)=(g(n)) si f(n)=O(g(n)) y
además f(n)=(g(n))
es decir, en ese caso g da el orden exacto de
crecimiento de f
Big- y Big-
(g): funciones que crecen por lo
menos tan rapidamente como g.
g
(g): funciones que crecen con
la misma rapidez que g.
O(g): funciones que no crecen más
rapidamente que g.
Evaluando el orden
¿Cómo evaluamos?
 Si se trata de código, despreciando los detalles y
fijándonos en los ciclos que dependan de n.
•Sentencias de asignación en general son O(1)
•Para una secuencia de sentencias, se toma la suma.
•Para un if/else, se suman el tiempo necesario para evaluar la
condición, y el máximo de los tiempos de sus opciones (lo
mismo para un case).
•Para un for, tomamos el tiempo de ejecución del cuerpo, más
el tiempo requerido para evaluar la condición de término, y
sumamos eso sobre todas las iteraciones del ciclo.
Evaluando el orden
void bubbleSort( float a[], int n )
{
int i,j;
float auxiliar;
for ( i=0; i < n; i++ )
for ( j=n-1; j > i; j-- )
if ( a[j-1]>a[j] )
 O(1)
{
auxiliar = a[j-1];  O(1)
O(1)
 O(1)
a[j-1] = a[j];
a[j] = auxiliar;  O(1)
}
}
O(1)
O(n-i)
 n 1

 n 
 n ( n  1) 
2
O  n  i   O  i   O
O n
2


 i0

 i 1 
 
 bubbleSort es O(n2).
Comparando el orden
Interesa comparar para saber qué algoritmos usar: es
preferible usar un algoritmo rápido, que intentar
“enchular” un algoritmo lento.
Ejemplo: búsqueda en una lista de datos almacenados en
un arreglo.
Algoritmo 1: búsqueda secuencial
Algoritmo 2: búsqueda binaria (requiere que la lista
esté ordenada)
Algoritmo 1 es O(n), Algoritmo 2 es O(log n) :
Comparando el orden
int buscaSecuencial( Tipo a[], int n, Tipo elem )
{
int i;
for ( i=0; i < n; i++ )
if ( elem == a[i] )
return (i);
return (-1);
}
En el peor caso, n vueltas  O(n)
Nota: si no sabemos nada a priori sobre los datos, O(n) es lo
mejor que podemos conseguir: en el peor caso (cuando lo
buscado no está) hay que al menos ver todos los elementos.
Comparando el orden
int buscaBinaria( Tipo a[], int n, Tipo elem )
{
int inicio=0;
int fin=n-1;
int medio=n/2;
while ( inicio < fin )
if ( elem == a[medio] )
return (medio);
else
if ( elem < a[medio] )
fin = medio-1;
else
inicio = medio+1;
return (-1);
}
En el peor caso, log2 n vueltas  O(log n)
Comparando el orden
•Ahí estamos evaluando la complejidad de algoritmos
específicos.
•Nos interesa hablar de la complejidad de problemas
específicos.
Idea: un problema es de dificultad O(f) si conocemos
algún algoritmo O(f) que lo resuelve. [Ojo: es una cota
superior: “tarda a lo más...” ].
El problema es (f) si el mejor algoritmo posible es (f).
Pero:
•Las nociones son imprecisas
•TALF nos permite precisarlas
Complejidad de una MT
•Primero, veamos que también con MT podemos evaluar
complejidad.
•No es tan evidente como en código.
•Conviene analizar un pseudocódigo que describa el
funcionamiento de la máquina, más que la máquina
misma.
Veamos la descripción de un par de MT que reconocen
{0n1n : n  0}.
Complejidad de una MT
•{0n1n : n  0}
Dado un input w
O(n) pasos
•Chequear que w sea de la forma 0*1*
•Mover el cabezal al extremo izquierdo.
•Mientras el cabezal vea 0 ó 1,
O(n) veces
•Si es un 1, rechazar
•Si es un 0
•Cambiar el 0 a 
O(n) pasos
•Avanzar hasta el extremo derecho
•Si no hay un 1 al final, rechazar
•Cambiar el 1 a 
•Mover el cabezal al extremo izquierdo O(n) pasos
•Aceptar
•Es O(n2)
Complejidad de una MT
•{0n1n : n  0}
Dado un input w
•Chequear que w sea de la forma 0*1*
O(n) pasos
•Mover el cabezal al extremo izquierdo.
•Mientras quede algo sin cambiar a $,
O(log n) veces
•Determinar la paridad de la cantidad de 0’s
O(n) pasos
•Determinar la paridad de la cantidad de 1’s
O(n) pasos
•Si las paridades son distintas, rechazar
•Si son iguales, cambiar un 0 por medio a $,
O(n) pasos
y un 1 por medio a $
•Aceptar
•Es O(n log n)
Complejidad de una MT
•{0n1n : n  0}
•Con una MT de dos cintas:
Dado un input w
•Chequear que w sea de la forma 0*1*
•Copiar los 0’s a la otra cinta
•Mover un cabezal al comienzo de los 0’s, el
otro al comienzo de los 1’s
•Avanzar de a un paso, simultáneamente en ambas
cintas.
•Si se acaban antes los 0’s (o los 1’s),
rechazar
•Aceptar
•Todo es O(n); el algoritmo es O(n)
Complejidad de una MT
•{0n1n : n  0}
•Seudo-c:
M(char *x)
{
int n = strlen(x);
if ( n%2 == 0 )
reject;
else
for (int i = 0; i < n/2; i++)
if ( x[i] != 0 || x[n-1-i] != 1 )
reject;
accept;
}
•También es O(n)
Complejidad según modelo de cómputo
No es sólo la diferencia de algoritmos: influye la
diferencia entre modelos de cómputo.
•Por ejemplo, en Java o C podemos acceder
“directamente” a la memoria del arreglo, sin tener
que recorrerlo.
“Un paso” puede significar cosas bien distintas.
C
if (x > 0)
y = 5*y + x;
1-tape TM
(q3, a) = (q7, b, R)
Tamaño de problemas
Otra consideración es el “n”: no siempre es tan
obvio.
•Para multiplicar una lista de números, ¿qué es
determinante: la cantidad de números, la
cantidad de dígitos que cada uno contenga,
ambas cosas, o alguna combinación...?
•En el caso de MT es sencillo: el tamaño del
problema es |w|, donde w es el input.
•Pero: depende de la codificación.
La codificación es parte de la resolución
eficiente del problema.
Clases de problemas
Observación:
•Por lo general en este campo se trabaja con problemas de
decisión (con respuesta sí/no).
•Sin embargo es fácil ver que la idea es aplicable a funciones
computables cualesquiera: contamos la cantidad de pasos que
la MT requiere para calcular la función.
•También se aplica a problemas de optimización (por ejemplo,
encontrar el camino más corto entre dos vértices de un
grafo): los vemos como funciones (el algoritmo entrega una
respuesta, en función del input).
•Dado un problema de optimización, se suele pasar a un
problema de decisión con dificultad equivalente.
Clases de problemas
Diremos que:
Un problema [o lenguaje] es DTIME(f) si existe una
MT estándar (por lo tanto, determinista) que lo
resuelve [o reconoce] en tiempo O(f(n)), donde n es el
tamaño del input.
Ej.:
•El problema de decisión asociado a cualquier LLC
está en DTIME(n3), gracias a CYK.
•El problema de decisión asociado a {0n1n : n  0} es
DTIME(n log n).
Clases de problemas
Insistamos: O( ) es cota superior ; por lo tanto, si

f(n) = O(g(n))
DTIME(f)  DTIME(g)
Una clase importante de problemas es P, formada
por todos los que se pueden resolver en tiempo
polinomial:
 
P   DTIME n
k 0
k
P
Otros ejemplos de problemas en P:
•Multiplicación de matrices
•Ordenar una lista
•Encontrar las distancias más cortas entre los
nodos de un grafo
•Programación lineal
Por lo general se identifica P con los problemas
“tratables”, es decir, “fáciles”.
NP
De manera similar a los DTIME y P, se definen:
•NTIME(f) como la clase de problemas que se
pueden resolver con una MT no-determinista en
tiempo O(f(n)), donde n es el tamaño del input.
• NP 
 
 NTIME n
k
k 0
NP son problemas que pueden ser resueltos en
tiempo polinomial por una MT no-determinista.
NP
Intuición: son problemas en que una solución se
puede chequear en tiempo polinomial.
Pero para encontrarla, ¿cuánto podemos tardar?.
•Vimos tiempo atrás cómo simular una MT no
determinista mediante una MT determinista.
•La reducción que hicimos ahí requería un
aumento exponencial de la cantidad de pasos.
Por lo tanto sabemos que si un problema están
en NP, la solución puede encontarse en tiempo
exponencial.
Clases de problemas
P y NP son las dos clases de problemas más famosas,
pero no son las únicas. De acuerdo a
•el modelo de cómputo (MT, MT no-det., MT paralelas,
computador cuántico...)
•el tipo de restricción (polinomial, exponencial...)
•el recurso que se restringe (espacio, tiempo, canal de
comunicación entre procesadores paralelos,...)
aparece una fauna enorme de clases.
Curiosos, ver http://qwiki.stanford.edu/wiki/Complexity_Zoo
Algunas clases importantes
Reducción polinomial
•Sean R y Q dos problemas de decisión, asociados a los
lenguajes LR1*, LQ2*.
•Sea :1* 2* una función computable tal que
wLR  (w)LQ
decimos que R se reduce a Q (si tenemos  y además
tenemos un algoritmo para Q, obtenemos un algoritmo
para R).
Reducción polinomial
wLP  (w)LQ
Sin perder generalidad, supongamos que (w) es
calculada por una MT M de tres cintas: una de
input (que contiene w, y no se modifica), una de
output (en que sólo escribe (w)), y una de trabajo.
Si para cada w, M sólo requiere usar O(log |w|)
celdas de la cinta de trabajo, entonces decimos que
P se reduce polinomialmente a Q.
Observación: M(w) tarda a lo más una cantidad
polinomial (en |w|) de pasos.
Clases de problemas
•Sea X una clase de problemas (puede ser P, NP, o
cualquier otra), y sea Q un problema.
Decimos que Q es X-duro si para cualquier
problema PX, P se reduce polinomialmente a Q.
Idea: Q tiene (al menos) la dificultad de toda la clase X.
Decimos que Q es X-completo si
•Q es X-duro
•Q  X
X-duros
X-completos
X
Clases de problemas
El problema abierto más importante en informática
teórica (y con enorme relevancia práctica):
¿P=NP?
•Planteado en 1971.
•Es uno de los “problemas del milenio”: hay un
millón de dólares esperando a quien conteste.
•Se conjetura que la respuesta es “no”.
Clases de problemas
Si P=NP:
Si PNP:
NP-completos
NP
P
P
•Nótese que bastaría encontrar un algoritmo
polinomial para un único problema NP-completo
_______, y
automáticamente se tendría P=NP.
•Encontrar un algoritmo polinomial para un problema en
NP que no es completo sólo pasaría el problema a P.
NP-completos
Como se sospecha que P  NP, cuando un
problema es NP-completo es como si tuviera
“licencia para matar”: es un certificado de su
dificultad.
Se asume que es “intratable”: no hay
esperanza de encontrarle solución eficiente.
Como un algoritmo exponencial no es viable,
se recurre a algoritmos aproximados,
probabilísticos, etc.
NP-completos
Ejemplos de problemas NP-completos:
•Programación lineal entera
•Vendedor viajero: dadas n ciudades,
encontrar el camino más corto que pasa
por todas, sin repetir ninguna. Para n =
20, las posibles rutas son 1019.
•División de un conjunto: si tengo n números, ¿puedo
separarlos en dos grupos, que sumen lo mismo?
•Predecir el plegamiento de una proteína.
•Factorizar un número entero.
NP-completos
¿Si nos pasan un problema Q, como demostramos que
es NP-completo?
1. Hay que probar que Q está en NP; eso suele ser
fácil (basta mostrar que se puede chequear una
respuesta en tiempo polinomial).
2. Hay que probar que es NP-duro. Lo que se hace es
tomar un problema que ya se sabe que es NPcompleto, y reducirlo (polinomialmente!) a Q.
 de esa forma, por transitividad, se muestra que todo
problema de NP es reducible a Q.
P y NP completos
•Pero para eso necesitamos tener algún problema NPcompleto a partir del cual empezar a demostrar que
existen otros.
•Idem con P: se necesita algún problema P-completo.
Los problemas “paradigmáticos” de P y NP están
relacionados, y ambos tratan de fórmulas booleanas.
Una fórmula booleana es una expresión lógica que toma
cierta cantidad de variables booleanas (V/F, 1/0,
true/false... usaremos 1/0) y entrega un resultado:
( x  y )  (x )
P y NP completos
Problema de evaluación: dada una fórmula booleana
f(x1,...,xn), y una asignación de valores (x1,...,xn){0,1}n,
¿f(x1,...,xn)=1?
Problema de satisfabilidad: dada una fórmula
booleana f(x1,...,xn), ¿existe una asignación de valores
(x1,...,xn){0,1}n, tal que f(x1,...,xn)=1?
•El problema de evaluación es P-completo.
•El problema de satisfabilidad es NP-completo.
Evaluación de fórmulas booleanas
Problema de evaluación: dada una fórmula booleana
f(x1,...,xn), y una asignación de valores (x1,...,xn){0,1}n,
¿f(x1,...,xn)=1?
¿Cuál es el "tamaño del input" aquí?
El tamaño de la fórmula (su longitud).
En a lo más n pasadas podemos evaluar la fórmula (en
cada pasada vamos calculando una operación).
Por ejemplo, evaluar
f(x,y) = ( x  y )  (x )
con la asignación de valores (x,y)=(0,0):
f(x,y) = f(0,0) = ( 0  0 )  (0 ) = 0  1 = 1
C-Value
 Por lo tanto, el problema de evaluación está en P
(de hecho, es O(n) ). Para ver que es P-completo,
tenemos que mostrar que cualquier problema en P se
puede reducir a él.
En realidad, usaremos una ligera variante: C-Value,
que pide evaluar un circuito booleano:
x
y


( x  y )  (x )

C-Value
C-Value consiste en tomar el circuito booleano sin
variables (o sea, con la asignación inicial ya hecha) y
determinar si la respuesta (el valor que sale del nodo
de abajo) es 1:
0
0
1

0

1

P-completitud de C-Value
•Queremos mostrar que C-Value es P-completo.
•Sea L el lenguaje de un problema cualquiera en P.
•Por lo tanto, existe una MT determinista ML que,
dado un input w, responde acaso wL, y tarda un
tiempo polinomial en dar esa respuesta.
•Reducir L a C-Value significa que, en lugar de echar a
correr ML, podemos construir (de manera eficiente,
polinomial) una instancia de C-Value, y usar C-Value
para responder acaso wL.
P-completitud de C-Value
•Consideremos un input w, |w|=n, y sea (c nk) la cota
para el tiempo que ML tarda en responder acaso wL.
•Podemos hacer un diagrama con la historia completa
del cómputo de ML sobre w; el cabezal de la máquina
lo anotaremos dentro de la celda a la que apunta:

......
  w1/q0

......
 
......
w'1
w2
w3 ...
wn 

......

w2/q3
w3 ...
wn 

......

......
P-completitud de C-Value
2 c nk

......
  w1/q0

......
 
w'1
w2
w3 ...
wn 
......

w2/q3
w3 ...
wn 
......

wn 
......

......

......
 
......
w'1
w2/q3
w3 ...
•Necesitamos a lo más c nk filas, pues al cabo de eso
ML se detiene.
•Necesitamos a lo más 2c nk, pues en c nk pasos el
cabezal no se pudo alejar más que c nk del origen.
c nk
P-completitud de C-Value
Notemos además que en esta tabla, el contenido de
cada celda está determinado por el contenido de tres
celdas en la fila anterior.
a/q1
b
b/q1
a
a
a
b
b
b/q1
a
a
a
•El contenido de cada celda es de la forma x o bien
x/y, donde x, yQ. Podemos codificarlo en binario.
P-completitud de C-Value
•Podemos diseñar un circuito lógico, que llamaremos
STEP, que calcule el estado de la celda a partir de los
estados previos.
a
b/q1
STEP
a
a
•Cada bit de salida es alguna
función de los inputs.
•Por lo tanto, podemos construir
un circuito booleano para cada
bit de salida.
•Reuniéndolos, tenemos STEP.
•Nótese que el tamaño de STEP sólo depende de ML,
no de |w|.
P-completitud de C-Value

…

w1/q0
w2
...
…
STEP STEP STEP STEP
STEP
…

STEP
…
•Entonces en lugar de ejecutar ML, podemos calcular
las sucesivas filas usando STEP.
P-completitud de C-Value

…

w1/q0
w2
…
STEP STEP STEP STEP
STEP

STEP
…
…
¿qF?
...
…
¿qF?
¿qF?
OR
•Después de la última fila podemos agregar un paso que
detecte acaso la celda incluye qF (aceptación), y
haciendo un OR de esos resultados vemos si w se aceptó.
P-completitud de C-Value

…

w1/q0
w2
…
STEP STEP STEP STEP
STEP

STEP
…
…
¿qF?
...
…
¿qF?
¿qF?
OR
Tenemos entonces un circuito booleano de tamaño
|STEP|2 c nkc nk (ergo, polinomial en |w| ) que vale 1 ssi
wML  el problema se reduce a C-Value.
QED
SAT
Volvamos ahora al
Problema de satisfabilidad (a.k.a. SAT): dada una fórmula
booleana f(x1,...,xn), ¿existe una asignación de valores
(x1,...,xn){0,1}n, tal que f(x1,...,xn)=1?
Por ejemplo:
•f(x,y) = ( x  y )  (x )
 Sí existe, x=F, y=F
•f(x,y) = (x  y )  (x )  (y )
 No existe ninguna
SAT
Claramente SAT es NP:
•Podemos "adivinar" una solución correcta (usando el
no-determinismo de la máquina de Turing).
•Luego para chequear que efectivamente es solución,
simplemente evaluamos como antes (y eso era O(n) ).
Lo que queremos ahora es demostrar que además SAT
es NP-duro.
[Este resultado se conoce como teorema de Cook-Levin].
NP
Una forma rápida de dar la idea de la demostración es
usando una caracterización alternativa de NP:
Teo. : Un lenguaje L está en NP ssi es de la forma
L={x : y, |y| |x|k, (x,y)R }
para algún k y algún lenguaje R que está en P.
•Por ejemplo en SAT, el "y" es la solución que
adivinamos, y R es el chequeo de que la solución es
correcta.
NP
Teo. : Un lenguaje L está en NP ssi es de la forma
L={x : y, |y| |x|k, (x,y)R }
para algún k y algún lenguaje R que está en P.
Demostración:
() sea L de esa forma, queremos una MT nodeterminista que decida L en tiempo polinomial.
Fase 1: usamos el no-determinismo
para adivinar y (requiere a lo más
|x|k pasos no-deterministas).
Fase 2: aplicamos MR sobre (x,y).
NP
Teo. : Un lenguaje L está en NP ssi es de la forma
L={x : y, |y| |x|k, (x,y)R }
para algún k y algún lenguaje R que está en P.
Demostración:
() sea L decidido por una MT no-determinista M en
tiempo polinomial, demostrar que es de la forma indicada.
•Sea m = la máxima cantidad de opciones entre las que
elige (no-determinísticamente) M en un paso dado.
•Sea k tal que M tarda nk pasos en decidir x, |x|=n.
•Entonces un cómputo de M con input x queda
determinado por x, y por y{1,...,m}nk, que registra las
decisiones que tomó M en cada "duda".
NP
y{1,...,m}nk registra
las decisiones que
tomó M en una
historia de cómputo
dada.
NP
Teo. : Un lenguaje L está en NP ssi es de la forma
L={x : y, |y| |x|k, (x,y)R }
para algún k y algún lenguaje R que está en P.
Demostración:
() Definimos
R={ (x,y): y es una historia de cómputo con la cual M
acepta x}
•Cumple |y| |x|k
•Cumple que R está en P, pues dados x,y, M se ejecuta
de manera determinista.
•M acepta x ssi y (es decir, una historia) de
aceptación.
QED
NP
Teo. de Cook: SAT es NP-completo.
Demostración:
Sea L un lenguaje NP dado. Queremos demostrar que,
dado x, podemos usar SAT para responder acaso xL.
•Por el teo. anterior, L es de la forma
L = {x : y, |y| |x|k, (x,y)R },
para algún k, y algún R en P.
•Dado un x, aplicamos la construcción que hicimos para CValue, a R. Nos quedará un circuito con inputs y1,..., ym, que
evalúa a 1 ssi (x,y)R.
NP
Teo. de Cook: SAT es NP-completo.
fijo (conocido)
x1
x2
…
1 ssi (x,y)  R
xn
variables
y1
y2
…
ym
reducción de C-Value,
aplicada a R
Usamos SAT para ver si existe algún y
que haga que la respuesta sea 1.
QED
NP-completos
A partir de SAT se demuestra que otros problemas
son NP completos.
cualquier
problema
NP
teorema de Cook
se puede reducir a
SAT
que se puede reducir a
implicará que ese otro
problema es NP-completo
otro
problema
NP
Cada problema NP completo podrá ocupar luego el rol
de SAT en este esquema.
NP-completos
Un caso particular de fórmula booleana consiste en
aquellas de la siguiente forma:
( x1  x 2  x 3 )  ( x 3  x 5  x 6 )  ( x 3  x 6  x 4 )  ( x 4  x 5  x 6 )
•Es un "AND" aplicado a un conjunto de cláusulas.
•Cada cláusula es un OR de 3 términos.
•Cada término es una variable, o su negación.
•3-SAT es el problema de Satisfabilidad (SAT), pero
restringido a expresiones de esta forma.
NP-completos
( x1  x 2  x 3 )  ( x 3  x 5  x 6 )  ( x 3  x 6  x 4 )  ( x 4  x 5  x 6 )
•Es posible transformar cualquier fórmula booleana
en una expresión de este tipo (no veremos cómo).
•La transformación requiere tiempo polinomial.
•Por lo tanto, 3-SAT también es NP-completo:
podemos reducir SAT a 3-SAT.
Ejemplo de reducción: Clique
En un grafo, una clique es un
subgrafo completo (donde todos los
nodos están conectados entre sí).
Por ejemplo, el grafo de la derecha
incluye una clique de tamaño 5.
Problema CLIQUE: Dado un grafo G y un
número k, ¿incluye G una clique de tamaño k?
Teo.: CLIQUE es NP-completo.
Dem: Primero que nada, CLIQUE está en NP:
simplemente adivinamos cuáles son los nodos de la
clique, y verificamos que están todos conectados.
Ejemplo de reducción: Clique
Además, CLIQUE es NP-duro:
veamos cómo reducir 3-SAT a
CLIQUE.
Lo que hay que mostrar es que, dada cualquier instancia
de 3-SAT, podemos construir una instancia de CLIQUE
cuya solución nos de la respuesta al problema de 3SAT. Además, la construcción debe ser "barata".
Sea una instancia cualquiera de 3-SAT. Para
ejemplificar, tomemos
(x 1  x 2  x 4 )  (x 1  x 2  x 4 )  (x 1  x 2  x 3 )  (x 2  x 3  x 4 )
Ejemplo de reducción: Clique
(x 1  x 2  x 4 )  (x 1  x 2  x 4 )  (x 1  x 2  x 3 )  (x 2  x 3  x 4 )
cláusula 2
cláusula 1
cláusula 3
cláusula 4
•Creamos un grafo con un nodo por cada término;
agrupamos (para no perdernos) los de cada cláusula.
Ejemplo de reducción: Clique
(x 1  x 2  x 4 )  (x 1  x 2  x 4 )  (x 1  x 2  x 3 )  (x 2  x 3  x 4 )
•Enlazamos cada término xi con todos los términos de las
demás cláusulas, excepto con los que sean negación de xi
Ejemplo de reducción: Clique
(x 1  x 2  x 4 )  (x 1  x 2  x 4 )  (x 1  x 2  x 3 )  (x 2  x 3  x 4 )
Listo: cada clique de tamaño k corresponde a una forma de
hacer verdadera la fórmula original.
Ejemplo de reducción: Clique
(x 1  x 2  x 4 )  (x 1  x 2  x 4 )  (x 1  x 2  x 3 )  (x 2  x 3  x 4 )
¿Por qué? Veamos:
•Los k nodos de la clique tienen
que estar uno en cada cláusula.
•Usamos esa variable para hacer
cierta la cláusula respectiva. En
este caso, hacemos x1=1, x1=0,
x1=1, x4=0, que es lo requerido
por las cláusulas 1, 2, 3 y 4.
•No aparecerán requerimientos
incompatibles, pues no hay arcos
entre xi y su negación.
Ejercicio:
convencerse.
Ejemplo de reducción: SUBSET-SUM
Problema SUBSET-SUM: Dada una colección de
números naturales a1,...,an, y un entero W, ¿existe un
subconjunto de los números, que sume exactamente W?
Ejemplo:
32, 34, 200, 250, 300, 700, 700, 1400, 1400
W=4482
Respuesta, sí:
4482 = 32 + 250 + 700 + 700 + 1400 + 1400
Teo.: SUBSET-SUM es NP-completo.
Dem: La parte fácil, SUBSET-SUM está en NP:
adivinamos los números que hay que elegir, y sumamos
para verificar que da W.
Ejemplo de reducción: SUBSET-SUM
Para la P-dureza, reduciremos (de nuevo) 3-SAT: dada
una instancia cualquiera de 3-SAT, queremos construir
una instancia de SUBSET-SUM que dé "SI" ssi la de 3SAT da "SI".
Dada una fórmula booleana con n variables y k
cláusulas, creamos 2(n+k) números. Procedemos de la
siguiente forma:
•Primero creamos 2 números por cada variable, que indican
las cláusulas en que participa con y sin negar.
•Además creamos 2 números por cada cláusula, que se usan
"de relleno".
•Más fácil vía ejemplo concreto
Ejemplo de reducción: SUBSET-SUM
(x  y  z)  (x  y  z)  (x  y  z)
Los dos números de x, uno
indicando cláusulas donde sale
x, otro indicando donde sale x.
Idem para y y para z.
Relleno
•Serán 2n+2k números,
de máximo n+k dígitos.
•Un subconjunto que
sume 111444 existe ssi
la fórmula era
satisfacible.
Ejemplo de reducción: SUBSET-SUM
(x  y  z)  (x  y  z)  (x  y  z)
Si un subconjunto suma
111444, tienen que ser 3
números, y verificarán que:
•Para cada variable se escogió
"x" o "-x", pero no ambos (eso
me lo garantizan los 111). Si se
escogió x, hacemos x=1; si se
escogió –x, hacemos x=0.
•Los 444 me garantizan que
para cada columna, sin usar
relleno, la suma fue 1, 2 ó 3:
ergo, al menos una variable
hará verdadera cada cláusula.
Ejercicio (fácil): PARTITION
Problema PARTITION: Dada una colección de números
naturales a1,...,an, ¿puede separarse en dos subconjuntos
que sumen lo mismo?
Hint:
•Reducir SUBSET-SUM a PARTITION.
•Para eso, dados a1,...,an, y W, resolver PARTITION
para a1,...,an, (ai)-2W (agregamos (ai)-2W a la “bolsa”).
•La pregunta es: ¿por qué funciona eso?
Ej. Extra, aún más fácil: hacer la reducción contraria,
de PARTITION a SUBSET-SUM.
Más ejemplos y reducciones entre problemas
sorprendentemente distintos: en cualquiera de los libros!
FIN
Descargar

EDA