Carrera:
Informática
Semestre:
5to.
Semestre
Materia:
Trabajo:
Maestro:
Alumno:
Una
Máquina de Turing es un mecanismo
capaz de manejar símbolos codificados en una cinta. La manipulación de dichos
símbolos dará lugar a la simulación de funciones sencillas. Las Máquinas de
Turing nos van a permitir demostrar la computabilidad de funciones.
Partes
Control finito: es donde figura el código del programa que regula
el funcionamiento de la máquina.
Cinta: es infinita por ambos lados y está dividida en
casillas en cada una de las cuales hay un único símbolo del alfabeto X.
Cabeza móvil: es capaz de leer, escribir y moverse por la cinta.
Funcionamiento
Inicialmente
la Máquina de Turing se encuentra en un estado que denominaremos inicial y
denotaremos por q0. En este estado la cabeza estará situada en la primera
cuadrícula no blanca de la izquierda.
Dependiendo
de un estado interno y del símbolo sobre el que se encuentre la cabeza ocurre
lo siguiente:
- el control cambia de estado
(eventualmente al mismo)
- la cabeza escribe un símbolo en
la casilla en la que se encuentra (eventualmente el mismo)
- la cabeza realiza uno de los
siguiente movimientos:
- desplazarse una casilla hacia la izquierda ( I )
- desplazarse una casilla hacia la derecha ( D )
- no moverse ( N )
- detener la computación ( H )
Finalizada
la computación se mira el estado de control en el que se ha parado, pudiendo
ocurrir lo siguiente:
- si el estado pertenece al
conjunto finito de estados finales ( F ) se acepta la computación y el
resultado está en la cinta
- si el estado no es final, el resultado
es indefinido.
Si
la computación no finaliza el resultado de la misma es indefinido.
Definición
formal
Una
Máquina de Turing es una quíntupla
de la forma (X, Q, i, F, T ) donde:
- X : alfabeto, que siempre será un conjunto finito
- Q : conjunto finito y no vacío de estados
- q0Ì Q : estado inicial. Es único
- FÍ Q : conjunto finito de estados finales (puede ser
vacío)
- T : aplicación denominada transición, definida de la siguiente
forma:
T : Q x X
------------------------> X x Acc x Q
(q,x) -----------------------> T(q,x) = (x' ,
acc, q' )
Acc = { D, I, H, N } = distintos movimientos que
puede hacer la cabeza.
Ante
un estado y un determinado símbolo de la cinta, escribiremos un nuevo símbolo,
haremos una acción y cambiaremos de estado.
T
puede no ser total, es decir, puede no estar definida para determinadas
combinaciones de estado-valor (q, x). Entonces si no existe T(q, x) la máquina
para. Si el estado en el que se encuentra en ese momento es final, entonces el
resultado de la máquina estará en la cinta; si no es final se considera
indefinido.
Descripción
instantánea
Inicialmente
estamos en un estado inicial i, en la cinta hay x1, x2, ... , xn símbolos y la
cabeza se encuentra sobre x1.
i x1 x2 ...
xn
|
... |
x1 |
x2 |
... |
xn |
... |
i
- si T(i,x1) = x1 D q1
|
... |
x1
|
x2
|
...
|
xn
|
...
|
q1
- si
T(i,x1) = x1 I q1
|
... |
x1
|
x2
|
...
|
xn
|
...
|
q1
- si T(i,x1) = x1 N q1
|
... |
x1
|
x2
|
...
|
xn
|
...
|
q1
Estado
instantáneo tras 'n' pasos:
Sea y1 ... yn q x1 ... xn descripción
instantanea de la máquina en un momento dado, donde y1 ... yn son casillas
recorridas. En el siguiente paso sólo puede cambiar la zona yn q x1.
Codificación
de la entrada (input)
- Si n Î N lo representaremos en la
cinta con n +1 unos.
Ejemplos:
'0' --> 1
'1' --> 11
'4' --> 11111
- Si (n1, n2, ... , nk) Î Nk su
codificación en la cinta será la siguiente:
01...(n1+1)...101...(n2+1)...101...(nk+1)...100
donde cada componente va separada por un sólo cero.
Función
semántica
Sea
M = (X, Q, i, F, T) una Máquina de Turing. Para cada k=> 1, se define la
función semántica de aridad k asociada a M como sigue:
jM(k)
: Nk ------------->N
donde
jM(k) (x1, ..., xk) es el número de unos de la cinta tras
una computación que pare en un estado final cuando el contenido inicial de la
cinta es la codificación del vector (x1, ..., xk). jM(k)
(x1, ..., xk) se considerará indefinido cuando la computación no finalice o
bien lo haga en un estado no final.
Función
Turing-computable
Una
función f será Turing-computable si existe M (Máquina de Turing) que la tiene
como función semántica; es decir tal que:
f = jM(k)
siendo f : Nk ----------> N
SUMA DE DOS NUMEROS
Una
de las tareas más simples que puede llevar a cabo una máquina de Turing es la
suma de dos números. Para ello debemos definir primero una convención para
representar dichos números en la cinta. En principio, podríamos pensar que, al
usar los símbolos 0 y 1, podemos representar los números directamente en
binario; sin embargo, la cantidad de operaciones necesarias para trabajar con
ellos hace que el número de estados de la máquina sumadora crezca
sorprendentemente, debido a que es un sistema de numeración posicional.
Para
simplificar el proceso, vamos a representar cada número por una cadena con
tantos unos como indique dicho número; así, para representar el tres,
escribiríamos tres unos seguidos; para un cinco, cinco unos.
Veamos
como podemos sumarlos. Si tenemos dos números en una cinta, separados uno de
otro por un cero, la forma más fácil de sumarlos sería convertir uno de los
unos de los extremos en cero, y cambiar el cero de separación por un uno. De
este modo tendríamos una cadena formada por tantos unos como indica la suma de
los dos números originales. Veámoslo con un ejemplo:
sumemos
tres y cinco:
cinta
inicial:
0000111011111000
ponemos
un cero en el lugar del uno de la izquierda:
0000011011111000
ponemos
un uno en el lugar del cero de separación:
0000011111111000
el
resultado: ocho unos, el número ocho.
Para
implementar esto, supondremos que la máquina se encuentra a la izquierda.
Empezaremos en el estado A. El estado inicial no tiene por qué ser
necesariamente el primero de la lista de estados, pero es costumbre que sea
así. De todos modos, si no es el primero, una simple reordenación del programa resuelve
el problema.
Dado
que el cabezal no tiene por qué estar inmediatamente antes del primer número,
sino que puede estar más alejada, debemos asegurarnos de que llega hasta él sin
alterar nada. Lo que debemos hacer es que, mientras lea un cero y esté en
estado A, escriba un cero (así no altera nada), vuelva a estado A, y se mueva
una casilla a la derecha.
En
cuanto llegue al primer número, se encontrará un uno que es preciso convertir a
cero antes de seguir. Por tanto, si se encuentra en estado A y encuentra un
uno, debe escribir un cero y moverse a la derecha para acercarse al cero de
separación. Pero hay que tener en cuenta que, si permaneciese en estado A, como
después del primer uno vienen más, los pondría todos a cero; por tanto, debemos
añadir un nuevo estado: el B. En cuanto encuentre un uno en estado A, deberá
pasar a este nuevo estado B.
Una
vez que ha puesto ese uno a cero, debe desplazarse hasta llegar al cero de
separación, pero sin alterar nada; luego, si estando en estado B encuentra un
uno, debe poner un uno, moverse a la derecha, y pasar de nuevo a estado B. Pero
en cuanto detecte un cero, significa que ha llegado a la separación, luego si
estando en B encuentra un cero, debe ponerlo a uno.
Ahora
que la suma está terminada, la máquina debe pararse, pasando al estado
correspondiente. Le denominaremos @ (arroba), para distinguirlo de otros
posibles estados. En cuanto lo alcanza, la máquina ya no leerá ningún símbolo
más ni se desplazará.
Veamos
el programa de esta máquina de sumar:
0 1
A
0,A,> 0,B,>
B
1,@ 1,B,>
COPIA DE UNA CADENA DE UNOS A CONTINUACION DE ELLA MISMA
Puede ser útil para
algunas aplicaciones obtener una copia de un número a continuación de él mismo,
bien sea como parte del proceso, bien porque éste lo modifica y queremos
mantener el original inalterado.
Una
posibilidad para copiar una cadena de N unos es usar una máquina de N estados;
sin embargo, esto hace aumentar su número de manera poco menos que
incontrolable; por eso nos conviene hallar un sistema que no consuma tantos
estados, y, sobre todo, que funcione para cualquier cadena, no solo para las de
longitud N.
Una
de las maneras más cómodas es usar un cero como contador. Esto es: colocamos un
cero en lugar del primer uno de la cadena, nos desplazamos hasta el final de
ella, colocamos un uno, y volvemos hasta donde esté el cero. Lo cambiamos a un
uno, pasamos a la siguiente casilla, ponemos un cero y repetimos el proceso. De
este modo, el cero se irá corriendo a lo largo de la cadena original, y cada
vez que se desplace una posición, aparecerá un nuevo uno al final de la cadena
copiada. La máquina se detendrá en cuanto intente poner un cero en el lugar que
ocupe otro cero en vez de un uno, pues significará que ha llegado al cero de
separación de la cadena original y la cadena copia.
Veamos
un programa que cumple lo expuesto, comentado:
0 1
A 0,A,> Nos movemos hacia la
derecha 0,B,> Ponemos un cero en
el
hasta el principio de la cadena.
primer uno de la cadena.
B 0,C,> Vamos a la derecha, a través
de 1,B,> Vamos desde el marcador
la separación entre cadenas.
hasta la separación.
C 1,D,< Ponemos un uno en el
extremo 1,C,> Vamos hacia la
derecha
de la cadena copia.
de la cadena copia.
D 0,E,< Vamos hacia la izquierda
desde 1,D,< Vamos hacia la izquierda
la separación.
por la copia.
E 1,H,< El marcador está a la
izquierda 1,F,< Vamos hacia la izquierda
de la separación. Fin de la copia.
desde la separación.
F 1,G,> Iniciamos el cambio de
lugar 1,F,< Seguimos hasta
encontrar
del marcador.
el marcador.
H ----- Nunca se da esta condición. No 0,B,> Terminamos el desplaza-
programar o poner un bloque
miento del marcador y
ficticio.
recomenzamos.
I
0,@ La cadena ya está
copiada. 1,I,> Nos movemos hasta
el
la máquina debe detenerse.
inicio de la cadena original.
PRODUCTO DE DOS NUMEROS
Vamos
a aprovecharnos de la rutina de copia para hacer una rutina de multiplicación.
Si
analizamos el producto de dos números, vemos que se trata simplemente de sumar
el primero a sí mismo tantas veces como indica el segundo. Y como trabajando
con nuestro particular sistema de numeración, la suma no es más que unir dos
cadenas, vemos que esta es una tarea perfecta para nuestra rutina de copiado.
La
manera de hacerlo es muy simple: debido a una casualidad totalmente
intencionada :-) , si hay dos números seguidos (con el cero de separación entre
ellos, claro) y mandamos a nuestra rutina que copie el primero (el de más a la
izquierda, en nuestro caso), lo hará a continuación del segundo, pero sin
separarlo; en otras palabras, habrá sumado al segundo una copia del primero. De
este modo, si activamos la rutina de copia sobre el segundo número a
multiplicar, tantas veces como indique el primero, lo que haremos será sumar el
segundo número a sí mismo tantas veces como indique el primero. Los habremos
multiplicado.
Para
que la rutina de copia se active tantas veces como indica el primer número,
haremos un contador con un cero, de la misma manera que hicimos en la propia
rutina de copia. Así de fácil.
Veamos
un programa de máquina de Turing que lo hace. Los estados de la A a la H son
los mismos que los de la rutina de copia, para ahorrar espacio en el artículo.
Esto significa que la máquina no se debe poner en marcha en el estado A, sino
en el estado J.
0
1 0 1
I
0,L,< 1,I,< M
1,N,> 1,M,<
J
0,J,> 0,K,> N
----- 0,K,>
K
0,A,> 1,K,> O
0,@ 1,O,<
L 1,O,< 1,M,<
El
bloque ----- significa que esa condición nunca puede darse, por lo que se debe
dejar sin rellenar o bien poner un bloque ficticio.
LA RUTINA BORRACINTAS
Un
programa que, en principio, no pasa de ser una mera curiosidad, es el programa
borracintas. Lo único que hace es colocar la cinta de una máquina de Turing a
cero, eliminando todos los posibles unos que pudiese contener. Dado que el
número de unos existentes no lo podemos conocer a priori, y dado que la cinta
es infinita, ésta máquina, para que realmente sea eficiente, no podrá detenerse
nunca. De todos modos, el número de unos no puede ser infinito, pues entonces
nunca conseguiríamos borrar totalmente la cinta (por mucho tiempo que
tuviésemos la máquina en funcionamiento, siempre quedarían unos sin borrar).
Veamos como diseñarla.
Una
posible opción sería hacer una máquina de un solo estado que, encuentre lo que
encuentre, escriba un cero y pase a la casilla siguiente. Su listado sería:
0 1
A 0,A,> 0,A,>
Vemos,
sin embargo, que esta máquina no es totalmente efectiva, pues sólo elimina los
unos que se hallen a la derecha de la posición de origen. Podríamos diseñar una
máquina borracintas que trabaje hacia la izquierda, y usar primero una y luego
otra; pero como la cinta es infinita, nunca sabríamos cuando podemos parar,
pues pueden quedar aún unos por eliminar. Por eso debemos diseñar otra máquina
más versátil que ésta.
La
segunda versión de la máquina borracintas usa dos estados. Se trata de una
unión de las dos máquinas borracintas anteriores. Lo que hace es desplazarse en
un sentido hasta que encuentra un uno. En cuanto llega a él lo cambia por un
cero y se desplaza en el sentido contrario hasta encontrar otro uno, repitiendo
el proceso. Su listado sería:
0
1 0 1
A
0,A,> 0,B,< B
0,B,< 0,A,>
Si
bien esta máquina es notablemente superior, vemos que puede darse el caso de
que haya más unos hacia el lado derecho de la posición inicial que hacia el
lado izquierdo (no olvidemos que el número de unos es finito). Si se diese esta
situación, en cuanto se acabasen los unos en uno de los lados, la máquina se
escaparía por él, dejando los del otro lado sin borrar. Por fortuna, en esta
vida todo tiene solución, y este problema no iba a ser menos.
Para
conseguir eliminar todos los unos, podemos hacer que, cada vez que la máquina
encuentre uno, lo ponga a cero, coloque un uno en la siguiente posición, e
invierta su sentido. De este modo, los nuevos unos se comportarán como
barreras. Cada vez que la máquina llega a una, la desplaza una posición e
invierte su sentido. De este modo, la máquina siempre recorrerá por igual los
dos sentidos.
Una
precaución consiste en colocar al principio dos unos seguidos, pues puede
ocurrir que en uno de los dos sentidos no haya unos, y la máquina se pierda. De
este modo, al colocar esos dos unos, inicializamos las barreras. A cada vuelta,
las barreras se irán ensanchando más. Cuando una barrera se pone encima de un
uno, lo anula, de modo que al siguiente paso del cabezal quedará eliminado.
El
programa puede ser el siguiente:
0
1 0 1
A 1,B,> 1,B,> D 1,E,> 1,E,>
B 1,C,< 1,C,< E 0,E,> 0,F,>
C 0,C,< 0,D,< F
1,C,< 1,C,<
Los
estados A y B sirven para inicializar las dos barreras. El código del programa
empieza en C, desplazándose hacia la izquierda hasta encontrar un uno, momento
en que lo cambia por un cero y pasa al estado D, que pone un uno una posición
más hacia la izquierda e inicia el desplazamiento hacia la derecha, pasando al
estado E. En el, el cabezal se desplaza hacia la derecha hasta encontrar un
uno, cambiándolo por un cero y pasando al estado F en la siguiente casilla. En
este estado, se pone un uno y se comienza el desplazamiento hacia la izquierda,
volviendo al estado C y cerrando el bucle.
LOS CASTORES AFANOSOS
El
problema del castor afanoso es uno de los más interesantes, trabajando con
máquinas de Turing. Un castor afanoso es, simplemente, una máquina de Turing de
N estados, la cual, una vez puesta en marcha sobre una cinta totalmente a cero,
imprime más unos que cualquier otra máquina de Turing de N estados. Además de
esto, debe cumplir la condición de detenerse tras haber impreso la serie de
unos. No es indispensable que los unos estén seguidos en la cinta; puede haber
ceros de separación entre ellos.
Tal vez alguien piense
que es un problema trivial; sin embargo, es la base de la teoría de la
computabilidad de una función. Precisamente, el máximo número de unos que puede
imprimir una máquina de Turing de N estados es una función no computable; es
decir, si queremos hacer un castor afanoso de N estados, no podemos saber, a
priori, cual es el número de unos que imprimirá.
Se
sabe el máximo de unos para las máquinas de 1,2,3 y 4 estados, que son 1, 4 , 6
y 13 unos, respectivamente. Para más estados, el número exacto no se puede
determinar.
Vamos
a ver los programas de algunos castores afanosos:
CASTOR AFANOSO DE 1 ESTADO:
0 1
A 1,@ 1,@
CASTOR AFANOSO DE 2 ESTADOS:
0 1
A
1,B,> 1,B,<
B 1,A,< 1,@
CASTOR AFANOSO DE 3 ESTADOS:
0 1
A
1,B,> 1,C,<
B
1,A,< 1,B,>
C 1,B,< 1,@
Para
intentar resolver el problema del castor afanoso de cinco estados, en 1982 se
anunció un concurso. Para participar, había que presentar un castor afanoso
pentaestado, y ganaría el que más unos fuese capaz de imprimir antes de
detenerse.
El
vencedor del concurso, celebrado en enero de 1983, fue la máquina presentada
por Uwe Schult, la cual fue capaz de imprimir 501 unos en la cinta. Su programa
es el siguiente:
0 1 0 1
A 1,B,> 0,C,< D 0,E,> 1,@
B 1,C,> 1,D,> E 1,C,< 1,A,>
C 1,A,< 0,B,>
Una
vez puesta en marcha, parece seguir un curso cíclico, a medida que va
aumentando el número de unos de la cinta. De hecho, parece que nunca se va a
detener; sin embargo, como castorcito afanoso que es, se detiene una vez
cumplida su misión: imprimir 501 unos.
Pero...
como (casi) siempre ha ocurrido en la historia de la computación, ante una
solución a un problema, siempre existe otra que es, o mejor, o más simple. Dos
años después, el 21 de diciembre de 1984, George Uhing descubrió una máquina de
Turing pentaestado capaz de imprimir 1915 unos antes de detenerse. Como es
lógico, el programa de Uwe Schult quedó sin el título de castor, otorgándoselo
al nuevo algoritmo. Me hubiera gustado poder incluir su listado, pero no he
tenido manera de encontrarlo.
Y
así sigue la cosa. Posiblemente algún día aparecerá una nueva máquina de Turing
pentaestado capaz de imprimir un número mayor de unos, proclamándose nueva
campeona.
La
Máquina de Turing (MT) es el paradigma de computación vigente hoy día. Esto
quiere decir que cualquier algoritmo (secuencia de instrucciones realizables en
tiempo finito) en una computadora, es realizado por una MT. Dado un enunciado
de entrada a una MT, luego de ser procesado bajo las instrucciones de la
máquina, ésta posiblemente proporcione un resultado de salida. El enunciado de
entrada es la tarea que se asigna a la computadora y el enunciado de salida es el
resultado que entrega, si es el caso. A lo largo de este capítulo veremos bajo
que condiciones una máquina de Turing, dada una entrada entrega un resultado, y
cuando no.
El
nombre de la máquina se debe a su creador, el genial científico Alan Turing
(1914 – 1954)[1].
Hay máquinas de Turing para todo tipo de tarea realizable por una computadora.
Las hay muy simples, para escribir (borrar) un símbolo un determinado número de
veces, hasta muy complejas, para controlar el desplazamiento de un vehículo. De
hecho, las máquinas de Turing complejas resultan de la combinación de otras más
simples. La descripción general de una MT es la siguiente: consta de una cinta
tan larga como se quiera (incluso infinita), una cabeza de lectura/escritura y
un control de sus movimientos. La cinta está dividida a cuadros en los cuales
la cabeza escribe o lee, un símbolo por cuadro; el control indica los
movimientos de la cabeza sobre la cinta, hacia delante o hacia atrás,
dependiendo del símbolo en el cuadro actual. El funcionamiento es el siguiente:
la cabeza lee, símbolo por símbolo, el enunciado de entrada (en adelante
llamado entrada) y conforme lo indica el control, modifica ó no el símbolo
actual y se mueve hacia adelante o hacia atrás. Al terminar de leer el último
símbolo de la entrada y de realizar la operación indicada por el control, hay
dos posibilidades. La máquina se detiene ó cae en un ciclo sin fin. Cuando se
detiene significa que o bien 1) ha realizado con éxito la instrucción indicada
en la entrada y da un resultado de salida, ó 2) la MT es incapaz de realizar
esa instrucción –realizable por otra MT- y lo indica. Si no se detiene, tenemos
que la MT es incapaz, tanto de realizar la instrucción como de indicar su
incapacidad. En este caso ninguna MT es capaz de realizar la instrucción y ésta
es no computable, es decir, no es posible que una computadora la lleve a cabo.
De
la manera descrita, una MT realiza (ó no) cualquier computo. Puede sorprender
que en base a un dispositivo tan simple como la Máquina de Turing y combinando
máquinas de Turing básicas, tales como MT’s para escribir, borrar ó copiar un
símbolo determinado número de veces, etc. una computadora realice cualquiera de
sus tareas. Algo que seguramente ayuda a la comprensión de este hecho es que el
conjunto de instrucciones que una MT es capaz de llevar a cabo o reconocer
forman un lenguaje (formal).
Las
palabras del lenguaje se forman a partir de los símbolos de un alfabeto. El
conjunto de reglas que determinan cuales combinaciones de símbolos son palabras
del lenguaje, y por complemento cuales no, forman la gramática del lenguaje.
Una máquina de Turing particular reconoce (acepta) las palabras de un lenguaje.
El control de la cabeza de lectura/escritura[2] es la implementación de la gramática
del lenguaje. Entonces, una MT dada es capaz de reconocer las palabras de un
lenguaje cuya gramática está expresada a través del control de la cabeza. Las
palabras que reconoce son las instrucciones que la máquina es capaz de realizar
mediante un número finito de pasos y lograr un resultado. De las palabras que
no reconoce, hay algunas que la MT indica como rechazadas por ella, y se
detiene; en este caso, son instrucciones que esta MT es incapaz de realizar,
las cuales, sin embargo, pueden ser ejecutadas por otra máquina de Turing.
Las
palabras no reconocidas ni rechazadas por una MT, dan lugar a un ciclo infinito
y no son realizables por ninguna MT, es decir, no son computables.
En
términos de una teoría lógica[3]
(TL) se tiene lo siguiente. Una TL se define a partir de un conjunto de
enunciados dados llamados axiomas y unas reglas de inferencia. A partir de los
axiomas y aplicando las reglas de inferencia se derivan los teoremas de la
teoría[4]. Ahora
bien, el conjunto de teoremas de la teoría forman un lenguaje. Si es posible
definir una máquina de Turing tal que reconozca a todos los teoremas de la
teoría, se dice que la teoría es decidible. Es decir, si el conjunto de
teoremas visto como un lenguaje es reconocido por una máquina de Turing,
entonces la TL es decidible. Y viceversa. Puede hablarse entonces,
indistintamente, de teorías lógicas o de lenguajes, ambos decidibles, como
aquellos para los que existe una máquina de Turing capaz de reconocerlos (ver
diagrama en Figura 1).
A
partir de la existencia de máquinas de Turing capaces de reconocer lenguajes y
teorías decidibles, la relación entre computación y lógica queda bien
establecida. Las teorías lógicas son decidibles si y solo si hay máquinas de
Turing capaces de calcularlas. O bien, el lenguaje formado por los teoremas de
una TL es decidible si y solo si hay una MT capaz de reconocerlo o calcularlo.
Luego, las teorías y lenguajes decidibles son los calculables o computables.
Por otro lado, los enunciados no reconocibles por una MT corresponden a
enunciados llamados indecidibles (no decidibles) en una teoría lógica, y no son
computables.
Es
oportuno decir ahora que el Cálculo Lambda de Alonzo Church (1933) y el sistema
de producciones de Emil Post (1943), son formalismos con los cuales puede
comprenderse, también, cualquier proceso computable. Luego, ambos son
traducibles en términos de máquinas de Turing, y viceversa respectivamente.
Actualmente se han planteado formalismos con la pretensión de generalizar el
paradigma computacional de máquinas de Turing, tales como las Máquinas de
Gurevich, entre otros. Sin embargo, son teorías que aún no han sido confirmadas
en lo general.
En
el resto del documento repasaremos con detalle los conceptos que hemos apuntado
brevemente en los párrafos anteriores. Comenzaremos con los autómatas y los
diferentes lenguajes que son capaces de reconocer. Luego repasaremos el
concepto de Teoría Lógica para establecer su relación con las máquinas de
Turing. Enseguida veremos algunas aplicaciones ilustrativas de la relación
entre lógica y computación, tales como el Análisis de Programas, la
Demostración Automática y la Inteligencia Artificial.
Autómatas y Lenguajes Formales
En
una computadora, el mecanismo básico para la realización de cualquier
instrucción de entrada es un autómata. Dependiendo de la complejidad del
lenguaje en el que este dada la instrucción a la computadora, es el tipo de
autómata que se utiliza para calcularla. Los autómatas más simples son los
autómatas finitos, capaces de reconocer lenguajes regulares, a los que siguen
en capacidad los de pila, capaces de reconocer lenguajes libres de contexto. La
Máquina de Turing es el autómata más general mediante el cual cualquier proceso
realizado por una computadora es llevado a cabo; estos reconocen los lenguajes
recursivos numerables. Los elementos comunes de los autómatas son los
siguientes:
Ø
Un conjunto de símbolos o alfabeto con el cual se forman las palabras del
lenguaje que reconoce el autómata
Ø
Un conjunto de estados, siendo especiales, el estado inicial y los estados
finales
Ø
Una función de transición (control) entre los estados del autómata.
Las
etapas en la realización de una entrada (instrucción) son los estados del
autómata. El número de estados de un autómata es finito[5]. Si partiendo del estado inicial es
posible llegar a un estado final, la instrucción de entrada es realizada por el
autómata. El paso de un estado a otro está en función del estado actual y del
símbolo leído, y el conjunto de pasos entre estados definen la función de
transición del autómata, lo cual constituye el control del autómata. Un estado
puede ser visitado una o más veces durante la realización de una instrucción.
Si
dado un estado de partida y una entrada el estado de llegada es uno y
necesariamente uno, el autómata es determinista, mientras que si son ninguno ó
varios los estados de llegada, el autómata es no determinista. Sin embargo, tal
diferencia no es esencial, pues un autómata no determinista es susceptible de
traducción a uno no determinista, y viceversa.
Un
lenguaje formal, por su parte, es un conjunto de palabras formadas a partir de
un alfabeto y de acuerdo a ciertas reglas gramaticales[6]. Un autómata es capaz de reconocer las
palabras de ciertos lenguajes formales, los calculables o computables. Los
lenguajes regulares, libres de contexto y recursivo numerables son calculables.
Esto implica que las instrucciones dadas utilizando palabras de tales lenguajes
pueden ser realizadas por una computadora.
El
funcionamiento de un autómata es el siguiente: hace lectura de una palabra de
izquierda a derecha, letra por letra. El estado inicial recibe de entrada la
letra más a la izquierda de la palabra; conforme a la función de transición
pasa a otro estado, y recibe como entrada la penúltima letra a la izquierda de
la palabra y pasa a otro estado. Este ciclo se repite sucesivamente con cada
letra de la palabra hasta leer la letra más a la derecha. En caso de llegar a
un estado final del autómata, la palabra pertenece al lenguaje que el autómata
reconoce, y en caso contrario no pertenece. Enseguida comentaremos el autómata
finito, el de pila y el de Turing, junto con los lenguajes que reconocen.
Un
punto fundamental es que los lenguajes formales computables permiten una
representación mediante una expresión finita. Esto quiere decir que hay una
expresión a partir de la cual es posible generar al lenguaje. Enseguida veremos
los lenguajes, las expresiones que los representan y los autómatas que los
reconocen.
Autómatas Finitos y Lenguajes Regulares
Un
dispositivo que reconoce las palabras de un lenguaje, y tal que no necesita un
almacén de memoria para hacerlo es un autómata finito[7]. Los lenguajes regulares son los
reconocidos por autómatas finitos y se rigen por gramáticas regulares.
Esencialmente,
un lenguaje regular es un conjunto de palabras formadas por la concatenación de
símbolos del alfabeto de acuerdo a una secuencia dada, la cual forma una
expresión regular (er). Las er’s más simples son la cadena vacía ε formada
de cero símbolos, y los símbolos del alfabeto. A partir de la concatenación de
estas er’s simples se forman otras er’s (de longitud finita) que conforman un
patrón. Concatenando consigo misma a cualquiera de tales expresiones regulares
pueden formarse, a su vez, otras expresiones regulares de mayor longitud.
Por
ejemplo, si el alfabeto consta de los dígitos 0 (cero) y 1 (uno), expresiones
regulares son: la cadena vacía e, de longitud cero; las cadenas 0 y 1, de longitud
uno; las cadenas 00, 01, 10, 11, de longitud 2; de la concatenación de todas
ellas entre si, resultan las cadenas 000, 001, 010, 011, 100, 101, 110, 111, de
longitud 3. Y así sucesivamente para formar las cadenas de longitud 4, 5, etc.
En este caso el lenguaje es generado por las er 0 y 1, y se representa por
{0,1}*. El símbolo * representa que la concatenación de 0 y 1 se hace formando
cadenas de 0’s y 1’s de longitud tan larga como se quiera, y por tanto, el
lenguaje {0,1}* consta de una infinidad de palabras o cadenas.
Otro
lenguaje formado con el alfabeto 0 y 1, es {00, 11}*, el cual consta de cadenas
tales como 0011, 1100, 0000, 1111, 000011, 001100, etc. En este caso, el
lenguaje también tiene una infinidad de palabras, las cuales son de longitud par.
Las
operaciones entre lenguajes regulares son la concatenación y la unión, el
complemento, la intersección y la cerradura estrella de Kleene *. Todas ellas
dan lugar lenguajes regulares, es decir, la concatenación de lenguajes
regulares es un lenguaje regular, etc.
Hay
lenguajes tan simples como xnyn dónde n es un número
natural, que no pueden ser reconocidos por ningún autómata finito. La razón es
porque un AF no tiene una memoria en la cual registrar el número de veces que
la x o la y han sido leídas, de tal manera de lograr un estado final una vez
que las hubiera leído: el autómata podría leer una cadena de x seguida de una
cadena de y, pero no sabría cuantas x’s o y’s ha leído. Luego, es requisito
para que un autómata reconozca tal tipo de lenguajes, contar con una memoria.
En un autómata, el almacén de datos o memoria más elemental y a partir del cual
se forman cualquier otro, es una pila. Los autómatas de pila son los autómatas
con memoria, más simples.
Autómatas
de Pila y Lenguajes Libres de Contexto
En
un autómata de pila (AP), la memoria del autómata es la pila, donde se guardan
algunos caracteres leídos. Para reconocer las cadenas del lenguaje xnyn,
se diseña un AP tal que guarde en memoria (la pila) las x’s leídas; conforme la
cabeza lectora lee cada y, una x es sacada de la pila, de tal manera que al
terminar de leer n y’s, la pila este vacía, lo cual quiere decir que,
exactamente, n x’s han sido leídas, el AP logra un estado final y la cadena es
aceptada. En caso contrario, ya sea la pila no está vacía al terminar de leer
las y’s y hay más x’s que y’s, ó la pila se vació antes de terminar de leer las
y’s y hay más y’s que x’s; en cualquiera de estos casos la cadena no es
aceptada por el AP.
Un
autómata de pila es capaz de leer cualquier lenguaje con palabras que
involucren cadenas con cierta simetría como la de {xnyn :
n Î N}. Más aún, con autómatas de pila es posible implementar diversos
intérpretes y compiladores, fundamentales en el funcionamiento de una
computadora. Actualmente, un programa para una computadora es una secuencia de
instrucciones escritas en un lenguaje de programación de alto nivel (C, C++,
Java, etc.) . Es de alto nivel porque permite a un ser humano, en un lenguaje
cercano a sus procesos de razonamiento y expresión, dar instrucciones a la
computadora. Un compilador es un dispositivo tal que dado un programa escrito
en un lenguaje de programación de alto nivel, lo traducen a otro programa
comprensible para la computadora escrito en lenguaje de bajo nivel. Utilizando
este programa la computadora es capaz de ejecutar las instrucciones. Antes del
surgimiento de los lenguajes de alto nivel, las instrucciones a la computadora
eran dadas en los llamados lenguajes de máquina (caso extremo de los lenguajes
de bajo nivel), de difícil comprensión para un humano.
El
proceso de traducción que realiza un compilador involucra reconocimiento
léxico, sintáctico y semántico. Durante el reconocimiento léxico se comprueba
que las partes elementales que forman las palabras del lenguaje, llamados
lexemas o tokens, sean correctas. Con el reconocimiento sintáctico se comprueba
que la construcción de las frases sean correctas. El reconocimiento semántico
comprueba que los nombres que se utilizan para los operadores, operandos,
variables, etc sean correctos, lo cual conlleva que la frase tenga sentido. El
reconocimiento sintáctico y semántico es realizado por el parser del
compilador. Una gran variedad de compiladores usuales en procesos
computacionales, con sus respectivos parsers, están implementados con autómatas
de pila.
Los
lenguajes reconocidos por autómatas de pila se llaman libres de contexto,
generados por gramáticas libres de contexto. El alfabeto esta formado por
símbolos terminales y no terminales. Las reglas de una gramática libre de contexto
son de la forma a®b, donde a y b son cadenas tales que a involucra tanto
símbolos terminales como no terminales, y b involucra, a lo más, un símbolo no
terminal. La aplicación de una regla a una cadena a, típicamente resulta en la
substitución de un símbolo no terminal por otro no terminal ó por uno terminal,
dando por resultado la cadena b. Cuando b contiene solamente símbolos
terminales no hay más reglas que aplicar; en este caso si el AP logra un estado
final, reconoce a la cadena como propia del lenguaje. En caso contrario, la
rechaza.
Obsérvese
que un autómata finito es de pila, simplemente que la pila permanece vacía
durante toda la operación. Hay una gran variedad de lenguajes libres de
contexto usuales en computación. Sin embargo, pese al mayor poder de
reconocimiento de los autómatas de pila capaces de reconocer lenguajes libres
de contexto, hay lenguajes muy simples no reconocidos por tales autómatas, por
ejemplo, {an bn cn : n Î N}. Tal cosa nos da
pie al estudio de los autómatas más generales, actualmente.
Máquina de Turing
Como
se ha dicho antes, actualmente, el autómata más general es una máquina de
Turing y cualquier modelo de computación es equivalente a una MT. Como muchas
cosas de gran utilidad práctica y profundidad conceptual, los elementos que
forman una MT son simples; aparte de los elementos comunes a cualquier autómata
se añaden los siguientes:
·
Una cinta (quizá infinita) dividida en espacios rectangulares.
·
Cabeza de lectura y escritura.
Las
cadenas de símbolos están escritos en la cinta, uno y sólo uno en cada espacio
rectangular; un símbolo es el espacio en blanco y los símbolos especiales, I y
D, indican movimiento a la izquierda y derecha, respectivamente, de la cabeza
lectora sobre la cinta. En el caso que la cinta sea infinita, se extiende hacia
la derecha y se asume que en el extremo izquierdo de la cinta se tiene un tope
más allá del cual la cabeza lectora no puede moverse. La infinitud de la cinta
quiere decir que se puede leer o escribir tanto como se quiera, lo cual
corresponde, teóricamente, a una capacidad de memoria ilimitada.
La
cabeza de lectura y escritura es la que se encarga de leer o escribir los
símbolos en la cinta conforme a la función de transición (mecanismo de
control). Puede leer un símbolo y cambiarlo por otro, ó borrarlo y dejar ese
espacio en blanco; ó habiendo leído un espacio en blanco, escribir un símbolo
distinto del blanco. Si los símbolos que lee son I o D, la cabeza lectora se
mueve a la izquierda o derecha, respectivamente.
La
memoria de un autómata de Turing es la propia cinta. En el caso del lenguaje {an
bn cn : n Î N} la MT es la de la figura X y funciona
conforme la función de transición descrita en la Tabla X: la cabeza lectora lee
las cadenas de a’s y sin borrarlas avanza hacia la derecha hasta leer la última
a; conforme empieza a leer un símbolo b lo sustituye por un espacio en blanco,
y cambia de dirección moviéndose hacia la izquierda hasta encontrar una a, la
cual sustituye por una b; entonces se mueve de nuevo hacia la derecha tantas
b’s como ha escrito, lee el espacio en blanco y lee la siguiente b (de la
cadena original) si la hay, completando un ciclo. Sucesivamente repite el ciclo
hasta encontrar un símbolo c distinto de b. Si el autómata lee y borra tantas
b’s como a’s que sustituye, significa que hubo el mismo número de a’s y b’s en
la cadena que se está leyendo. Entonces se opera el ciclo de la misma manera
con las c’s y las b’s. Si son tantas c’s que lee y borra como b’s que
sustituye, el autómata logra un estado final y reconoce a la cadena como parte
del lenguaje. En caso contrario, no son iguales el número de ocurrencias de a,
b y c, por lo que la cadena es rechazada por la MT y no forma parte del
lenguaje.
Obsérvese
como en el ejemplo la cinta funciona como memoria al mantener guardadas durante
la operación, primero las a’s luego las b’es y luego las c’s. Conforme necesita
lo escrito en memoria (la cinta) para operar, lo saca (lo lee) y lo utiliza –a
veces lo borra, otras lo sustituye, etc. Sin embargo, la cinta ofrece posibilidades
de manejo de memoria mucho más poderosas que la pila. En el ejemplo, la MT
empila (lee sin borrar de izquierda a derecha) las a’s y luego, desempila cada
una y empila en su lugar una b (lee de derecha a izquierda una a, la borra y
escribe en su lugar una b); el punto es que para desempilar las a’s la MT lee
no solo en la cima de la pila, sino también puede leer las posiciones
interiores de la pila (puede recorrer la cinta todas los cuadros a la izquierda
hasta llegar al tope, el cual representaría el fondo de la pila). A diferencia,
un AP solo puede leer de la cima de la pila. Por este manejo limitado de
memoria es que un AP no puede reconocer el lenguaje {an bn
cn : n Î N} pese a poder reconocer al lenguaje {an bn
: n Î N}.
En
general puede decirse que un autómata de pila es una MT tal que la pila esta
sobre la cinta y tiene la restricción de moverse hacia la izquierda solamente
una posición. Es claro que en una MT los movimientos hacia derecha e izquierda
de la cinta, así como la capacidad de leer y escribir cualesquiera símbolos y
espacios blanco sobre la cinta, es lo que permite un manejo dinámico de la
memoria, versatilidad de la cual carece un autómata de pila al no contar con
una cinta ni una cabeza de lectura – escritura, ni la capacidad de ir hacia
delante o atrás.
Es
posible que con el ejemplo anterior, el lector empiece a creer que pese a que
una MT es un dispositivo simple, es capaz, sin embargo, de realizar cualquier
procedimiento computable. Al fin y al cabo un proceso computable no requiere si
no
Ø
Un almacén de datos (cinta tan larga como se requiera),
Ø
Un dispositivo para leer y/o escribir datos en el almacén (cabeza de
lectura/escritura), y
Ø
Capacidad para moverse a través de los datos en el almacén (movimientos de la
cabeza a lo largo de la cinta, coordinados por el control de estados).
Como
se ve, todos ellos son elementos que posee una MT. Una computadora no es sino
una gran y compleja Máquina de Turing formada a partir de máquinas de Turing
más simples. El disco duro corresponde a la cinta, la cabeza a los dispositivos
de lectura y escritura del y sobre el disco, y el control de la cabeza
(matemáticamente, la función de transición) a los comandos de los distintos
programas que se ejecutan con la computadora[8]. Pasaremos ahora a la precisar lo que
es un algoritmo o secuencias de instrucciones que una computadora ejecuta en
tiempo finito.
El problema de la parada
Si
dada una entrada a un autómata de Turing, luego de una secuencia de
transiciones a través de sus estados logra un estado final, de parada, se dice
que la entrada es decidible para el autómata. Dada una entrada a una máquina de
Turing, el llamado problema de parada es de importancia capital en computación.
La razón es simple: en computación, no hay dispositivo más poderoso que una
máquina de Turing. Luego, las entradas que luego de una secuencia finita de
transiciones logran un estado de parada bajo una MT son las computables, y nada
más.
Dado
un conjunto de entradas, algunas máquinas de Turing poseen dos estados finales,
uno de aceptación y otro de rechazo, los cuales son los estados de parada del
autómata. Las cadenas para las cuales la MT logra un estado de parada -de
aceptación o rechazo- conforman un lenguaje decidible por la máquina. Luego,
una entrada es decidible por una MT ya sea porque el autómata la acepta como
parte del lenguaje o porque la rechaza; bajo tales entradas la MT se detiene
luego de una secuencia finita de transiciones entre estados. Los lenguajes
decidibles son cadenas de palabras calculables mediante funciones recursivas
por lo cual también se les llama lenguajes recursivos. Se dice que una función
o un lenguaje es recursiva(o), si existe una MT que la calcula.
Hay
lenguajes formados por cadenas tales que una máquina de Turing logra un estado
final con las cadenas que reconoce y acepta, solamente. En este caso se dice
que la Máquina de Turing semidecide al lenguaje. Los lenguajes semidecididos
por una MT se llaman recursivos numerables. Las gramáticas sin restricciones
son las que generan los lenguajes recursivo numerables. De aquí en adelante
será suficiente referirse a los lenguajes recursivos numerables, pues estos
generalizan a los lenguajes recursivos, los cuales generalizan a los lenguajes
libres de contexto, y éstos a los lenguajes regulares. Lo anterior tiene
relación directa con que los autómatas de Turing generalizan a los de pila y
estos a su vez a los autómatas finitos. Por otro lado, pese a que lenguajes
formales más generales que los recursivos numerables no son reconocidos por un
autómata de Turing, no existe hasta el momento ningún autómata más poderoso
capaz de reconocerlos.
En
términos de procedimientos, las cadenas de un lenguaje decidible corresponden a
procedimientos que terminan, ya sea realizando lo que indica la palabra ó
señalando que no tiene la capacidad de realizarlo. Para un lenguaje
semidecidible, las cadenas decididas por la MT son instrucciones realizadas por
la MT. De manera complementaria, las cadenas no decidibles por la MT corresponden
a procedimientos que no terminan utilizando una máquina de Turing. A partir de
lo dicho aquí tenemos la definición de algoritmo:
·
Un algoritmo es la implementación de una máquina de Turing tal que el conjunto
de sus entradas es un lenguaje decidible.
Es
decir, si dado un conjunto de entradas bajo las cuales una MT logra un estado
de parada para cada entrada, la máquina corresponde a la implementación de un
algoritmo. Esta es la Tesis de Church – Turing. No es un teorema pues no se
puede demostrar matemáticamente, de manera general y categórica. Es solo la
afirmación de que el concepto informal de algoritmo corresponde a un objeto
matemático. Al ser solo una afirmación no demostrable, puede suceder que luego
fuera refutada. Para que esto ocurra, se necesitaría encontrar un autómata más
potente que uno de Turing tal que fuese la implementación de un algoritmo[9]. Si bien hay
algunas propuestas interesantes que pretende generalizar a la MT, hasta la
fecha ninguna de ellas ha sido aceptada para sustituir nuestro actual concepto
de procedimiento computable.
Por
otro lado, mientras que los lenguajes computables son una infinidad numerable,
los lenguajes no computables son una infinidad no numerable[10]. Por ello, son más los lenguajes no
computables o indecidibles que los computables o decidibles.
Teorías Lógicas y Máquinas de Turing
En
el Capítulo 2 de este volumen se tiene una presentación detallada de la Lógica
de Primer Orden. En esta sección recordaremos los conceptos necesarios para
establecer la relación de una teoría lógica en general con los Autómatas de
Turing, y en general con la disciplina de Computación.
Una
teoría lógica (TL) se define a partir de un conjunto de enunciados dados
llamados axiomas, unas reglas de inferencia y un esquema de derivación. A
partir de los axiomas y aplicando las reglas de inferencia y el esquema de
derivación se infieren los teoremas de la teoría[11]. El conjunto de teoremas de la teoría
forman un lenguaje formal.
Si
es posible definir una máquina de Turing tal que reconozca al lenguaje de los
teoremas, este lenguaje es decidible y la teoría también lo es en consecuencia.
Dicho en otras palabras, si el conjunto de teoremas visto como un lenguaje es
reconocido por una máquina de Turing, entonces la TL es decidible. Y viceversa.
Puede hablarse entonces de manera indistinta de teorías lógicas o de lenguajes
decidibles, como aquellos para los que existe una máquina de Turing capaz de
reconocerlos (ver diagrama en Figura 1). Luego, la correspondencia entre la
sintaxis de una teoría lógica (lenguaje formal) y el reconocimiento simbólico
de la mismo por parte de un autómata queda establecida.
Desde
el punto de vista semántico, las interpretaciones de las cadenas del lenguaje
se realizan ya sea por el intérprete ó bien por el compilador del lenguaje de
programación en el cual se dan las instrucciones (ver Sección de Autómatas de
Pila). Las cadenas que resultan en instrucciones realizadas por la computadora pueden
considerarse interpretadas como verdaderas y por tanto tienen, al menos, un
modelo de la Teoría Lógica formada por tales cadenas.
Procesamiento electrónico de Lenguaje Formales
Las
computadoras son máquinas que operan mediante señales electrónicas, las cuales
son traducción de secuencias de bits (abreviatura de binary digits); un bit es
un cero (0) o un uno (1) arábigo. Aunque parece difícil de asimilar, con
cadenas de ceros y unos, solamente, pueden expresarse la variedad de
instrucciones que una computadora ejecuta. Electrónicamente, el cero es el
estado apagado, en tanto el uno es de encendido. Tal cosa es una traducción de
la ejecución hecha por una Máquina de Turing.
Un
byte es una cadena de ocho bits y es la longitud estándar de una cadena (palabra)
que reconoce una computadora. Por ejemplo, para escribir los números enteros
positivos 1, …, 5 en bytes se hace de la siguiente manera, respectivamente,
00000001, 00000010, 00000011, 00000100, 00000101. Obsérvese la escritura de las
operaciones de suma ( + ) y multiplicación (*) con números escritos en bytes:
Código
decimal Código binario
6
+ 7 = 13 00000110 + 00000111 = 00001101
8*2
= 16 00001000 * 00000010 = 00010000
9*2
= 18 00001001 * 00000010 = 00010010
En
las antiguas computadoras, en las cuales las señales se transmitían a través de
tubos de vacío o bulbos, durante el procesamiento de instrucciones la imagen
visual era la de tubos encendidos (1) o apagados (0) alternativamente, conforme
la instrucción que se procesaba. Con 30 bulbos era posible codificar más de un
billón de instrucciones y con 33 bulbos unos diez billones. En las computadoras
modernas, los bulbos han sido sustituidos por chips, los cuales son diminutos
dispositivos de transmisión y procesamiento de señales a mucha mayor velocidad.
La
manipulación simbólica en un lenguaje formal es traducible en procesamiento de
señales electrónicas en una computadora. La posibilidad práctica de tal cosa es
lo que ha traído como consecuencia el uso intensivo de la computadora en
diversas actividades humanas. Una computadora realiza tareas tales como
procesamiento de texto, manejo de bases de datos, cálculos financieros y
matemáticos en general (probabilístico, estadístico, etc.); control de un
satélite o vehículo cualquiera, control de un robot, ya sea en un entorno
médico (sistema de diagnóstico), financiero (cajero automático) o industrial
(control de la línea de ensamble en una fábrica). A continuación se comentan
algunas aplicaciones donde se ilustra la combinación, implícita ó explícita, de
la Lógica y la Computación.
Aplicaciones
Análisis de Programas
Un
programa escrito en cualquier lenguaje, como cualquier objeto diseñado para
realizar determinada tarea, ha de probarse que cumple bien el objetivo para el
cual ha sido elaborado. Un programador ingenuo puede pensar que con haber
realizado algunas pruebas complicadas siendo el resultado satisfactorio, el
programa ha mostrado su buena manufactura. No es así. Esas son solo muestras
particulares, puntuales de que el programa funciona bien para esas entradas de
prueba, pero no para cualquier entrada. Para demostrar, en general, que el
programa funciona bien, es necesario que dada una entrada cualquiera, la salida
del programa sea conforme lo que se esperaba que hiciera. Si el programa es
para la realización del producto de números enteros se espera que el resultado
de multiplicar cualesquiera par de enteros sea correcto; junto con ello si las
entradas no son números enteros que el programa lo rechace y lo indique.
Utilizando lógica de primer orden es posible hacer un análisis general del
flujo de ejecución de una clase de programas, dada una entrada y hasta la
salida. Los programas que no se invocan a si mismos durante la ejecución forman
la clase para la cual este análisis es adecuado.
El
análisis de un programa consiste en revisar las relaciones que se establecen
durante el flujo del mismo dada una entrada y hasta la salida. Las
especificaciones del programa establecen de principio las relaciones a darse
durante su ejecución. Las relaciones de entrada - salida en un programa tienen
que ver con los siguientes aspectos:
·
Terminación del programa
·
Respuesta del programa
·
Correctitud del programa
·
Equivalencia con otros programas
·
Especialización del programa
Para
considerar estos aspectos se parte de una entrada dada al programa. La
terminación se refiere a si dada la entrada la secuencia de instrucciones del
programa logra un estado de parada, en tanto lo que el programa proporciona
como salida es la respuesta; si la salida es conforme a las especificaciones
del programa entonces éste es correcto. Dos programas son equivalentes si dada
la misma entrada las salidas son iguales. Un programa es una especialización de
otro si considerando un subconjunto de las entradas al programa original, es posible
modificarlo de tal manera que el programa modificado se ejecute a mayor
velocidad sobre el subconjunto de entradas.
Utilizando
lógica de primer orden la verificación de estos aspectos puede hacerse de la
siguiente manera: haciendo una descripción mediante un conjunto de axiomas del
flujo de ejecución del programa, de la entrada y de las operaciones
involucradas. A partir de estos axiomas el objetivo es deducir (derivar) las
fórmulas que describen la terminación, respuesta y correctitud del programa, así
como su equivalencia con otro y una especialización. Del cumplimiento o no de
estas derivaciones se desprende el resultado del análisis.
La
terminación del programa estaría dada por una cláusula de parada, la cual
describe las condiciones de terminación del programa. Cláusula de parada puede
haber más de una, cada una de las cuales es una respuesta de salida dada por el
programa. Si la fórmula que describe las especificaciones del programa junto
con una fórmula de parada es consecuencia lógica de los axiomas entonces el
programa es correcto. La equivalencia se prueba si dados los axiomas de
ejecución de los dos programas y compartiendo los axiomas de realización y
entrada, estos tienen como consecuencia lógica a los predicados de parada de
los dos programas.
El
flujo de ejecución del programa se hace mediante diagramas de estados y
transiciones, es decir mediante diagramas típicos de autómatas de Turing. Las
transiciones indican las condiciones que se deben satisfacer para que el
control de un programa pase de un estado a otro. Si dado el estado inicial
existe una secuencia de transiciones entre estados que conduzca a un estado
final, el programa termina y da una respuesta. De esta manera, el análisis de
un programa se realiza haciendo una traducción a fórmulas lógicas del autómata
de Turing que calcula las instrucciones del programa. La derivación de la
fórmula de parada a partir de los axiomas corresponde a que el autómata logra
el estado final para esa entrada.
Demostración Automática
La
Demostración (Razonamiento) Automática es la implementación en una computadora
de los procesos de inferencia de teoremas de una Teoría Lógica. Un demostrador
automático de una Teoría Lógica es un programa de computadora capaz de derivar
los teoremas de la teoría aplicando las reglas de inferencia ya sea sobre el
conjunto de axiomas, ó sobre los teoremas derivados previamente. Los ejemplos
de derivaciones de teoremas de los capítulos 1 y 2 de éste volumen son
realizables en un demostrador automático. Los primeros demostradores se
hicieron en la década de los sesenta, fundamentados en la Teoría de Modelos de
Herbrand de la Lógica de Primer Orden. La implementación descansó en el Método
de Davis Putnam, cuya generalización en el Principio de Resolución de A.
Robinson es omnipresente a la fecha en muchos demostradores. Junto con ello, el
método de Arboles Semánticos (Tableros Analíticos) es otra manera de realizar
demostración automática. El auge de distintos formalismos lógicos para la
representación de información diversa para la cual se requiere el uso intensivo
de la computadora, ha traído, a la par, el desarrollo de demostradores
automáticos para tales desarrollos.
Lógicas
no Clásicas e Inteligencia Artificial
La
complejidad y diversidad de la información que se maneja en una computadora, ha
impulsado el desarrollo de diversos formalismos lógicos para representar tal
información de manera clara y precisa. El objetivo ha sido fundamentar el
procesamiento computacional de información compleja en ingeniería, medicina, economía,
política, etc. Algunas de estos formalismos, que de manera genérica se
identifican como Lógicas no Clásicas, se estudian en los siguientes capítulos.
La lógica difusa (fuzzy logic), a manera de ejemplo, es utilizada en la
manufactura de dispositivos que utilizamos en la vida cotidiana tales como
hornos de microondas, lavadoras, planchas, etc.; su aplicación también se da en
dispositivos más sofisticados como aviones y satélites aeroespaciales. La
Lógica Modal, cuyo lenguaje, típicamente, es una extensión del lenguaje de la
Lógica de Primer Orden, hace posible el estudio formal, simbólico de conceptos
tales como conocimiento (Lógica Epistémica), creencia (Lógica Doxástica),
temporalidad (Lógica Temporal), normatividad (Lógica Deóntica), etc. Muchos de
estos desarrollos son producto de la así llamada Inteligencia Artificial ó
Computacional, cuyo objetivo es la implementación en una computadora de
procesos que emulen o reproduzcan conductas inteligentes, tales como el
aprendizaje, el razonamiento, la adaptación, entre otros.
Conclusiones
La
contribución fundamental de la Lógica a la Computación es haberle dado un
estatus matemático, básicamente al identificar el concepto informal de
algoritmo con el objeto matemático de Autómata de Turing. De hecho, en este
sentido, la Lógica puede considerarse una ciencia experimental, al implementar
una abstracción formal como interacciones de señales electrónicas en un entorno
físico. Es aquí donde radica la relación profunda entre Lógica y Computación.