Breves Notas sobre

Teora de la Computaci
on
Jorge L. Ortega Arjona
Departamento de Matematicas
Facultad de Ciencias, UNAM
Enero 2008

Indice general
1. El Teorema de G
odel
Lmites en L
ogica

2. La M
aquina de Acceso Aleatorio
Una Computadora Abstracta

15

3. No-determinismo
Un Aut
omata que Supone Correctamente

23

4. M
aquinas de Turing
Las Computadoras M
as Sencillas

31

5. M
aquinas Universales de Turing
Computadoras como Programas

41

6. C
alculo de Predicados
El Metodo Resoluci
on

47

7. El Problema de la Detenci
on
Lo No-Computable

57

8. El Problema de la Palabra
Diccionarios como Programas

63

Prefacio
Las Breves Notas sobre Teora de la Computaci
on presentan en forma
simple y sencilla algunos temas relevantes de Teora de la Computacion. No
tienen la intencion de substituir a los diversos libros y publicaciones formales
en el area, ni cubrir por completo los cursos relacionados, sino mas bien, su
objetivo es exponer brevemente y guiar al estudiante a traves de los temas
que, por su relevancia, se consideran esenciales para el conocimiento basico
de esta
area, desde una perspectiva del estudio de la Computacion.
Los temas principales que se incluyen en estas notas son: El Teorema
de Godel, la Maquina de Acceso Aleatorio, No-determinismo, Maquinas de
Turing, Maquinas Universales de Turing, Calculo de Predicados, el Problema de la Detenci
on y el Problema de la Palabra. Estos temas se exponen
haciendo enfasis en los elementos que el estudiante (particularmente el estudiante de Computacion) debe comprender en las asignaturas que se imparten
como parte de la Licenciatura en Ciencias de la Computacion, Facultad de
Ciencias, UNAM.

Jorge L. Ortega Arjona

Enero 2008

Captulo 1

El Teorema de G
odel
Lmites en L
ogica
A principios de los a
nos 1930s, Kurt Godel, un matematico aleman,
intenta probar que el c
alculo de predicados era completo, es decir, que
se puede obtener mecanicamente (en principio, al menos) una demostracion
de cualquier formula verdadera expresada en tal calculo. Su falla en lograr
esto se corona con el descubrimiento de que tal tarea es imposible: ciertos
sistemas formales, incluyendo la aritmetica, son incompletos en este sentido.
Este descubrimiento impacto al mundo de las matematicas.
Como parte del Programa de las Matematicas para el Cambio de Siglo de
David Hilbert, se esperaba que todas las matematicas, cuando se encontraran
adecuadamente formalizadas en un sistema como el calculo de predicados,
resultaran ser completas. Pero Godel descubre que ni siquiera la aritmetica
es completa. Su ahora famoso teorema establece que en cualquier sistema
solido, consistente y formal que contiene a la artimetica, hay declaraciones
que no pueden ser demostradas; declaraciones cuya veracidad se conoce por
otros medios, pero no por ning
un proceso de decision formal o paso a paso.
Desde el tiempo de Hilbert, una sucesion de investigadores han intentado
formular tal proceso de decision en varias formas. Todos tenan en com
un,
sin embargo, la adopci
on de ciertos axiomas y una variedad de formalismos
para manipular los axiomas mediante reglas para obtener nuevas declaraciones que, dada la veracidad de los axiomas, resultaban ciertas. Uno de
tales sistemas es la teora de las funciones recursivas, que el propio Godel
participo en su desarrollo. Las funciones recursivas son una mas de las descripciones de lo que significa computar.
7

El punto central del metodo de Godel es codificar cada declaracion posible en el c

alculo de predicados, visto como un lenguaje, mediante codigos
numericos especiales conocidos como n
umeros de Godel. Brevemente, el
proceso tiene tres pasos:
Proponer axiomas para el calculo de predicados junto con una regla
de inferencia mediante la cual se pueden obtener nuevas formulas de
formulas iniciales.
Proponer axiomas para la aritmetica estandar en el lenguaje del calculo
de predicados.
Definir una numeracion para cada formula o secuencia de formulas en
el sistema formal resultante.
Utilizando un lenguaje implicativo facil de leer, los axiomas para el calculo de predicados pueden listarse como sigue:
1. yi (F (G F ))
2. yi ((F (G H)) ((F G) (F H)))
3. yi ((F G) ((F G) F ))
4. yi (x(F G) (F xG)) siempre que F no tenga ocurrencia
independiente de x
5. yi ((F G) (yi F yi G))
6. yi (xF (x) F (y)) siempre que y no se cuantifique cuando se substituye
Una vez entendida la notacion anterior, los axiomas parecen razonablemente auto-evientes como la base de una teora de deduccion matematica.
Los smbolos como F , G y H se entiende que representan formulas;
yi representa una cadena arbitraria de variables como y1 , y2 , . . . , yk , todas
universalmente cuantificadas; tal simbolismo de lee para todas yi o para
todas y1 , y2 , . . . , yk . El smbolo representa a la implicacion, y a la
negacion.
Las varias formulas involucradas en los axiomas anteriores pueden o no
contener a las variables que se cuantifican fuera de ellas, pero en cualquier
8

caso, el axioma 4 no puede aplicarse a menos que cada vez que ocurra la variable x en la formula F , debe estar cuantificada dentro de F . El axioma 6 no
puede aplicarse a menos que y no este cuantificada dentro de F (y) (esto es,
la formula que se obtiene al reemplazar todas las ocurrencias independientes
de x en F por y).
Los axiomas por s mismos pueden ser facilmente entendibles. Por ejemplo, el axioma 1 puede leerse como para todos los valores posibles de sus
variables independientes, si F es verdadero, entonces G F . En otras
palabras, una formula verdadera se implica por cualquier formula. El axioma 2 dice que la implicacion es distributiva sobre s misma. Y el axioma 3
sostiene que si ambos G y G se implican por F , entonces F no puede
ser verdadera, es decir, F debe ser verdadera. Como un ejemplo final, el
axioma 4 se puede leer como para todos los valores posibles de sus variables independientes (como siempre), si F G para toda x y si x no tiene
ocurrencias independientes en F , entonces F xG.
Al conjunto anterior de axiomas se debe a
nadir una regla de inferencia
como la siguiente:
Si F y F G, entonces G
Es notorio que esta regla no cae en el mismo nivel que los axiomas, en
un sentido: se pretende que cada vez que se haga una deduccion (esencialmente, una cadena de formulas) y se observen formulas F y F G ambas
ocurriendo como miembros anteriores de la cadena, se puede a
nadir G a la
cadena.
Se entiende como aritmetica estandar simplemente a los Postulados
de Peano para los n
umeros naturales:
1. x (0 = sx)
2. x, y (sx = sy) (x = y)
3. x x + 0 = x
4. x, y x + sy = s(x + y)
5. x, y x sy = xxy + x
6. x x 0 = 0
9

Aqu, s denota la funcion sucesor, la cual para cada n

umero natural x,
arroja a su sucesor x + 1. As, los postulados 1 y 2 afirman, respectivamente,
que:
Cero no es el sucesor de ning
un n
umero natural.
Si los sucesores de dos n
umeros son iguales, entonces esos n
umeros son
iguales.
El resto de los postulados son relativamente faciles de entender. Sin embargo, este primer conjunto de seis postulados requieren complementarse
con el concepto de igualdad. Esto se encuentra plasmado en los siguientes
tres postulados:
1. x x = x
2. x, y, z (x = y) ((x = z) (y = z))
3. x, y (x = y) (A(x, x) A(x, y))
donde A es cualquier formula que tiene dos variables independientes.
As como se ha a
nadido una regla especial de inferencia a los axiomas
para el c
alculo de predicados, se a
nade ahora una regla de induccion:
(P (0)&x(P (x) P (sx))) xP (x)
Esta formula codifica la bien conocida regla de induccion: si un predicado
P es verdadero al substituirse en el el valor 0 y si en cualquier caso P es
verdadero para un n
umero x, P es tambien verdadero para el sucesor de x,
entonces P es verdadero para todos los n
umeros posibles x.
Los 15 axiomas y dos reglas que se han listado hasta aqu son lo suficientemente poderosos para proporcionar un sistema formal para la aritmetica,
en el cual muchas ideas pueden expresarse y verdades comprobarse, que
es tentador imaginar a priori que cualquier verdad aritmetica es no solo
expresable en este sistema, sino tambien demostrable en el mismo.
Habiendo preparado estos axiomas, Godel contin
ua con el siguiente paso
de su demostracion, es decir, asigna un n
umero u
nico a cada formula concebible en el sistema que se ha definido. Hace esto mediante asignar un n
umero
natural a cada uno de los siguientes smbolos basicos:
10

Smbolo
0
s
+

=
(
)
,
x
1

&

C
odigo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Ahora bien, dado cualquier axioma o formula dentro del sistema formal
anterior, es cosa facil revisar la formula de izquierda a derecha, reemplazando
cada smbolo en ella por un n
umero primo elevado a la potencia del codigo
del smbolo. Los primos utilizados para esto son consecutivamente 2, 3, 5,
7, 11, etc. Como ejemplo, considerese el axioma 4 anterior:
x1 + sx11 = s(x1 + x11 )
que tiene el n
umero de Godel:
29 310 53 72 119 1310 1710 195 232 296 319 3710 413 439 4710 5310 597
El n
umero se obtiene de revisar la expresion dada smbolo a smbolo,
convirtiendolo en la potencia prima apropiada. As, x, el primer smbolo,
tiene c
odigo 9; por lo tanto, 2 (el primer primo) se eleva a la novena potencia.
El siguiente smbolo, 1, se convierte en 310 , ya que 3 es el siguiente primo y
10 es su c
odigo.
Notese que el axioma ha sido alterado de su forma original por comodidad para usar las variables de notacion especial propuestas, por ejemplo, el
uso de notacion unaria (consistente en unos consecutivos) como subndices
del smbolo x. Es decir, x1 y x11 son considerados nombres perfectamente
generales como x y y en el axioma 4 de la aritmetica.
11

Como puede verse en el ejemplo anterior, los n

umeros de Godel tienden a ser enormes. Sin embargo, son computables, y dado cualquier entero,
es posible computar la expresion que representa (si la hay) mediante encontrar todos sus factores primos y agruparlos como potencias en el orden
incremental de primos.
En este momento, se puede acceder al centro del Teorema de Godel
mediante considerar el siguiente predicado:
P roof (x, y, z)
Aqu, P roof (x, y, z) es un predicado que tiene la siguiente interpretacion:
x es el n
umero de Godel de una demostracion X de una formula Y (con
una variable independiente y n
umero de Godel y) la cual tiene al entero z
subtituido dentro de s. La demostracion X a la que se refiere aqu puede
considerarse a s misma como una formula a fin de que se tenga un n
umero
de Godel asignado.
Notese que los smbolos basicos a los que los codigos se conectan no
incluyen el smbolo Proof o ning
un otro smbolo de predicado excepto la
igualdad (=). Ciertamente, P roof (x, y, z) es tan solo la forma resumida
para una expresion inmensamente larga con tres variables independientes x,
y y z, o en la notacion de Godel, x1 , x11 y x111 . Esta expresion incluye un
n
umero de procedimientos, incluyendo los siguientes:
1. Dado un entero, se produce una cadena de la cual este es su n
umero
de Godel.
2. Dada una cadena, se verifica si es una formula.
3. Dada una secuencia de formulas, se verifica si es una demostracion
para la u
ltima formula en la secuencia.
Todos estos procedimientos son computables y, como Godel demuestra,
en s mismos reducibles a formulas dentro del sistema formal definido anteriormente. Antes de mostrar como este predicado se usa en el Teorema
de Godel, hay un peque
no detalle que aclarar. Se debe establecer que es
una formula: la definicion que se encuentra en el procedimiento 2 anterior
aportara a una definicion inductiva de una expresion aritmetica propiamente formada y las formas en las cuales tales expresiones pueden legalmente
combinarse mediante conectivas logicas & y , o cuantificadas con y .
12

