Matías Alvarado
Centro de Investigación en Computación
Instituto Politécnico Nacional, México
En este capítulo se explica la relación entre la Lógica Matemática y la Ciencia de la Computación. La secuencia de instrucciones que lleva a cabo una computadora para realizar cualquier tarea, es siempre traducible a secuencias de enunciados en un formalismo lógico. Y viceversa. De esta manera, los alcances y limites de lo realizable por una computadora están dados por los alcances y limitaciones teóricamente establecidos para la lógica.
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.
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 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.
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.
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.
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.
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.
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.
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.
Ejemplo
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.
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.
[1] Alan Turing fue el líder del grupo de científicos en el Reino Unido, quienes durante la Segunda Guerra Mundial descifraron los mensajes enviados entre el ejército alemán, y de esta manera fundamental contribuyeron a la victoria de los aliados (EEUU, Reino Unido y la ex Unión Soviética) sobre los nazis de Adolfo Hitler.
[2] Matemáticamente, el control de los movimientos de la cabeza es una función, y en general, es una relación (producto cartesiano sobre el conjunto de símbolos o alfabeto).
[3] Más adelante repasaremos el concepto de Teoría Lógica. También puede verse en el Capítulo X de este libro.
[4] En particular, los axiomas se consideran teoremas de la teoría, los cuales se derivan aplicando cero veces las reglas de inferencia.
[5] El autómata es finito en consecuencia. Pese a ello, en ocasiones entran en ciclos infinitos, cuyas implicaciones veremos más adelante.
[6] Semánticamente, cada palabra tiene un significado, el cual depende, a su vez, del contexto en el cual se menciona; esto último concierne a la pragmática del lenguaje.
[7] El control del autómata que regula las transiciones del estado inicial al estado final del autómata puede considerarse una memoria que no requiere de ningún almacén externo para guardar nada.
[8] El monitor de la computadora es el dispositivo en el cual se muestra las salidas, al igual que la impresora.
[9] Actualmente, hay algunas propuestas que buscan esta generalización de Máquina de Turing. Es oportuno advertir al lector que el añadirle una o más cintas a una MT, o permitirle acceso de lectura aleatorio, no añade poder ni generalidad a una MT.
[10] Un conjunto es infinito numerable si puede ser contado con los números naturales (enteros positivos). En caso contrario un conjunto es infinito no numerable.
[11] En particular, los axiomas se consideran teoremas de la teoría, los cuales se derivan aplicando cero veces las reglas de inferencia.