Por ejemplo, x1 (X11 (x) = X111 (x)) es una formula, pero 1X)x11 =)) no
lo es.
Ahora bien, se puede proceder a considerar un uso muy especial del
predicado bajo consideracion. Supongase que a la formula Y se le alimenta
su propio n
umero de Godel y que se niega la existencia de una demostracion
dentro del sistema formal de la siguiente formula:
xP roof (x, y, z)
Es decir, la formula P roof (x, y, z) significa x es el n
umero de Godel
de una demostracion de la formula obtenida mediante substituir su propio
n
umero de Godel y por su u
nica variable independiente. Consecuentemente,
escribir x al principio de esto es negar la existencia de tal demostracion.
Tal predicado expresable en el sistema formal que se ha construido tiene
un n
umero de Godel. Sin embargo, considerese lo siguiente:
En primera instancia, se tiene la expresion con una sola variable independiente xP roof (x, y, z), que se alimenta con y. Su propio n
umero
de Godel se representa con g.
En seguida, a la propio expresion se le alimenta con su propio n
umero de Godel g, y al substituirlo, se transforma en un predicado sin
variables independientes que no puede recibir mas valores para sus
variables.
Naturalmente, dado lo anterior, la formula resultante tiene ahora un
nuevo n
umero de Godel g .
Teorema de G
odel: xP roof (x, g, g) es verdadero pero no demostrable en el sistema formal de la artimetica.
La demostracion de esto requiere tan solo unas cuantas lneas:
Supongase que xP roof (x, g, g) es demostrable en el sistema,
y sea p el n
umero de Godel de tal demostracion P . Se tiene
entonces que:
P roof (p, g, g)
es verdadero ya que P es una demostracion de G con g substituido por su u
nica variable independiente. Pero, evidentemente,
P roof (p, g, g) contradice xP roof (x, g, g), arrojando la conclusion de que no existe tal demostracion P .
13

La formula xP roof (x, g, g) es ciertamente verdadera porque se ha

establecido la propuesta que hace de s misma: que no tiene demostracion.
Tal demostracion, donde a predicados de dos variables se les da el mismo
valor para sus argumentos, se le conoce como demostracion por diagonalizaci
on, y aparece frecuentemente en la teora de los conjuntos infinitos y
en la l
ogica matematica. Cantor es el primero en usar tal argumento para
demostrar que los n
umeros reales no son contables.
Hay afirmaciones verdaderas que los matematicos intentan demostrar
ahora mismo, pero nunca lo haran? Que tal la Conjetura de Goldbach, que
establece que todo n
umero par es la suma de dos primos? Ciertamente, nadie
ha demostrado esta afirmacion hasta hoy, aun cuando muchos matematicos
creen que es verdadera.
La lucha por formalizar las matematicas en una forma mecanica llevo al
descubrimiento de un problema basico y profundamente enraizado en las
propias matematicas. El descubrimiento se considera a la altura del intento
unos a
nos mas tarde de formalizar los procedimientos efectivos, lo que derivo en el descubrimiento de una inadecuacion basica de las computadoras.
Hay algunas tareas que simplemente son imposibles tanto para las computadoras como para los matematicos.

14

Captulo 2

La M
aquina de Acceso
Aleatorio
Una Computadora Abstracta
El termino maquina de acceso aleatorio (random access machine o RAM)
tiende a tener un doble uso dentro de la computacion. A veces, se refiere a
computadoras especficas con memorias de acceso aleatorio, es decir, memorias en acceso a una direccion es tan facil y sencillo como el acceso a cualquier
otra direccion. Por otro lado, se refiere a un cierto modelo de computo que
no es menos abstracto que, por ejemplo, la maquina de Turing, pero que
esta mas cercana en cuanto a su operacion a las computadoras digitales
programables estandar.
No es de sorprender que la principal diferencia entre las maquinas de
Turing y las RAM (abstractas) recae en el tipo de memoria empleado. Por
un lado, la memoria de una maquina de Turing esta completamente contenida en una cinta, haciendola una especie de maquina de acceso serial. Una
RAM, por otro lado, tiene su memoria organizada en palabras, y cada palabra tiene una direccion. Tiene, mas a
un, un n
umero de registros. El modelo
descrito aqu tiene un registro llamado acumulador (accumulator, o AC).
Como es el caso con las maquinas de Turing, las RAM se definen en
terminos de programas, el tipo de estructuras como la que se muestra en la
figura 2.1, siendo meramente un vehculo para interpretar tales programas.
Como tal, la figura muestra a la RAM equipada con una Unidad de Control
capaz de realizar las operaciones especificadas en el Programa de la RAM,
el cual esta cargado en alg
un sentido. El Programa dicta la transferencia
15

de informacion entre varias palabras de memoria y el acumulador. Tambien

especifica ciertas operaciones sobre los contenidos del acumulador. Finalmente, es capaz de dirigir cual de sus propias instrucciones debe ejecutarse
enseguida.

AC

Unidad de
Control

Programa

Figura 2.1: Una maquina de acceso aleatorio.

Tanto el acumulador como cada una de las palabras de memoria se suponen capaces de contener un solo entero, sin importar su longitud. Aun
cuando la RAM tiene solo un registro, tiene un n
umero infinito de palabras
en su memoria. En la figura se muestra una lnea de comunicacion entre la
Unidad de Control y cada una de sus palabras de memoria. Esto simboliza
el hecho de que tan pronto como una direccion se especifica en el Programa
de la RAM, la palabra de memoria correspondiente a esa direccion se hace
instant
aneamente accesible a la Unidad de Control.
Se conoce una gran variedad de RAM, definidas por varios autores. Sin
embargo, aqu solo se muestra una clase muy sencilla, que es programable en
el lenguaje que se resume en la siguiente tabla. A este lenguaje, se le conoce
con el nombre de lenguaje de acceso aleatorio (random access language,
o RAL).

16

Nem
onico
LDA

Argumento
X

LDI

STA

STI

ADD

SUB

JMP
JMZ

X
X

HLT

Significado
Carga en AC con el contenido de la direcci
on de
memoria X
Carga en AC indirectamente con el contenido de la
direcci
on de memoria X
Almacena el contenido de AC en la direcci
on de
memoria X
Almacena el contenido de AC indirectamente en la
direcci
on de memoria X
Suma el contenido de la direcci
on de memoria
X con el contenido de AC
Resta el contenido de la direcci
on de memoria
X del contenido de AC
Salta a la instrucci
on con etiqueta X
Salta a la instrucci
on con etiqueta X si AC
contiene 0
Alto

Cuando se habla del contenido de la direccion de memoria X, se refiere

al entero contenido actualmente en la palabra de memoria cuya direccion
es X. Para cargar AC indirectamente con los contenidos de la direccion de
memoria X significa tratar a los contenidos de la palabra de memoria como
otra direccion cuyos contenidos seran cargados. La instruccion STI utiliza
la misma clase de indireccion, pero en sentido inverso.
Cuando se escribe un programa RAL, normalmente se numeran sus instrucciones a fin de que las instrucciones de salto (JMP y JMZ) pueden
comprenderse claramente. As, JMP 5 significa que la siguiente instruccion
a ser ejecutada es la instruccion en la direccion 5. JMZ 5 significa ejecutar
la instruccion con direccion 5 siempre y cuando el contenido de AC sea 0;
de otra manera, contin
ua con la siguiente instruccion despues de JMZ.
El indireccionamiento es una caracterstica muy u
til en los programas
RAM. Ambas instrucciones, LDI y STI, utilizan la indirecci
on de la siguiente
manera: LDI X significa primero buscar el contenido de X. Si el contenido
almacenado aqu es Y , entonces la RAM enseguida busca los contenidos de
Y , finalmente cargando el contenido de esa palabra de memoria a AC. Esta
forma de referencia indirecta de memoria tambien ocurre para STI: busca
los contenidos de X, obtiene el entero almacenado ah, por ejemplo Y , y
entonces almacena el contenido de AC en la palabra de memoria Y .
Como en el caso de las maquinas de Turing, no se toma en cuenta la
entrada o salida de la RAM; ya que no se trata de maquinas reales, no hay
razon en tratar de comunicarlas con el usuario. En lugar de esto, un cierto
conjunto inicial y finito de enteros se supone que existe en ciertas palabras
17

de memoria, con el resto conteniendo ceros. Al final de un procesamiento de

la RAM, lo que permanece en memoria se considera la salida.
Una RAM se detiene bajo dos condiciones:
Si durante la ejecucion se encuentra una instruccion HLT, todas las
operaciones cesan y el computo llega a su fin.
Si la RAM encuentra una operacion no ejecutable, entonces se detiene.
Una operacion no ejecutable es aquella cuyos argumentos no hacen
sentido en el contexto de la RAM. Por ejemplo, si una direcci
on tiene
un valor negativo, de modo que STA -8 no tiene sentido. De manera
similar, si se tiene JMP 24 en un programa con 20 instrucciones. Tales
operaciones no ejecutables se supone que no existen en programas
RAL.
A continuacion, considerese un algoritmo que detecta enteros duplicados
en una secuencia A de enteros positivos. Lo enteros se encuentran originalmente almacenados en otro arreglo B, cada uno igual al entero almacenado.
ST OR
1. for i 1 to n do
a) if B(A(i)) 6= 0
1) then output A(i); exit
2) else B(A(i)) 1
Este algoritmo puede traducirse en un programa en RAL como sigue:
ST OR RAL
01.
02.
03.
04.
05.
06.
07.
08.
09.

LDI
ADD
STA
LDI
JMZ
LDA
STA
HLT
LDA

3 / obtiene la i-esima entrada de A

4 / suma un desplazamiento para obtener el ndice j
5 / almacena el ndice j
5 / obtiene la j-esimo entrada de B
9 / si la entrada es 0, salta a 9
3 / si la entrada es 1, obtiene el ndice i
2 / y lo almacena en 2
/ detiene la ejecucion
1 / obtiene la constante 1
18

10.
11.
12.
13.
14.
15.
16.
17.

STI
LDA
SUB
JMZ
LDA
ADD
STA
JMP

5
3
4
8
3
1
3
1

/
/
/
/
/
/
/
/

y la almacena en B
obtiene el ndice i
substrae el lmite
si i = lmite, se detiene
obtinen el ndice (de nuevo)
incrementa i
almacena el nuevo valor de i
regresa a la primera instruccion

El programa ST OR se puede comprender mejor si se refiere a la figura

2.2, en la cual el uso del programa tanto del AC y la memoria se muestra
claramente.

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14

Constante
Respuesta
Indice i
Limite de A
Indice j

1
0
6
9
0
3
4
2
2
0
0
0
0
0

A(i)

B(j)

Figura 2.2: El programa ST OR en memoria.

Las primeras cinco palabras de la memoria contienen las variables y constantes utilizadas dentro del programa. En este caso particular, las siguientes
cuatro palabras contienen un conjunto de 4 enteros que se verifica si estan
19

duplicados. Estas palabras son colectivamente referidas como A, efectivamente, un arreglo. Todas las demas palabras de la memoria, de la direccion
10 en adelante, comprenden al arreglo infinito B, en el cual ST OR coloca
un valor de 1 cada vez que procese un entero de A.
La primera direccion de memoria contiene la constante 1, que el programa ST OR utiliza para incrementar el ndice i. Este ndice (o mas bien, su
valor actual) se almacena en la direccion 3. Un segundo ndice j se almacena
en la direccion 5, y sirve para accesar a los contenidos en B.
Las tres primera instrucciones de ST OR son:
01. LDI 3
02. ADD 4
03. STA 5
Estas instrucciones leen el contenido de la direccion i, suma su contenido
al contenido de la direccion 4, y entonces almacenan el resultado en la direcci
on 5. Especficamente, la instruccion LDI lee el contenido de la direccion
3, y coloca este n
umero en AC. La direccion 4 contiene la constante 9, que
delimita la seccion de memoria de A. El efecto de sumar 9 con 3 en AC es
obtener la tercera direccion en B, es decir, 12. La computadora entonces
almacena este n
umero en la direccion 5. As, ST OR lee 3 como el primer
entero de A y obtiene la direccion del tercer elemento de B.
La siguiente instruccion de ST OR (LDI 5) carga el n
umero almacenado en la tercera direccion de B en AC. Este n
umero tiene valor 0 para la
instruccion 5, de modo que la ejecucion salta a la instruccion 9. Las instrucciones 9 y 10 leen la constante 1 y la almacenan en la tercera direccion de
B: en realidad, sucede que esta es 12, que es donde ST OR coloca el valor 1.
Esto indica que ST OR ha encontrado un 3. Si (dada otra secuencia en A)
ST OR encontrara un 3 mas tarde, tendra un valor 1 en AC cuando llegara
a la instruccion JMZ 9. En tal caso, inmediatamente cargara el valor actual
de i en la direccion 3, lo almacenara en la direccion 2, y se detendra.
La direccion 2 contiene la respuesta cuando ST OR termina. Si es 0,
significa que no hay duplicados entre los enteros de A. Si no, contiene la
direccion en A del entero repetido.
El resto del programa, de la instruccion 11 a la 16, recupera el ndice i de
la direccion 3 y le resta 9 (de la direccion 4) para decidir si ST OR ha llegado
al final de A. Si este no es el caso, incrementa el ndice i y lo almacena de
20

nuevo en la direccion 3 antes de saltar de regreso al inicio del programa, a

fin de revisar al siguiente entero en la secuencia A.
A primera vista, parece que las RAM son mas poderosas que las maquinas de Turing en terminos de las funciones que puede operar, pero esto no
es realmente cierto. Las maquinas de Turing pueden hacer todo lo que las
RAM pueden hacer. Por ahora, es interesante comprobar lo inverso. Puede
parecer obvio, pero las RAM realmente pueden hacer cualquier cosa que
una maquina de Turing puede hacer? Afortunadamente, esto no es difcil
de demostrar. Dada una maquina de Turing arbitraria con una cinta semiinfinita, utilcese la memoria de una RAM para simular la cinta, como se
muestra en la figura 2.3.
Cinta de la maquina de Turing
0

AC
1 Posicion
2
Estado
3
0
4
1
5
1
6
1
7
0
8
1
Memoria de la RAM

Figura 2.3: Una RAM simulando una maquina de Turing.

Dada la correspondencia uno a uno entre las palabras de la memoria de
la RAM y las celdas de la cinta en la maquina de Turing, se requiere ahora
tan solo escribir un programa para la RAM que simule el programa de la
maquina de Turing. Cada quntupla de la maquina de Turing, entonces,
debe remplazarse por un n
umero de instrucciones en RAL, que tengan el
mismo efecto sobre la memoria de la RAM como la quntupla lo tiene sobre
la cinta de la maquina de Turing. Para tal fin, es necesario que el programa
RAM recuerde la posicion de la cabeza lectora/escritora de la maquina
de Turing, as como su estado actual.
21

Debido a su equivalencia con maquinas de Turing y, ciertamente, por

su equivalencia con todas los mas poderosos esquemas computacionales abstractos, las RAM ofrecen una alternativa en el estudio de computos factibles.
Algunas preguntas pueden formularse de manera mas sencilla, y responderse
de igual manera en el marco de tal modelo de computo; de todos los esquemas, es el mas parecido a una computadora digital estandar. Es tambien uno
de los esquemas mas convenientes para expresar computo real, tal y como
lo muestra el programa RAL que se ha examinado aqu.

22

Captulo 3

No-determinismo
Un Aut
omata que Supone
Correctamente
Supongase la siguiente situacion: es de noche, y se encuentra conduciendo
por una ciudad extra
na. Debe llegar a la casa de X en 10 minutos, pero no
tiene la direccion. No puede telefonear a X, pues no conoce su apellido.
Afortunadamente, su automovil se encuentra equipado con un automata
no-determinstico en el panel. Tocando un boton, aparecen cinco letras en
su pantalla:
LFRSB
Aqu, L significa izquierda, F significa de frente, R significa derecha, S es
detengase y B significa hacia atras. Cada vez que llegue a una interseccion, se
presiona el bot
on y se sigue la direccion dada. Eventualmente, se llega a una
interseccion para la cual aparece B: ya ha pasado la casa de X. Ahora debe
dar la vuelta, y presionar el bot
on conforme pasa cada casa. Eventualmente,
aparece una S. Puede ahora tocar a la casa, donde aparece su amigo que le
espera.
Es evidente que esta historia es ficcion, y que no existe en realidad un
automata as. Pero son muy u
tiles en teora. No solo resultan en una cierta
simplificacion de la teora de automatas, sino tambien proponen algunas de
las mas profundas preguntas abiertas en computacion.
Cada uno de los automatas en la jerarqua de Chomsky tiene una version
determinstica y no-determinstica. Aqu, se estudia el modelo no-determinsti23

co de los cuatro modelos de automatas. El primero es el automata finito.

En el diagrama de transicion de estados (figura 3.1) es posible descubrir
una multitud de rutas a partir del estado inicial I y hasta el estado final o
de aceptacion F . Sin embargo, si se pregunta que entradas colocan a este
automata en su estado final, resulta una cierta confusion: algunos estados
tienen dos o mas transiciones que se disparan por el mismo smbolo de entrada. Ciertamente, una entrada como 01011 puede poner a esta maquina en
cualquiera de sus varios posibles estados, uno de los cuales es el estado final.
La definicion de un automata finito no-deteminstico dice que tal entrada
se acepta por la maquina: si el automata puede aceptar una entrada dada,
entonces se considera que el automata acepta la entrada.

0
F

B
0
I

1
0
1

0
0

1
C

A 0

Figura 3.1: Un automata no-determinstico.

En terminos precisos, un automata finito no-determinstico (nondeterministic finite automaton o NFA) consiste de un conjunto finito de estados Q,
un alfabeto finito , y una funcion de transicion . Lo mismo es cierto para
un automata determinstico. Solo la funcion de transferencia es diferente:
: Q P (Q)
donde P (Q) representa el conjunto de todos los subconjuntos de Q. En otras
palabras, cuando el NFA esta en un estado dado y un smbolo se le da como
entrada, entonces resulta un conjunto no vaco de siguientes estados. En el
automata de la figura 3.1, la funcion de transicion mapea el par estadoentrada (I, 0) al conjunto de estados {A, B}.
Si w es una palabra compuesta de letras de , se define (w) como el
conjunto de todos los estados en los que un NFA puede encontrarse en el
24

momento en que el u
ltimo smbolo de w le ha sido dado como entrada. Si
(w) contiene un estado final, entonces w se acepta por el NFA. El conjunto
de todas las palabras aceptadas por un NFA dado se conoce como lenguaje.
Es importante insistir, una vez mas, que esta definicion de aceptar es
equivalente a decir que el automata supone la transicion correcta a cada
paso del proceso. Por ejemplo, la palabra de entrada 01011 podra resultar
en una serie de transiciones como I B I B I C o en otra
serie como I A F C F F . Hasta determinar la aceptacion de
01011 por el automata, sin embargo, solo una secuencia como la u
ltima se
supone que se computa.
Podra suponerse que un automata finito con tal extension de poderes
de suposicion podra aceptar lenguajes mas alla del poder de sus semejantes
determinsticos. Es interesante, pero este no es el caso.
Dado un NFA, por ejemplo, M , se puede describir un automata deter que acepta exactamente el mismo lenguaje que M . He aqu como
minstico M
funciona.
Supongase que M tiene un conjunto de estados Q, un alfabeto y una
un automata con un estado qi por
funcion de transicion . Ahora bien, sea M
como
cada subconjunto no vaco Qi de Q. As, al escribir un estado de M
qi , se esta refiriendo tambien a un conjunto particular no vaco Qi de Q. La
razon de esta construccion algo exotica recae en una simple observacion: aun
si no se puede determinar en que estado estara M despues de una entrada
dada, s se puede determinar el conjunto de estados en los que M puede
posiblemente estar.
Si M pudiera estar en cualquier estado del subconjunto Qi en un momento dado, y si un smbolo se da como entrada, entonces M podra estar
en cualquier estado del conjunto:
[

i , ) =
(Q

(q, )

qQi

. Mediante
La funci
on es en realidad la funcion de transicion para M
i , ) como Qj , una multitud de transiciones en M se expresan
denotar (Q
, como muestra la figura 3.2.
como una sola transicion en M
, es claro que
Dada esta definicion para la funcion de transicion de M

M es determinstico. Para cada estado actual y entrada, hay exactamente un

25

Qi

Qj

Figura 3.2: Muchas transiciones se vuelven una.

solo estado nuevo posible. Si q0 es el estado inicial de M y F es el conjunto
de los estados finales, entonces se define Q0 = {q0 } como el estado inicialTde
. Mas a
teniendo la propiedad que Qk F
M
un, cualquier estado Qk de M
no sea vaco califica como un estado final de M .
acepta L, el lenguaje aceptado por M , sea w una
Para probar que M
palabra arbitraria en L. Si w se compone de los smbolos
w1 , w2 , . . . , wn
pasa a traves de una sucesion de estados
entonces se observa que M
Q 1 , Q 2 , . . . , Qn
donde
i1 , wi ) = Qi
(Q

i = 1, 2, . . . , n

Ahora, Q1 , Q2 , . . . , Qn es tambien una sucesion de subconjuntos de Q,

los estados de M . Se nota facilmente que
Q1 = (q0 , w1 )

Q2 = (q0 , w1 w2 ) . . . Qn = (q0 , w1 w2 . . . wn )

Es decir, conforme la palabra w se da como entrada a M , puede encontrarse en cualquiera de los estados de Qi cuando se lee el i-esimo smbolo.
Qn contiene un estado final de M , y por lo tanto, Qn es un estado final
,
de M . La implicacion inversa tambien se mantiene, si w se acepta por M
acepta el mismo lenguaje que
entonces w tambien se acepta por M . As, M
M , y el resultado queda comprobado.
26

Ya que todo automata finito determinstico (deterministic finite automaton o DFA) es tan solo una clase especial de un NFA, se sigue que cualquier
lenguaje que se acepte por un DFA tambien se acepta por un NFA. Se prueba entonces que los NFA no son mas podersos que los DFA cuando se trata
de aceptar lenguajes. De paso se nota, sin embargo, que para obtener un
DFA equivalente a un NFA dado, se requiere realizar una cantidad de trabajo exponencial para construirlo. En general, el DFA equivalente puede tener
tantos como 2n estados cuando el NFA tenga solo n estados.
Al siguiente nivel de la jerarqua de Chomsky, se encuentra un automata
cuyas versiones determinstica y no-determinstica no son equivalentes en
absoluto. Los automatas de pila no-determinsticos aceptan lenguajes libre
de contexto, pero algunos de estos lenguajes no se aceptan por los automatas
de pila determinsticos.
Por ejemplo, es suficientemente facil probar que el siguiente lenguaje se
acepta por algunos automatas de pila no-determinsticos:
L = {0a 1b 0c 1d : a = c o b = d}
No resulta facil comprobar que un automata de pila no-determinstico
puede aceptar L. Aqu, se puede argumentar intuitivamente al menos la
razon de esto: al procesar la cadena de smbolos 0a 1b 0c 1d , el automata de
pila debe de alguna manera recordar tanto a como b mediante almacenar
informacion acerca de estos valores en su pila. La informacion puede consistir
en s misma de cadenas de ceros
o unos, o algo mas sofisticado. En cualquier
caso, meramente accesar la informacion acerca de a (para comparar a con c)
resulta en una perdida de informacion acerca de b. Esa informacion se a
nade
a la pila despues de la informacion de a, y debe sacarse (es decir, destruirse)
para que el automata pueda recordar a.
Partiendo del argumento anterior (hecho rigurosamente), el automata de
pila no-determinstico es definitivamente mas poderoso que su contraparte
determinstica.
Que sucede con las siguientes computadoras dentro de la jerarqua de
Chomsky, los automatas lineales? Estos dispositivos se parecen cada vez
mas a las maquinas de Turing en todos aspectos excepto uno: la cantidad
de cinta que se les permite utilizar esta limitada por una funcion lineal del
tama
no de la cadena de entrada. En otras palabras, cada aut
omata lineal
acotado tiene asociada una constante k, de modo que cuando un tama
no de
palabra n aparece como entrada en la cinta, se le permite a la maquina el
27

uso de no mas de kn celdas para determinar la aceptabilidad de la palabra.

Ha sido un problema desde hace largo tiempo decidir si un aut
omata lineal
acotado no-determinstico es mas poderoso que uno determinstico. Nadie lo
sabe con certeza.
En lo alto de la jerarqua de Chomsky se encuentran las maquinas de
Turing. Para estos dispositivos abstractos, como para los automatas finitos,
el no-determinismo no a
nade nada a su capacidad de aceptar lenguajes. Dada
una maquina de Turing no-determinstica M , una maquina determinstica
equivalente M se construye como una maquina de Turing universal.
La funci
on de transicion de M se almacena como una secuencia de
quntuplas en una cinta especial de trabajo de M . Para simplificar el argumento, supongase que M tiene solo una transicion no-determinstica y que
tal transicion involucra tan solo dos alternativas, etiquetas 0 y 1:

q 1 , s 1, d1

(0)

q 2, s 2, d2

(1)

(q,s)

Como en el caso de una maquina de Turing universal, M lee la cinta

de M para ver que smbolo esta leyendo M . En una porcion de su cinta de
trabajo, M escribe el estado actual de M . Es entonces una cuestion simple
(y sin embargo, algo complicada de describir en detalle) para M ejecutar
las quntuplas de M para ver si alguna se aplica a la combinacion de smbolo
de entrada actual y estado. Si solo hay uno, todo va bien: M meramente
escribe el smbolo a ser escrito en su version de la cinta de M , cambia al
estado escrito en la seccion de estado de memoria, y mueve (simula mover)
la cabeza lectora/escritora de M en la direccion apropiada.
Pero, que pasa si dos de tales transiciones son posibles? Es aqu donde
difiere de la maquina universal. En una porcion de su cinta de trabajo,
mantiene una cuenta que comienza en el 0 binario y progresa al infinito si
es necesario. El n
umero almacenado en el espacio de cuenta le informa a

M cual de las dos transacciones tomara M . Cada vez que M encuentra el

par estado-smbolo (q, s) en su simulacion de la actividad de M , consulta
su cuenta actual. Si al consultar este n
umero por primera vez, usa tan solo
el primer dgito (0
o 1) para decidir sobre las alternativas. Si consulta la
cuenta una segunda vez, utiliza el segundo dgito, y as contin
ua. Tarde o
temprano, acepta la palabra de entrada a M o consulta la cuenta por el

28

u
ltimo dgito en el n
umero. La aceptacion por M implica la aceptacion por

M . Pero si M alcanza el u
ltimo dgito de su cuenta sin haber aceptado la
palabra de entrada a M , a
nade entonces un 1 a la cuenta y comienza todo
de nuevo para simular M . Si M nunca se detiene, obviamente, tampoco se
detiene M . Pero la aceptacion por M es equivalente a la aceptacion por
M . Lo inverso de estas dos u
ltimas afirmaciones es tambien cierto.
El objetivo de que M mantenga una cuenta es que tarde o temprano
los dgitos de este incremento lento y permanente del n
umero debe coincidir
con una secuencia aceptable de alternativas para las dos opciones (q, s) de
M.
A lo largo de la discusion, se ha permitido solo que el no-determinsmo
resida en la seleccion de transiciones que el automata pueda tomar. En el
caso de las maquina de Turing, hay una segunda manera: mientras se deja
a todas las transiciones como determinsticas, se puede suponer la aparicion
en la cinta de la maquina de Turing no-determinstica de una palabra finita
x en una posicion inmediatamente adyancente a la palabra de entrada w. Si,
en lugar de permitrsele seleccionar entre dos o mas transiciones para una
combinacion dada de estado-smbolo, la maquina de Turing es dirigida para
consultar la palabra x como una parte de su proceso de toma de decisiones,
entonces una maquina equivalente al primer tipo puede siempre construirse.
Esta noci
on particular de no-determinismo es importante al definir la muy
importante noci
on de complejidad en tiempo polinomial no-determinstico.

29

30

Captulo 4

M
aquinas de Turing
Las Computadoras M
as Sencillas
Las maquinas de Turing son los modelos teoricos de computacion mas
sencillos y mas ampliamente utilizados. Demasiado lentas y poco eficientes
como para ser construidas en un dispositivo real, estas maquinas conceptuales, sin embargo, parecen capturar todo lo que significa el termino computaci
on. No solo las maquinas de Turing ocupan el lugar mas alto dentro de la
jerarqua de Chomsky, sino tambien parecen capaces de computar cualquier
funcion que sea computable mediante cualquier otro esquema conceptual de
computo. Mas a
un, las maquinas de Turing son el mas simple de todos esos
esquemas, de funciones generales recursivas a maquinas de acceso aleatorio.
La maquina de Turing es sencilla: una cinta infinita compuesta por celdas discretas se revisa, una celda en cada momento, por una cabeza lectora/escritora que comunica con un mecanismo de control. Bajo este, la
maquina de Turing es capaz de leer el smbolo en la celda actual de la cinta, o reemplazarlo con otro. Similarmente, la maquina de Turing es capaz
de desplazarse sobre la cinta, celda por celda, ya sea a la izquierda o a la
derecha.
Como otras maquina de la jerarqua de Chomsky, las maquinas de Turing
pueden ser tratadas como aceptadores de lenguajes. El conjunto de palabras que causan que una maquina de Turing llegue finalmente a detenerse
se considera como su lenguaje. Sin embargo, como se indica anteriormente,
las maquinas de Turing son mucho mas que esto. En general, se considera a
la funci
on definida por una maquina de Turing M como:
31

Sea x una cadena sobre el alfabeto de la cinta de la maquina M .

Colocando la cabeza lectora/escritora sobre el smbolo mas a la izquierda de
x en la cinta, M comienza en su estado inicial, procediendo el computo sin
interferencia. Si M eventualmente se detiene, entonces la cadena y que se
encuentra en la cinta en ese momento se considera como la salida de M que
corresponde a la entrada x. Ya que M no necesariamente se detiene para
toda cadena de entrada x, M computa una funcion parcial:
f :
donde denota el conjunto de todas las cadenas sobre . Bajo este esquema, toda clase de posibilidades para pueden tomarse. Por ejemplo,
puede usarse como base para la representacion de enteros, racionales,
smbolos alfabeticos, o cualquier clase de objetos que puedan computarse.
Estrictamente hablando, una maquina de Turing es esencialmente lo
mismo que su programa. Formalmente, tal programa M es un conjunto de
quntuplas de la forma:
(q, s, q , s , d)
donde q es el estado actual de M , s es el smbolo que actualmente M lee en la
cinta, q es el siguiente estado de M , s es el smbolo que M escribe en la cinta
para remplazar a s, y d es la direccion a la cual la cabeza lectora/escritora
se mueve relativamente sobre la cinta. Los estados provienen de un conjunto
finito Q, los smbolos del alfabeto finito y los movimientos de la cabeza
de D = {L, R, S} (derecha, izquierda y detente, respectivamente).
El programa de una maquina de Turing, dada una cadena particular a la
entrada, comienza siempre en un estado incial q0 Q y puede detenerse en
un n
umero de formas. El metodo que se utiliza para detener un programa
involucra el uso de estados de detenci
on. Cuando M entra al estado de
detencion q , toda actividad computacional cesa. Naturalmente, q nunca
aparece como un smbolo inicial de las quntuplas de un programa de M .
El programa P para maquina de Turing que se muestra a continuacion
se utiliza para multiplicar dos n
umeros unarios. Bajo esta representacion,
un n
umero m se representa mediante m unos consecutivos sobre la cinta.
Inicialmente, la cinta de P contiene dos n
umeros a ser multiplicados, separados por el smbolo . Finalmente, la cinta de P contiene el producto m n
en forma unaria. Los estados inicial y final se muestran en la figura 4.1.
32

Figura 4.1: Multiplicando dos n

umeros unarios.
Como en otras maquinas conceptuales, hay muchas maneras de representar el programa de una maquina de Turing, siendo la mas directa simplemente listar las quntuplas de P .
M U LT
q0 , 1, q1 , 1, L
q1 , , q2 , , R
q2 , , q3 , , L
q2 , , q2 , , R
q2 , 1, q2 , 1, R
q2 , X, q2 , X, R
q2 , A, Q2 , A, R
q3 , 1, q4 , , L
q3 , X, q9 , X, L
q4 , 1, q4 , 1, L
q4 , X, q5 , X, L
q5 , , q8 , , R
q5 , 1, q6 , A, L
q5 , A, q5 , A, L
q6 , , q7 , 1, R
q6 , , q6 , , L
q6 , 1, q6 , 1, L

q7 , , q7 , , R
q7 , 1, q7 , 1, R
q7 , X, q5 , X, L
q7 , A, q7 , A, R
q8 , , q3 , , L
q8 , 1, q8 , 1, R
q8 , X, q8 , X, R
q8 , A, q8 , 1, R
q9 , , q10 , , S
q9 , 1, q9 , 1, L
q10 , , q11 , , S
q10 , 1, q10 , , R
q10 , X, q10 , , R
q10 , A, q10 , , R

La representaci
on mas comprensible del programa de una m
aquina de
Turing es probablemente un diagrama de transicion de estados. Tal diagrama
puede frecuentemente ser simplificado a
un mas, mediante etiquetar ciertos
estados como moviendose a la izquierda y moviendose a la derecha, y
omitiendo las flechas de transicion de un estado a s mismo cuando el smbolo
33

que se lee se re-escribe y el movimiento de la cabeza se puede inferir con

la direccion asociada a ese estado. La figura 4.2 muestra el diagrama de
transicion de estados para P .

Estado Inicial
0

11
Estado de
detencion

R
1

10

2 b

LX
*

9
L

L
b

L 1

X 3
L

b
L

L 4 X

b R

L 1

L 6

5 L
X
**

8
R

b
1
X R

7
R

Figura 4.2: Multiplicando dos n

umeros unarios.
La primera acci
on de P , al ser confrontado con dos n
umeros unarios a
multiplicar, es moverse una celda a la izquierda desde el 1 m
as a la izquierda
y escribir un asterisco ah, entrando al estado 2. El programa P permanece
en el estado 2, contnuamente moviendose a la derecha hasta encontrar la
primera celda en blanco. En el estado 3, P cambia el 1 justo a este blanco
(estado 3 estado 4) y se mueve a la izquierda hasta encontrar un signo
. Ahora, en el estado 5, entra en un ciclo de tres estados en el que cada 1
a la izquierda del n
umero unario se cambia a un valor A, escribiendose un 1
correspondiente en la primera celda disponible a la izquierda del asterisco. De
esta forma, P escribe una caden de m unos. Cuando P finalmente encuentra
el asterisco, la cadena se ha terminado y P pasa al estado 8, donde cambia
todas las A otra vez a 1 y contin
ua moviendose a la derecha hasta encontrar
un blanco (estado 8 estado 3). Aqu, el ciclo recomienza, el siguiente
1 en la cadena de n unos se borra, y P vuelve a entrar en el ciclo de tres
estados a fin de escribir otra cadena de m unos adyacente a la cadena escrita
anteriormente. De esta forma, n cadenas adyacentes de m unos se escriben,
complentando la formacion del producto m n en forma unaria. En el paso
final de este c
omputo, P borra el asterisco (estado 9 estado 10) y se
mueve a la derecha, borrando todos los smbolos (lo que se denota con )
hasta encontrar el primer caracter blanco. Entonces se detiene.
Las maquinas de Turing fueron originalmente descritas por Alan Tu34

ring, uno de los fundadores de la computacion moderna. Turing concibio su

maquina a mediados de los 1930s en un esfuerzo por obtener en los terminos mas simples posibles lo que significa que un computo proceda en pasos
discretos. Turing pensaba que su maquina era el modelo teorico concebible mas poderoso, cuando observo que era equivalente a varios esquemas
conceptuales de c
omputo. Otro factor que le dio confianza en esta tesis fue
la robustez de las maquinas de Turing. Sus alfabetos, conjuntos de estados
y cintas pueden cambiarse radicalmente sin afectar el poder de la clase de
maquinas que se obtenan.
Por ejemplo, el alfabeto de una maquina de Turing puede contener tan
solo dos smbolos, y a
un as, computar cualquier cosa que otros esquemas
con alfabetos mas grandes pueden computar. El n
umero de estados puede
reducirse tambien a solo dos, sin alterar su potencia. Naturalmente, hay
una relacion entre el n
umero de estados y el tama
no del alfabeto: dado un
programa P arbitrario para una maquina de Turing empleando m estados
y n smbolos, un programa basado en dos smbolos que imite a P debe, en
general, tener muchos mas que m estados. Similarmente, un programa con
dos estados que imite a P debe tener muchos mas que n smbolos.
Una de las caractersticas mas robustas de las maquinas de Turing es la
variacion en el n
umero y tipo de cintas que puede tener, lo que no afecta su
poder de c
omputo. Las maquinas de Turing pueden tener cualquier n
umero
de cintas, o pueden arreglarselas con tan solo una cinta semi-infinita. Esta no
es mas que una cinta infinita que ha sido cortada a la mitad, por as decirlo.
Si se utiliza la mitad derecha, entonces no se le permite a la maquina de
Turing moverse mas all
a de su celda mas a la izquierda.
Un programa de una maquina de Turing multicinta no es ya una secuencia de quntuplas, sino un conjunto de (2 + 3n)-tuplas, donde n es el n
umero
de cintas utilizadas. Las intrucciones de tal programa tienen la siguiente
forma general:
q, s1 , s2 , . . . , sn , q , s1 , s2 , . . . , sn , d1 , d2 , . . . , dn
donde q es el estado actual, y s1 , s2 , . . . , sn los smbolos que actualmente se
leen (por medio de n cabezas lectoras/escritoras) de las n cintas. Bajo estas
condiciones, esta (2 + 3n)-tuplas hace que la maquina entre en el estado
q , escriba los smbolos s1 , s2 , . . . , sn en sus respectivas cintas y mueva
las cabezas en las direcciones d1 , d2 , . . . , dn , donde cada di puede tomar los
valores L, R y S, como se describe antes en la maquina de Turing de una
sola cinta.
35

Aun cuando las maquinas multicinta no pueden computar aquello no

computable por una maquina de una sola cinta, sin embargo, pueden computar de una manera mucho mas eficiente. Por ejemplo, dada la tarea de formar
el producto de dos n
umeros unarios, existe un programa para una maquina
de tres cintas que lo realiza en aproximadamente n m pasos. El programa
que se presenta anteriormente requiere de n2 m2 pasos.
Finalmente, se demuestra que una maquina de Turing con una sola cinta
puede hacer todo lo que una maquina con n cintas. Mas precisamente, se
muestra que dado el programa M para una maquina de Turing de n cintas,
hay un programa P para una maquina de Turing con (n 1) cintas que
hace precisamente lo mismo. La construccion basica puede re-aplicarse para
construir un equivalente con (n 2) cintas, y continuar as hasta que finalmente resulta una maquina de Turing con una sola cinta y equivalente a M .
Por simplicidad, supongase que M es una maquina de Turing con dos
cintas. Denotando ambas cintas como T 1 y T 2, se selecciona una celda arbitraria en cada una de ellas como la celda 0, y el n
umero de celdas a izquierda
y derecha de estas celdas 0 se consideran numeradas con valores enteros positivos y negativos, respectivamente (figura 4.3).

T1

4 3 2 1 0 1 2
0 1 1 0 1 0 0

T2

4 3 2 1 0 1 2
1 1 0 0 1 0 1

3 4 5 6 7
1 0 0 0 0

3
1

4 5
1 0

6 7
0 0

Figura 4.3: Las dos cintas de M .

En una nueva cinta, se numeran las celdas en pares 0, 0, 1, 1, etc. colocando el smbolo de la i-esima celda de T 1 en la primera celda del i-esimo
par, y colocando el smbolo de la i-esima celda de T 2 en la segunda celda
del i-esimo par (figura 4.4). Es conveniente suponer que el alfabeto en la
36

cinta de M consiste solo de n

umero binarios 0 y 1. Las posiciones de las dos
cabezas lectoras/escritoras se indican mediante los smbolos A y B. Estos
smbolos sirven para indicar 0 y 1, respectivamente, es decir, cual cabeza (1
o 2) representan se mantiene por la maquina de Turing M que se encuentra
en consturccion.

3 3 2 2 1 1 0 0 1 1 2 2
0 1 A 0 1 0 0 1 B 0 0 0

Figura 4.4: Juntando las dos cintas en una.

La idea general tras la construccion de M es obtener una sola cabeza
lectora/escritora que imite las cabezas de M mediante alternar entre los dos
marcadores. Cada marcador, por lo tanto, se mueve dos celdas a la vez ya que
dos celdas adyacentes en las dos cintas originales de M en M se encuentran
ahora separadas por dos celdas en M . La nueva maquina de Turing M se
especifica en terminos de un diagrama de transicion de estados que tiene
dos mitades simetricas. En una mitad (figura 4.5), el marcador de lectura
y escritura para la cinta 1 se supone que se encuentra a la izquierda del
marcador de lectura y escritura para la cinta 2. Si durante la simulacion de
M , los dos marcadores de M se cruzan, una transicion toma el control de
la primera mitad a la segunda; aqu, el marcador de la cinta 1 se supone que
se encuentra a la derecha del marcador de la cinta 2.
El primer paso en la operacion de M es decidir cual octupla de M debe
aplicarse en seguida:
q, s1 , s2 , q , s1 , s2 , d1 , d2
Dado que se supone que M se encuentra en estado q, se asigna el mismo
estado a M , y se entra a una porcion del diagrama de transicion de estados que parece un
arbol de decision. La cabeza lectora/escritora de M se
encuentra leyendo actualmente el marcador izquierdo (figura 4.5).
En este diagrama y en los subsecuentes, se introducen algunas convenciones por simplicidad: si no aparece un smbolo a la mitad de una transicion
(flecha), meramente se re-escribe el smbolo al principio de la transicion. Un
estado etiquetado L
o R significa movimiento a la izquierda y movimien37

A
R

A
B

q
B

A
L L B
L

A
B

A
B

R R
B
L

Al siguiente
diagrama

Figura 4.5: Leyendo los dos marcadores.

to a la derecha, respectivamente. Es decir, M mantiene en movimiento
su cabeza lectora/escritora en la direccion indicada, permaneciendo en ese
estado hasta que se encuentra con un smbolo en una de sus transiciones actuales. Las transiciones con dos smbolos a su inicio en realidad representan
dos transiciones, una por cada smbolo.
La maquina M primero pasa a uno de sus dos estados de movimiento a la
derecha dependiendo si el marcador de la derecha es A (0) o B (1). Contin
ua
moviendose a la derecha hasta encontrar un marcador de la derecha. Aqu se
hace una decision similar, y la cabeza ahora se mueve de regreso al marcador
izquierdo antes de una transicion que sale del diagrama.
En este punto hay suficiente informacion para especificar que transicion
se simula por M . Los smbolos s1 y s2 se conocen. Se representan por los
valores (A
o B) de los dos marcadores. El diagrama que maneja la escritura
de s1 y s2 , as como los movimientos de los marcadores indicados por d1 y
d2 tiene una estructura muy sencilla (figura 4.6).
En el marcador de la izquierda, M reemplaza A o B por una version
alfabetica del smbolo s1 , y entonces se mueve a la derecha hasta encontrar
el marcador de la derecha. Este marcador se reemplaza por una version alfabetica de s2 , y la cabeza de M regresa al primer marcador, reemplazandolo por el correspondiente smbolo numerico. Entonces, M se mueve un paso
en la direccion d1 y verifica si la celda actual contiene una A o una B. Si
as es, los marcadores estan a punto de cruzarse: una trasicion apropiada
38

A s 1 R
A s 2 L
R
L
B
B
A B
01
d1
A
B

0A L
1 B

A
B

d2
0 A R
A 0 d2
R
1 B
B 1A
B

d1
s

s
Cruce

Cruce

Figura 4.6: Escribiendo y moviendo los marcadores.

lleva entonces a M a la otra mitad de su diagrama, aquel en el que el marcador 1 esta a la derecha del marcador 2. Naturalmente, hay una transicion
correspondiente a este estado del estado correspondiente en la otra mitad del
diagrama. En cualquier caso, M hace otro movimiento en la direccion d1 ,
reemplazando el smbolo numerico en esta celda por su contraparte alfabetica. As, el marcador de la izquierda se ha movido dos celdas en la direccion
d1 .
En seguida, M realiza la operacion correspondiente en el marcador de
la derecha y finalmente regresa al primer marcador. Tan pronto como este
marcador se encuentra, M pasa por una transicion que lo lleva fuera del
diagrama anterior. En que estado entra M enseguida? Entra a q un estado
prestado de M de la misma manera en que q esta tambien prestado. Ahora
M esta lista para pasar por otro arbol de decision de estados como el primer
diagrama.
Adem
as de mostrar que las maquinas de Turing con n cintas no son mas
poderosas que las maquinas con una sola cinta, esta construccion resulta
muy u
til para la simplificacion de mucho de la teora de la computacion
mediante permitir confinar la discusion en cuanto a lo que las maquinas de
Turing con una sola cinta pueden o no pueden hacer. Por ejemplo, se puede
usar una maquina de tres cintas para simular un dispositivo que parece mas
poderoso. Al convertir esta maquina de tres cintas en su equivalente de una
cinta por los metodos expuestos aqu, se puede obtener una maquina de
Turing con una sola cinta que realiza la simulacion del dispositivo.

39

40

Captulo 5

M
aquinas Universales de
Turing
Computadoras como Programas
Las maquinas de Turing se describen como un tipo de computadora abstracta. Sin embargo, tal terminologa puede ser en ocasiones equivocada, ya
que las maquinas de Turing normalmente se definen para resolver problemas especficos, y no son programables en el sentido com
un de la palabra.
Es cierto que, si se piensa en una maquina de Turing solo en terminos de
su hardware, es decir, en la cinta, la cabeza lectora/escritora, la unidad de
control, y demas partes, entonces es razonable distinguir entre una maquina
de Turing y los programas que se ejecutan en ella. Tales programas pueden
darse como entrada a la maquina de Turing en forma de quntuplas.
En un sentido, la descripci
on abstracta de una maquina de Turing programable ya se ha realizado. Se le conoce como Maquina Universal de Turing (Universal Turing Machine), y fue inicialmente definida por el propio
Alan Turing en los a
nos 1930 como un modelo abstracto de un dispositivo
de computo del tipo mas general que pudo imaginar.
Una maquina universal de Turing (figura 5.1) tiene un programa fijo
permanentemente grabado en su unidad de control. Este programa simula
la acci
on de una maquina de Turing arbitaria (o un programa) mediante leer
el programa en una cinta y simular su comportamiento en otra.
La maquina universal de Turing U que se describe aqu normalmente
cuenta con dos cintas. La cinta 1 contiene una lista de quntuplas que definen
41

Cinta 1

Programa de T

Unidad de
Control de U

Cinta 2

Cinta de T

Figura 5.1: Una maquina universal de Turing.

a una maquina de Turing T , y la cinta 2 se encuentra en blanco. En esta
u
ltima cinta, U simula la accion de T : las apariencias inicial y final de la
cinta 2 son identicas a las que resultaran si T hubiera operado directamente
en ella.
Se sabe que una maquina de Turing con dos cintas puede simularse mediante una maquina de Turing de una sola cinta, y esta observacion se aplica
con la misma intensidad a las maquinas universales de Turing. En otras palabras, dada la contruccion de U , sera una cuestion sencilla la construccion
de una maquina universal de Turing de una sola cinta U 1 que la simulara.
El programa fijo que habita en la seccion de control de U es realmente
analogo a un interprete de software en una computadora digital. Se divide
en dos secciones:
1. Dados el estado actual de T y un smbolo de entrada, encuentra la
quntupla (q, s, q , s , s) en la descripcion de T que aplique.
2. Registra el nuevo estado q , se escribe el nuevo smbolo s en la cinta
2, se mueve la cabeza 2 en la direccion d, se lee el nuevo smbolo en la
cinta 2, y se registra junto con q .
La maquina universal U espera un formato particular para la descripcion
del programa de T . Las quntuplas de T y todos los smbolos de la cinta de T
usan el alfabeto binario. As, si T tiene n estados, entonces n
umeros binarios
de k bits se utilizan para indexar los estados de T , donde k = logn. Dados
42

dos movimientos basicos de las cintas, izquierdo (igual a 0) y derecho (igual

a 1), cada quntupla puede listarse como un n
umero binario de (2k + 3)
bits. Las quntuplas se separan por los caracteres X y Y como marcadores
de lmites a ambos lados de las quntuplas de T . En la quntupla que se
muestra en la figura 5.2, los bits se
nalados con q y s representan el estado
actual y smbolo de entrada de T , y q y s representan el nuevo estado y
en nuevo smbolo de T , mientras que d representa la direccion en la que la
cabeza de T se debe mover.
Y

X 0/1

0/1 0/1 0/1

q

0/1 0/1 0/1 X

q

Figura 5.2: Un programa a ejecutarse.

Ls figura 5.3 muestra una porcion del programa interprete de U , en forma de un diagrama de transicion de estados. Se ha compactado el diagrama
mediante designar cada estado para moverse a la derecha (R) o a la izquierda
(L); toda transicion de salida de esos estados (y posiblemente, retornando
a ellos) involucra el movimiento de la cabeza de U en la direccion correspondiente. Muchas transiciones por las que pasa U en este y subsecuentes
diagramas no se muestran. Una transicion perdida simplemente significa
que U permanece en el mismo estado, moviendose de acuerdo con la direccion del estado y escribiendo cualquier cosa que lea. El proposito de esta
porcion que se muestra del diagrama de U es localizar la siguiente quntupla
a ejecutarse mediante encontrar sus primeros dos elementos, el estado q y el
smbolo s.
La maquina U utiliza (k 1) segmentos de bit de la cinta 1 inmediatamente a la izquierda del marcador Y izquierdo como espacio de trabajo
para registrar la cinta de T y el smbolo de entrada. Dado que una etiqueta
de estado q y un smbolo s ocupan este espacio, el programa para localizar
q/s es facil de describir. Con la cabeza lectora/escritora 1 en el marcador
Y de la izquierda, U inicia el estado con la transicion de Inicio. Revisa
hacia la izquierda, cambiando cada 0 por A y cada 1 por B hasta encontrar
un caracter blanco b. Entonces se mueve a la derecha, cambiando el primer
smbolo no-blanco que encuentre a 0 o 1 dependiendo de si el smbolo era
una A o una B. Entonces, se mueve a la derecha, buscando una coincidencia
con ese smbolo. El primer bit 0 o 1 encontrado dispara ya sea un retorno
al mismo ciclo de coincidencia o regresa al estado de inicio, dependiendo
43

R
1
0

0
A
Y

A la siguiente porcion

Inicio
B

A
b

B
A

b
L

A,B

A
0,1

Alto

R 0

Figura 5.3: B
usqueda de la quntupla actual.
si se ha encontrado una coincidencia. En cualquier caso, la porcion q/s del
primer smbolo no coinciden con la q y la s almacenados en el espacio de
trabajo. En tal caso, U se mueve a la derecha a la primera X y entonces
re-entra al estado inicial, donde cambia todos los ceros y unos entre esa X
y el extremo final izquierdo del espacio de trabajo, a A y B respectivamente. Entonces U intenta hacer coincidir la q y la s en su espacio de trabajo
con la siguiente quntupla. Finalmente, U tiene exito, pasando mediante una
transicion al siguiente diagrama, o deteniendose por no encontrar ninguna
coincidencia. En tal caso, T tambien se detendra bajo la convencion usual
para las maquinas de Turing. La figura 5.4 muestra la cinta 1 despues de
que U ha encontrado una coincidencia para q y s en la segunda quntupla.
q
0

s
1

Espacio de
trabajo

B A

Primera quintupla

Segunda quintupla

Figura 5.4: U localiza la quntupla.

La segunda porcion del programa de U registra el nuevo estado q en el
espacio de trabajo, y mueve la cabeza lectora/escritora 2 de acuerdo con la
quntupla actual de T . Entonces, registra el nuevo smbolo s en el espacio
de trabajo junto a q en la cinta 1. En la figura 5.5, los estados representados en forma cuadrada indica movimientos de la cabeza sobre la cinta 2.
44

Correspondientemente, los ceros y unos subrayados indican smbolos leidos

o escritos en la cinta 2.

L
A

0/1

0
Del diagrama anterior

0
L
1

A
R
B

0/1
R

A
L
B

Al Inicio

0
R

L
B

Figura 5.5: Registrando el nuevo estado y moviendo la cabeza de T .

Esta parte del programa de U se invoca cuando la primera porcion ha
localizado la quntupla cuyo componente q/s coincide con el contenido del
espacio de trabajo. Tal componente ha sido re-escrito en terminos de A y B,
pero el componente q /s a
un existe como una cadena de ceros y unos. Esta
porcion del programa de U comienza con la cabeza 2 justo a la derecha del
marcador izquierdo Y .
Revisando hacia la derecha, los primeros smbolos binarios que U encuentra pertenecen a el siguiente estado q . Estos smbolos se copian uno a
la vez, en terminos de A y B, en el espacio de trabajo. Cuando esta seccion
del programa de U ha terminado de copiar q , enseguida encuentra el u
nico
smbolo binario de s en la quntupla de T . La maquina U copia s como
una A o una B en la u
ltima celda, la que se encuentra mas a la derecha del
espacio de trabajo, revisando hacia la derecha de la quntupla para recoger
el u
ltimo smbolo, que corresponde a d.
En la figura 5.6 se muestra la cinta 1 en este momento de la operacion
de U . Cuando U retorna al espacio de trabajo, sin embargo, encuentra que
se ha terminado el espacio: encuentra el marcador Y . En este punto, U
recuerda el valor de d mediante encontrarse en la parte superior o inferior
de su diagrama de estados. En cualquier caso, U revisa hacia la izquierda
a fin de recoger el smbolo s como una A o una B, convierte este en el
correspondiente 0
o 1, y lo escribe en la cinta 2 tal y como T lo hara.
Finalmente, U mueve la cabeza 2 a la izquierda (en la parte superior del
diagrama) o a la derecha (en la parte inferior del diargrama), como lo hara
45

T , y entonces lee el siguiente smbolo de la cinta 2. Reemplaza s en el

espacio de trabajo, U se recorre hasta el marcador Y y regresa a la porcion
del programa de la figura 5.3.

Espacio de
trabajo

B A

Primera quintupla

X A

B A

B B

Segunda quintupla

Figura 5.6: Para que lado se mueve la cabeza de T ?.

Para iniciar a U al principio de la ejecucion del programa de T , es necesario colocar la cabeza 1 sobre el marcador Y izquierdo. La cabeza 2 se
coloca sobre la celda inicial de la cinta de T . El espacio de trabajo debe
inicializarse tambien mediante colocar una cadena de k bits para el estado
q0 (el estado inicial de T ) junto con el smbolo que se lee inicialmente en la
cinta 2. Entonces, el programa de U hace el resto.
La tesis de Turing es un paralelo muy cercano a la tesis de Church, en
cuanto a declarar que cualquier cosa que razonablemente podra significar un
procedimiento efectivo se captura por un esquema computacional especfico, en este caso, las maquinas de Turing. Una maquina universal de Turing
incorpora la tesis de Turing de una sola vez, por decirlo de alg
un modo, mediante representar simultaneamente todas las maquinas de Turing posibles
y (por la tesis de Turing) todos los procedimientos efectivos. Lo hace en un
nivel abstracto, de una manera muy parecida a como una computadora digital de proposito general representa todos los posibles programas para ella
misma. Su propia existencia es un reto para explorar el rango de programas
posibles; que puede hacer y que no puede hacer.
En la teora de la computacion, la nocion de las maquinas universales
de Turing sirve como una aproximacion para responder algunas preguntas
concernientes a la existencia de procedimientos efectivos. Por ejemplo, el
problema de la detencion (halting problem) pregunta si hay un procedimiento
efectivo que decida, para cada par posible (T, t), si T finalmente se detiene
en t. En lugar de construir tal procedimiento para todos los pares (T, t),
es tan solo necesario construir uno para (U, t), ya que t puede inicialmente
contener T , y por lo tanto, U se detiene si y solo si T se detiene.

46

Captulo 6

C
alculo de Predicados
El Metodo Resolucion
El c
alculo de predicados es uno de los lenguajes mas poderosos conocidos
para la expresion de ideas y pensamientos matematicos. Ha influenciado a
la Computacion directamente a traves de la invencion de los lenguajes de
programacion como LISP, e indirectamente a traves de las teoras de la
computacion que dependen de el.
Como un ejemplo simple del poder expresivo del calculo de predicados,
considerese el conocido problema del lobo, la cabra y el heno: un hombre
desea llevar a un lobo, una cabra y una paca de heno al otro lado de un
ro. Para ello, cuenta con un bote de remos, pero este es demasiado peque
no, tanto que solo puede transportar a alguno de los tres seres ademas
de s mismo. El problema es que no puede dejar al lobo y a la cabra en una
sola ribera mientras cruza el ro, ya que el lobo se comera a la cabra. De
manera similar, no puede dejar a la cabra con el heno, ya que la cabra se
comera el heno.
Muchas configuraciones posibles pueden utilizarse que combinan al hombre, el lobo, la cabra y el heno en su travesa por el ro. Todas ellas pueden
representarse mediante un solo predicado P . Es en realidad una funcion de
verdad, que cuenta con cuatro argumentos: m, w, g y c, los cuales toman
valores binarios. Por ejemplo, m = 1 significa que el hombre esta en la ribera
inicial, mientras que m = 0 significa que esta el otro lado. Una convencion
similar puede considerarse para w (el lobo), g (la cabra) y c (el heno). El
predicado se escribe funcionalmente como:
47

P (m, w, g, c)
y tiene una intepretacion muy especfica: para cada posible combinacion de
valores de las cuatro variables logicas, P es verdadero para estas variables
si y solo si la configuracion correspondiente puede realizarse sin que el lobo
se coma a la cabra ni que la cabra se coma el heno. Este ejemplo se vuelve
a toma mas adelante, para plantear su solucion.
El interes de la Computacion en el calculo de predicados ha sido explotar
su poder de expresividad para comprobar teoremas. En el campo de la Inteligencia Artificial, se han hecho varios intentos para construir programas
que puedan comprobar teoremas automaticamente. Dado un conjunto de
axiomas y una tecnica para derivar nuevos teoremas a partir de teoremas
comprobados, podra uno de estos programas comprobar un teorema particular que se le provea? Algunos intentos iniciales fallaron porque no haba
una tecnica lo suficientemente eficiente para derivar nuevos teoremas. Hasta
que en 1965, J.A. Robinson, de la Universidad de Syracuse, descubrio una
tecnica llamada resolucion (resolution). No solamente resolucion permite
frecuentemente la derivacion de teoremas, sino tambien fue la base de la
quinta generacion de computadoras, las cuales se esperaba dedicaran su
tiempo a comprobar teoremas. Estos teoremas se consideran como problemas de recuperacion y deduccion de hechos sobre bases de datos. De hecho,
el problema de que el hombre exitosamente logre cruzar con el lobo, la cabra
y el heno puede expresarse como un teorema.
Sint
acticamente, el calculo de predicados puede definirse recursivamente
como cadenas de smbolos que siguen una manera particular de construccion:
tal y como se define el calculo proposicional.
Los bloques basicos de construccion de formulas en el calculo de predicados son los smbolos individuales. En la aproximacion algo informal que
se presenta aqu, las letras may
usculas denotan predicados mientras que las
min
usculas indican funciones y variables. Se entiende que si se requieren mas
predicados, funciones o variables, es posible utilizar la subscripcion de las
letras. Otra convencion utilizada es escribir los n
umeros en su forma com
un,
en lugar de escribirlos en notacion unaria.
Adem
as de los smbolos alfabeticos, se requieren parentesis, y una colecci
on de operadores l
ogicos estandar como , , y , as como otros dos
smbolos muy peculiares dentro del calculos de predicados: los cuantificadores existencial () y universal ().
48

Un termino se define recursivamente como sigue:

1. Un termino es una variable.
2. Si f es una funci
on de n argumentos, y x1 , x2 , . . . xn son terminos,
entonces f (x1 , x2 , . . . xn ) es un termino.
Una formula at
omica se define como cualquier predicado cuyos argumentos son terminos. Finalmente, el objetivo de estas definiciones, una
formula, se define recursivamente como:
1. Una formula at
omica es una formula.
2. Si F y G son formulas, tambien los son (F G), (F G) y ( F ).
3. Si F es una formula y v es una variable, entonces v(F ) y v(F ) son
formulas.
Notese en estas definiciones el uso de smbolos como x1 para terminos
y F para formulas; estos no son elementos del calculo de predicados, sino
en realidad parte de un metalenguaje usado para definirlo. Un ejemplo de
una formula en el c
alculo de predicados (que a partir de aqu se le llama
simplemente formula) es:
e(P (e) (d(P (d) (L(a(x, y), d) L(a(f (x), f (y)), e)))))
Es tal vez un poco injusto esperar que un estudiante de teora de funciones reconozca en esta formula la definicion de continuidad en una funcion
real. En el estilo informal de los textos de matematicas, esta definicion se
escribe normalmente como sigue:
> 0 > 0 tal que | x y |< | f (x) f (y) |<
En el contexto mas restrictivo del calculo de predicados, esta definicion
debe re-formularse en terminos de variables, funciones, predicados, y sus
combinaciones legales en formulas. Por ejemplo, > 0 se escribe como
e(P (e) . . . ). Aqu, P (e) es un predicado cuyo u
nico argumento es una
variable real. Se interpreta para significar que e es un n
umero positivo. Si e
es positivo, la formula contin
ua para decir que hay un d tal que d es positivo
y que la formula
L(a(x, y), d) L(a(f (x), f (y)), e)
49

es verdadera. Aqu, L es un predicado que es verdadero cuando su primer

argumento es menor que el segundo. La funcion a define el valor absoluto
de la diferencia de sus argumentos. Bajo la interpretacion dada a la formula
como un todo, obviamente expresa la continuidad de una funcion real.
Por supuesto, tal formula no es en realidad equivalente a la definicion
de continuidad hasta que otras formulas adicionales que definen la nocion
de n
umero, inequidad, etc. son dadas. Ciertamente, los libros mas rigurosos sobre funciones reales hacen algo cercano a esto. En cualquier caso, no
solo puede la teora de funciones proponerse en el calculo de predicados,
sino virtualmente todas las matematicas. Este es el objetivo del Principia
Mathematica, la ambiciosa codificacion logica de las matematicas realizado
en 1921 por los matematicos britanicos Bertrand Russell y Alfred North
Whitehead.
El c
alculo de predicados hereda muchas de las reglas de manipulacion
del c
alculo proposicional. Por ejemplo, las leyes de De Morgan establecen
que:
(A B)
es l
ogicamente equivalente a:
( A) ( B)
donde A y B son proposiciones. Si se reemplazan A y B por predicados arbitrarios, la regla a
un se mantiene. Esto tambien sucede con reglas adicionales
de manipulacion relativas a los cuantificadores universal y existencial. Por
ejemplo:
(x(P (x)))
es equivalente a:
x( (P (x)))
La regla tambien funciona a la inversa, con:
(x(P (x)))
equivalente a:
x( (P (x)))
50

Es necesario distinguir en las formulas entre variables libres y variables dependientes. La dependencia en este caso se refiere a estar bajo un
cuantificador particular. Mas precisamente, si F es una formula y x es una
variable en F , entonces para ambos x(F ) y x(F ) la variable es dependiente. Cualquier variable en F que no se cuantifique es llamada libre.
Como en el c
alculo proposicional, algunas formulas predicadas son verdaderas, y otras falsas. Su veracidad depende, sin embargo, en como sus
predicados y funciones se interpretan. Una interpretacion de una formula
involucra un universo U y una funcion de interpretacion I que mapea cada
predicado n-localizado de la formula en una relacion n-aria en U . Tambien
mapea cada smbolo de la funci
on n-localizada de la formula en una funcion
n-localizada de U en s mismo.
Si la formula contiene una variable libre, en general es imposible bajo
cualquier interpretacion de F determinar su veracidad. Por ejemplo, bajo
la usual interpretacion del predicado menor-que L, no se puede decir si la
formula
xL(x, y)
es verdadera o no. Obviamente, lo sera si se inserta y inmediatamente
despues de x. En cualquier caso, una formula que no contiene variables
libres es satisfactible (satisfiable) si tiene al menos una interpretacion en
la cual es verdadera. Se le llama valida si es verdadera bajo todas las
posibles interpretaciones.
Determinar la validez de una formula no es una cosa sencilla. Aun decidir
si es satisfactible resulta irresolvible: no hay un procedimiento efectivo que
decida la satisfactibilidad de formulas arbitrarias.
Hay procedimientos, sin embargo, para derivar formulas de otras formulas. Las otras formulas pueden ser llamadas axiomas, y la formula derivada puede llamarse un teorema. Derivar un teorema de un conjunto de
axiomas ha sido la labor de los matematicos desde el tiempo de Euclides, y
mucho antes.
Para la comprobacion automatica de teoremas en computacion, el procedimiento seleccionado es el metodo resolucion. En el, los axiomas con los
que se inicia tienen una cierta forma, llamada clausal. Una clausula
es simplemente una disyuncion de predicados o sus negaciones. Cualquier
formula en el c
alculo de predicados puede escribirse en esta forma.
51

Considerense dos clausulas ( P (x) Q(x, y) R(y)) y (P (x) S(x)).

En una de estas cl
ausulas el predicado P (x) aparece, y en la otra se ve
su negacion. Dado que no hay otro predicado que comparta esta propiedad
respecto a las dos cl
ausulas, se les puede reemplazar por la disyuncion de
todas las literales tomadas en conjunto, excluyendo P (x) y P (x):
(Q(x, y) R(y) S(x))
Desafortunadamente, resolucion no es tan directo en muchos otros casos. Por ejemplo, el predicado que se elimina puede tener una estructura
mas complicada. Supongase que P (a, f (x)) aparece en una clausula y que
P (x, y) aparece en la otra. Unificar tales predicados significa encontrar
una substituci
on para las variables que ocurren en ellas, que las exprese precisamente en la misma forma. Esta substitucion debe tambien ser la mas
general posible al efectuar este proposito, en lugar de encontrar el mnimo
denominador com
un. La substitucion para el ejemplo dado anteriormente
sera x = a y y = f (a). Realizando la substitucion, resulta en la aparicion
de:
P (a, f (a)) y P (a, f (a))
En este punto, resolucion puede llevarse a cabo como antes.
Supongase ahora que F es un teorema a ser comprobado y que A1 , . . . , An
son todos axiomas. Formalmente hablando, F y A1 , . . . , An son todos formulas clausales en el c
alculo de predicados. Los cuantificadores existenciales se
han removido por un proceso de skolemizacion (skolemization): si x aparece en una formula, se reemplazan las ocurrencias de x limitadas por su
cuantificador por una instancia particular x = a que hace verdadera a la
expresion bajo . Cada variable de cada clausula se entiende como universalmente cuantificable, de modo que los signos se omiten. El metodo resolucion procede mediante primero negar el teorema F y entonces adjuntarlo
con los axiomas. El sistema resultante puede escribirse como:
F, A1 , A2 , . . . , An
A grandes rasgos, el metodo consiste en resolver pares de clausulas dentro
de este sistema hasta que se llegue a una contradiccion. Ambos, un predicado y su negacion, son resultado de resolucion. Si esto sucede, F ha sido
comprobado. Si esto no puede hacerse, F no puede comprobarse a partir de
los axiomas.
52

Recordando el predicado P (m, w, g, c), el universo en el que se interpreta

este consiste de un ro, un hombre, un lobo, una cabra y una paca de heno.
Las variables m, w, g y c son valuadas binariamente, y se refiere a la situacion
de un lado u otro del ro: si m = 0, el hombre esta en el margen inicial del
ro. Si m = 1 el hombre esta del otro lado. De tal modo, considerando el
lobo, la cabra y el heno, el predicado
P (0, 1, 1, 0)
es verdadero si es posible para el hombre y el heno estar en el lado inicial
del ro y el lobo y la cabra del otro. Sera desafortunado para la cabra si
esto fuera verdadero.
Adem
as, resulta u
til contar con un predicado de equidad E(x, y) que
es verdadero si x y y tienen el mismo valor. Una funcion f hace posible
distinguir uno de los lados del ro del otro: f (0) = 1 y f (1) = 0. En general,
se usa f para definir los primeros axiomas, que regulan la equidad:
1. (E(x, x))
2. ( E(x, f (x)))
Las operaciones de cruce permisibles arrojan otros cuatro axiomas. Solo
se explica aqu la derivaci
on del primero.
Si el hombre y el lobo estuvieran del mismo lado del ro, entonces es
posible que el hombre lleve al lobo al otro lado, resultando que la cabra y el
heno se quedan del otro lado. Esto puede escribirse en terminos de la funcion
y los predicados como sigue:
P (x, x, y, z) E(y, z) P (f (x), f (x), y, z)
Reescribiendo en forma clausal, esto se convierte en el siguiente axioma:
3. ( P (x, x, y, z) E(y, z) P (f (x), f (x), y, z))
Las operaciones de cruce restantes son:
4. ( P (x, y, x, z) P (f (x), y, f (x), z))
5. ( P (x, y, z, x) E(y, z) P (f (x), y, z, f (x)))
6. ( P (x, y, x, y) E(x, y) P (f (x), y, x, y))
Otros dos axiomas se requieren para completar de la solucion. El primero
representa la condicion inicial del hombre, el lobo, la cabra y el heno. El
segundo respresenta la condicion final. Esta clausula esta negada:
53

7. (P (0, 0, 0, 0))
8. ( P (1, 1, 1, 1))
En seguida se muestra un conjunto de unificaciones y resoluciones como
sigue:
1. Comenzando con el axioma 4. cuando x = y = z = 0 resulta en
( P (0, 0, 0, 0) P (1, 0, 1, 0)). Considerando la condicion inicial 7., la
expresion anterior puede reducirse a:
(P (1, 0, 1, 0)) *
2. Por otro lado, se tiene el axioma 6. cuando y = f (x), resultando
en ( P (x, f (x), x, f (x)) E(x, f (x)) P (f (x), f (x), x, f (x))). Este
resultado se reduce junto con el axioma 2., dando:
( P (x, f (x), x, f (x)) P (f (x), f (x), x, f (x)))
Evaluando esto u
ltimo en x = 1, resulta:
( P (1, 0, 1, 0) P (0, 0, 1, 0))
3. Finalmente, reduciendo (P (1, 0, 1, 0) y ( P (1, 0, 1, 0) P (0, 0, 1, 0))
se obtiene:
(P (0, 0, 1, 0)) *
Las dos cl
ausulas marcadas con asteriscos de los pasos 1 y 3 representan
dos partes de la solucion del problema del cruce del ro. En la primera, el
hombre ha tomado a la cabra al otro lado del ro. En la segunda ha regresado
al lado original.
Los pasos de resolucion se han seleccionado teniendo la solucion en mente. Un sistema real de comprobacion de teoremas no tendra tal comportamiento. Procedera mas bien a ciegas, buscando por resoluciones y unificaciones, construyendo una lista de clausulas intermedias hasta finalmente
derivar (P (1, 1, 1, 1)). Comparando esto con el axioma 8., obtendra una
contradiccion. Este hecho se garantiza por un teorema de Robinson, que
establece que resolucion llega a una contradiccion si y solo si la formula
originalmente negada es logicamente derivada de todos los axiomas.
54

Hay numerosas estrategias que apoyan al metodo resolucion para obtener una contradiccion tan rapido como sea posible. Una se conoce como
estrategia de preferencia de unidad (unit preference strategy): seleccione
aquellas cl
ausulas (para unificar y resolver) que sean tan cortas como sea
posible. Otra estrategia, llamada conjunto de apoyo (set-of-support) mantiene una distincion entre axiomas primarios y de apoyo: ning
un par de
axiomas primarios se resuelven en contra entre s.
El metodo resolucion se vuelve muy poco manejable, desde el punto
de vista computacional, para problemas mas complicados que el problema
del cruce del ro. Sin embargo, deducciones as de complicadas no aparecen
com
unmente en el contexto de muchas aplicaciones de programacion logica.

55

56

Captulo 7

El Problema de la Detenci
on
Lo No-Computable
La maquina de Turing es una de varias formulaciones equivalentes de
lo que significa un procedimiento efectivo o computo. Nada mas poderoso que una maquina de Turing ha sido descubierto que capture mejor
el significado de tales terminos. Y a
un as, hay lmites para el poder de
las maquinas de Turing, problemas que estas maquinas no pueden resolver.
Tales problemas son semejantes a aquellos en los que no existe un procedimiento efectivo o c
omputo recursivo que los resuelva. De hecho, se puede
reformular un problema no-resoluble por una maquina de Turing como un
problema no-resoluble en cualquier sistema formal equivalente.
El problema mas conocido no-resoluble por maquinas de Turing es el
problema de la detencion (halting problem). En el, se requiere una maquina
de Turing TH (figura 7.1) capaz de realizar la siguiente tarea para cualquier
par (T, t) como entrada,
Dada una maquina de Turing arbitraria T como entrada y una
cinta igualmente arbitraria t, decidir si T se detiene con t.
Naturalemente, T debe ser del tipo de maquinas de Turing que ejecuta
sobre una cinta semi-infinita, pues al dar como entrada el par (T, t) a TH ,
una mitad de la cinta de TH debe contener la descripcion de T , llamada
dT , y la otra mitad es un duplicado de la cinta semi-infinita t. Un esquema
similar se usa para implementar una maquina universal de Turing.
La pregunta es: existe tal maquina TH ?
57

dT

TH

Figura 7.1: Una maquina de Turing que resuelve el problema de la detencion.

Supongase por un momento que s. Si T se detiene con t, entonces tarde
o temprano TH se
nalara el equivalente a un s, y al hacerlo, completa una
transicion de alg
un estado qi a un estado de detencion qh (figura 7.2). Si T
no se detiene con t, sin embargo, entonces TH tarde o temprano dira no,
haciendo otra transicion de un estado qj a un estado de detencion qk (figura
7.3).

"Si"

Figura 7.2: Transicion para un s.

"No"

Figura 7.3: Transicion para un no.

Ahora bien, mediante realizar algunas alteraciones simples a TH , se pueden complicar las cosas seriamente. La primera alteracion resulta de preguntar si TH puede decidir si T se detiene con dT en lugar de con t (figura
7.4).
Si se le solicita a TH realizar esta tarea especializada (o mas bien extra
na), se le podra proveer a TH con una cinta mas compacta que contenga
58

dT

dT

TH

Figura 7.4: Se detiene T con su propia descripcion?

solo una copia de dT , mediante implantar una maquina de Turing especial
TC dentro de TH . El objetivo de TC es hacer una copia de dT y, cuando
haya terminado, entregar los datos a TH mediante una transicion del estado
final de TC al estado inicial de TH (figura 7.5).

dT

TC
TH
TH

Figura 7.5: Una maquina de copia se incluye en TH .

Denotando la maquina resultante como T H , se realizan algunos cambios
59

leves sobre sus dos transiciones de detencion. La transicion para s desde

qi y la transicion para el no desde qj se desvan a dos nuevos estados, qn
y qy , respectivamente (figura 7.6). Una vez que se llegue al estado qn , hay
una transicion hacia qn para todo posible combinacion de estado/entrada en
la cual T H pueda encontrarse. As, una vez en el estado qn , la maquina de
Turing resultante T H nunca se detiene. Sin embargo, una vez en el estado
qy , T H se detiene por definicion: qy es un estado de detencion (figura 7.7).

"Si"

j
"No"

k
q

Figura 7.6: Recolocando los estados de detencion de TH .

Ahora bien, se puede hacer una prueba muy interesante si se alimenta la
cinta dT H a T H para procesarla. Si T H se detiene con dT H , entonces
debe tomar la misma transicion para el s que TH debe tomar. Pero al
hacerlo, entra en un estado en el que debe estar en ciclos infinitos, y nunca
se detiene: si T H se detiene con dT H , entonces T H no se detiene con
dT H . La situacion no mejora si se supone que T H no se detiene con dT H .
Para tal caso, dT H debe tomar la transicion no, terminando en el estado
qy , un estado de detencion: si T H no se detiene con dT H , entonces T H
se detiene con dT H .
Estas contradicciones aseguran que la maquina TH no puede existir desde un principio. As, el problema de la detencion no puede resolverse por
ninguna maquina de Turing.
Un problema similar que no puede resolverse es el siguiente: hay una
maquina de Turing, la cual, para cualquier par dado (T, t) como entrada,
puede decidir si T imprime el smbolo x cuando procesa la cinta t? Ciertas alteraciones en la maquina Tp que se supone puede resolver el problema de la
impresion (printing problem) resultan en el mismo tipo de contradicciones.
60

dT

TH
T
H
q

q
"Si"
qn

qk
"No"
qy

Figura 7.7: La maquina de Turing T H .

61

62

Captulo 8

El Problema de la Palabra
Diccionarios como Programas
La idea de buscar una palabra en un diccionario es lo suficientemente
com
un y sencilla para cualquiera, pero lleva directamente a un problema que
no puede ser resuelto por una computadora. El problema se basa en la equivalencia de cadenas. Por ejemplo, dada una afirmacion, esc
ojase una palabra
aleatoriamente, use un diccionario para seleccionar una palabra equivalente,
y entonces substit
uyase la nueva palabra en la afirmacion original. Hasta
cuando son las dos afirmaciones equivalentes bajo una secuencia de estas
operaciones?
La pregunta parece bastante trivial cuando se imaginan dos afirmaciones. Ciertamente, se sabe cuando dos afirmaciones son equivalentes: solo
requieren tener el mismo significado. Pero una computadora no cuenta con
esa ventaja. Hasta ahora, no hay un programa que entienda de significados.
Parece ser mas facil apreciar el problema computacionalmente si se considera otro lenguaje desconocido, como el griego antiguo. Supongase que
se cuenta con dos fragmentos de escritura de la Grecia antigua: un texto
con dos afirmaciones y una parte de un diccionario de griego antiguo. Se
cuenta con lo suficiente del diccionario para establecer si las afirmaciones
son equivalentes. Las afirmaciones escritas en el texto griego no cuentan con
espacios. Si se toman estas dos cadenas de caracteres, seran equivalentes?
Para averiguar esto, sistematicamente se hacen substituciones de palabras
en la primera de las afirmaciones, con la esperanza de obtener tras algunos
cambios la segunda. Por supuesto, solo se tienen las substituciones disponi63

bles en el diccionario. Si se tiene una palabra, esta puede substituirse por su

significado. A primera vista, este procedimiento parece lo suficientemente
solido y directo, pero tiene una falla. De hecho, no hay un procedimiento
que funcione.
En 1914, Axel Thue, un matematico noruego, hizo la primera enunciacion
formal de este problema: Sea un alfabeto finito de smbolos arbitrarios, y
sea D un diccionario consistente de un n
umero finito de pares (Xi , Yi ) de palabras. Dada una palabra arbitraria X sobre el alfabeto , una substitucion
involucra encontrar una sub-palabra Xi en X y substituir su correspondiente
palabra Yi . Las palabras X y Y son equivalentes si hay una secuencia finita
de substituciones llevando de X a Y .
Para un ejemplo mas humilde (y algo mas legible) de este problema, se
puede utilizar el alfabeto latino:

RTCXUPNTRX

PN
NTR
XUPN
TCX
RX
PRC
TU
NTT

UUTCXXRNP

XXR
CU
CXXP
RNC
NP
UTC
XRN
CC

Es posible convertir la palabra superior izquierda a la palabra inferior

izquierda mediante substitucion de secuencias del diccionario? El ejecicio
puede ser extenuante para un lector humano, pero seguramente una computadora podra ser programada para determinar la equivalencia de estas palabras. El metodo implcito en el algoritmo descrito anteriormente podra
comenzar con la palabra superior izquierda y derivar todas las posibles substituciones en ella (figura 8.1).
Manteniendo una lista de todas las palabras que se han derivado, el
programa simplemente itera este mismo procedimiento para cada palabra
en la lista. Las palabras en las que se hace una substitucion se reemplazan
en la lista por las palabras resultantes. Como cada nueva palabra se a
nade
a la lista, la computadora intenta hacerla coincidir con UUTCXXRNP. Si
esta palabra es equivalente a RTCXUPNTRX, el programa encontrara la
coincidencia tarde o temprano.
64

RTCXUPNTRX

RTCXUXXR

RTCXUPCUX

RTCCXXPTRX

RRNCUPNTRX

RTCXUPNTNP

Figura 8.1: Comienzo del proceso de generacion de palabras.

Este u
ltimo enunciado hace pensar que el problema ha sido resuelto,
pero no es as. Aun si las dos palabras fueran equivalentes, la secuencia de
substituciones volviendo una palabra a la otra puede involucrar palabras
intermedias que son arbitrariamente largas. No hay, consecuentemente, una
forma de saber cuando terminara el computo. Si las dos palabras no son
equivalentes, la computadora podra continuar hasta el infinito, mientras se
espera pacientemente la respuesta.
Una de las caratersticas cardinales de la computabilidad es que el computo debe detenerse tarde o temprano en todos los casos. Para ser computable,
una funci
on (aun aquella que involucre una simple respuesta de s o no)
debe ser computable en tiempo finito.
La falla del algoritmo de b
usqueda propuesto no comprueba que el problema de la palabra (tambien conocido como el problema de la palabra para
semigrupos) no tiene una solucion computacional. Despues de todo, como
se sabe que no existe una sutil teora que puede ser implementada en un
algoritmo totalmente diferente? Quiza tal algoritmo puede hasta ejecutarse
en tiempo lineal, es decir, puede determinar la equivalencia de dos cadenas
de longitud n en O(n) pasos.
El hecho de que no existe algoritmo alguno para este problema se puede
observar mas claramente mediante utilizar un truco matem
atico muy antiguo: desarrollar una transformacion entre el problema a la mano y alg
un otro
del cual se sabe algo mas. La transformacion se conoce como una reduccion
de Turing (Turing reduction).
Ya que la dificultad encontrada en la solucion propuesta para este problema se refiere a la detencion, es posible que el problema de la palabra
este relacionado con el problema de la detencion para maquinas de Turing.
Esta suposicion resulta ser correcta. Para ver como, debe ser posible conver65

tir una maquina de Turing a un problema de la palabra. Primero, se enuncian ambos problemas explcitamente. Respectivamente, ambos requieren
encontrar algoritmos que hagan lo siguiente: dada una maquina de Turing
arbitraria y una cinta inicial, el primer algoritmo determina si la maquina
se detiene. Ahora bien, dado un diccionario y pares de palabras, el segundo
algoritmo determina si las palabras son equivalentes. El paralelismo en ambas descripciones lleva a preguntarse si la reduccion involucra reemplazar
una maquina de Turing por alguna clase de diccionario. La nocion clave que
lleva a tal reemplazo es la descripcion instantanea de una maquina de Turing
y el ambiente de su cinta. Meramente copia toda la porcion no vaca o en
blanco de la cinta de la maquina de Turing. Entonces, a la izquierda de la
celda actual, insertese una nueva celda que contenga un nombre simbolico
para el estado actual de la maquina. Por ejemplo, si la cinta de la maquina
de Turing actualmente se viera como:

Supongase que la maquina se encuentra en la celda n

umero 10 contando
desde la izquierda, y se encuentra en el estado 5. Reemplacese el 5 por alg
un
smbolo que no se encuentre en el alfabeto de la cinta, por ejemplo, F. Ahora,
la cinta queda as:

Parece claro ahora como proceder. Constr

uyase un diccionario que reproduzca el efecto local en la cinta del programa de la maquina de Turing
cuando se le aplique a la posicion de la cabeza lectora/escritora.
Si por ejemplo cuando la maquina esta en el estado 5 y lee un 1, entra al
estado 2 y escribe un 0, moviendose una celda a la izquierda, el diccionario
se compodra de las siguientes entradas:

0F1
1F1
#F1

F00
F10
F#0

66

En este caso, se aplicara la primera entrada: reemplacese los contenidos

de la celda 0F1 por F00.
Este proceso, sin embargo, no es mas que un ejemplo de las substituciones
utilizadas en el problema de Thue. La reduccion completa, desafortunadamente, involucra algo mas. Dos palabras deben proveerse para finalmente
llegar adecuadamente a una instancia del problema de la palabra. Sea la
primera palabra el estado inicial de la cinta, con el marcador de estado ya
considerado a la izquierda de la celda inicial.
Podra parecer sobre-restrictivo, pero es perfectamente correcto permitir que la segunda palabra este compuesta enteramente de ceros, o tal vez
alg
un smbolo especial, por ejemplo, Z. Cualquier maquina de Turing puede
modificarse para producir este efecto, si llega a detenerse.
Claramente, es notorio que el proceso de reduccion es Turing-computable.
Esto significa simplemente que es computable. Las dos palabras y el diccionario pueden facilmente ser procesadas por un algoritmo que tome el programa
de la maquina de Turing y la cinta inicial como entrada.
Se sabe que no hay un algoritmo que resuelva el problema de la detencion.
Se tiene, sin embargo, una transformacion computable de este problema al
problema de la palabra. Si este u
ltimo tuviera solucion, tambien la tendra
el problema de la detencion, lo que no es posible.

67

68

Bibliografa
[1] A.V. Aho, J.E. Hopcroft, and J.D. Ullman The Design and Analysis of
Computer Algorithms. Addison-Wesley, 1974.
[2] D.I.A. Cohen Introduction to Computer Theory. Jophn Wiley, 1986.
[3] D.R. Hofstadter G
odel, Escher, Bach: An Eternal Golden Braid. Basic
Books, 1979.
[4] S.C. Kleene Introduction to Metamathematics. Van Nostrand, 1950.
[5] H.R. Lewis and C.H. Papadimitriou Elements of the Theory of Computation. Prentice-Hall, 1981.
[6] D.W. Loveland Automated Theorem Proving: A Logical Basis. North
Holland, 1978.
[7] D.E. Knuth The Art of Computer Programming, Vol. 1: Fundamental
Algorithms. Addison-Wesley, 1969.
[8] M.L. Minsky Computation: Finite and Infinite Machines. Prentice-Hall,
1967.

69