Teorías Lógicas y Máquinas de Turing
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. 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. 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.
En particular, los axiomas se consideran teoremas de la teoría, los cuales se derivan aplicando cero veces las reglas de inferencia
No Computabilidad Se ha visto que los algoritmos son un concepto fundamental de la ciencia de la computación y se ha desarrollado cierto conocimiento interno sobre la forma en que pueden construirse. Se sabe que existen algoritmos para tejer un suéter, construir un modelo de aeroplano, preparar un pastel y ejecutar una sonata de Beethoven. Es conocido que las computadoras pueden controlar señales de tráfico, líneas de producción y plantas químicas. Pueden llevar las revisiones de vuelos en líneas aéreas, controlar robots y producir nominas. Existen algoritmos para preparar una taza de café, determinar cual es el mayor de un conjunto de números, descubrir si un número es primo o no o no primo e imprimir el máximo común divisor de 2 números. Desde la época escolar se recuerda que existen algoritmos para sumar, resta, multiplicar y dividir números enteros y para calcular raíces cuadradas. Sin duda existen algoritmos para calcular logaritmos, determinar la frecuencia de las palabras en un fragmento dado de texto y controlar un submarino nuclear. Existen trabajos que las computadoras no pueden realizar. Hay muchas cosas que una computadora no puede hacer. En realidad, el número de cosas que pueden calcularse o computarse es infinitesimal en comparación con el número de cosas que a uno le gustaría calcular, las computadoras no pueden hacer muchas cosas. Historia de la Computabilidad La idea de disponer de un algoritmo, o receta para efectuar alguna tarea, ha existido durante miles de años. También durante muchos años la gente creyó que si cualquier problema podía iniciarse de manera precisa, entonces con suficiente esfuerzo seria posible encontrar una solución con el tiempo(o tal vez una prueba de que no existe solución podría proporcionarse con el tiempo). En otras palabras, se creía que no había problema que fuera tan intrínsicamente difícil que en principio nunca pudiera resolverse. Uno de los grandes promotores de esta creencia fue el famoso matemático David Hilbert. En cierta ocasión afirmo: “Todo problema matemático definido debe ser necesariamente susceptible de un planteamiento exacto, ya sea en forma de una respuesta real a la pregunta planteada o debido a la constatación de la imposibilidad de resolverlo, a lo que se debería la falla necesaria de todos los intentos… una de las cosas que nos atrae mas cuando nos dedicamos a un problema matemático es precisamente que dentro de nosotros siempre escuchamos la llamada: e aquí el problema, busca la solución; puedes encontrarla por pensamiento puro, ya que en matemáticas no existe cosa alguna que no pueda conocerse. ” La meta de Hilbert era crear un sistema matemático formal en el que todos los sistemas pudieran plantearse con precisiones y términos de proposiciones que fueran verdaderas o falsas. Su idea era encontrar un algoritmo que, dada cualquier proposición en el sistema formal, determinara si esa proposición era o no verdadera. Si Hilbert hubiera logrado este objetivo, entonces cualquier problema que estuviera bien definido podría haberse resuelto simplemente al ejecutar el algoritmo. Al decidir la verdad de una proposición dada en el sistema formal, Hilbert lo denominó entscheidungsproblem, considerándolo como un problema abierto fundamental en matemáticas. Por desgracia para el objetivo de Hilbert, en la década de 1930 se produjo una serie de investigaciones que mostraron que el entscheidungsproblem no es computable. Es decir, no existe algún algoritmo del tipo que buscaba Hilbert. Un cínico podría decir que los matemáticos dieron un suspiro de alivio, porque si hubiera tal algoritmo, todos se quedarían sin trabajo en cuanto se le encontrara. Sin embargo a los matemáticos les sorprendió este notable descubrimiento. Las primeras noticias del descubrimiento surgieron en 1931 cuando Kurt Gödel publicó su ahora famoso “teorema de la incompletez”. Entre otras cosas, este teorema mostró que no existe algún algoritmo cuya entrada puede ser cualquier no verdad. Siguiendo cerca de Gödel otros matemáticos más tales como Alonso Church, Stephen Kleene, Mil Post, Alan Turing y muchos otros, encontraron más problemas que carecían de solución algorítmica. Tal vez la característica más notable de estos primeros resultados sobre problemas que no pueden resolverse por medio de las computadoras es que se obtuvieron en la década de 1930 antes de que se hubieran construido las primeras computadoras. Tesis de Church-Turing. Existe un obstáculo importante al probar que no existe un algoritmo para una tarea específica. Primero es necesario saber con exactitud que significa algoritmo. Cada uno de los matemáticos mencionados anteriormente había superado este obstáculo, cada definiendo “algoritmo” de una manera diferente. Gödel definió un algoritmo con una secuencia de reglas para formar funciones matemáticas complicadas a partir de funciones matemáticas más simples. Church utilizó un Pág. 4 formalismo denominado calculo lambda, mientras que Turing empleo una maquina hipotética conocida como máquina de Turing. Turing definió un algoritmo como cualquier conjunto de instrucciones para su máquina simple. Entonces, ¿por qué debe cualquiera dar atención a resultados acerca de algoritmos definidos en formas tan diversas y oscuras? La respuesta es que todas las definiciones en apariencia diferentes y creadas de manera independiente resultan equivalentes. Esto es, si algo puede calcularse a partir de un algoritmo definido de una forma, entonces también puede calcularse a partir de un algoritmo definido en cualquiera de las otras formas. Conforme los investigadores se dieron cada vez mas cuanta de esta equivalencia en la década de 1930, se creyó en forma amplia en las 2 proposiciones que siguen: - Todas las definiciones razonables de “algoritmos” conocidas hasta el momento son equivalentes. - Cualquier definición razonable de “algoritmo” que se legue a dar, a su vez será equivalente a definiciones ya conocidas. Estas creencias han llegado a denominarse Tesis Church-Turing en honor a dos de los primeros trabajadores que se dieron cuenta de la naturaleza fundamental del concepto que habían definido juntos. Hasta el momento, no ha surgido evidencia en contra y se acepta ampliamente la Tesis de Church-Turing. La Tesis mencionada tan sólo anuncia que se considera tener una buena definición para lo que es un algoritmo. Cualquiera tiene una sensación intuitiva acerca de lo que significa efectuar una tarea en la forma rutinaria o mecánica. Las personas tienen un manejo intuitivo del concepto de plantear un conjunto de instrucciones o pasos para efectuar alguna tarea y dar después las instrucciones a una persona o máquina para solamente ejecución sistemática. A tal conjunto de instrucciones a lo que se considera como algoritmo y la Tesis Church-Turing asegura que las definiciones precisas de algoritmo que se utilizan en las ciencias de la computación en realidad coinciden con estas ideas informales que poseen las personas. Abreviando, se cree que siempre que se escriba algún conjunto de pasos que se consideren podrían ejecutarse de una manera puramente sistemática, entonces existe un algoritmo formal en el sentido que da la ciencia de la computación a la palabra para la misma tarea. En un planteamiento moderno, es posible definir algoritmo como cualquier cosa que pueda ejecutarse en una computadora. Por fortuna, la computadora que se elija no importa para la definición, ya que cualquier algoritmo que pueda implantarse en una computadora también puede implantarse en cualquier otra. Esto se cumple debido a que todas las computadoras pueden simularse unas a otras. Es decir, dadas 2 computadoras cualesquiera es posible escribir un programa para una de ellas que pueda comprender y ejecutar cualquier programa escrito para la otra. A tal programa se le denomina intérprete (o simulador o programa universal). La equivalencia entre todas las computadoras modernas, y su equivalencia con las máquinas de Turing y los otros numerosos medios de definir algoritmos, es una evidencia más de la Tesis Church-Turing. La existencia de intérpretes, según se analizó antes, es en sí misma una propiedad interesante y notable de los algoritmos. Aún no es auto-evidente, es verdadero para cualquier lenguaje de programación que existe un intérprete que, dada la descripción de cualquier programa en el lenguaje, pueda simular ese programa. Por tanto, el intérprete puede efectuar cualquier tarea que cualquier otro programa pueda realizar. Esta notable propiedad de los algoritmos se denomina universalidad. En términos informales, universalidad significa que cualquier computadora es equivalente a todas las otras en el sentido de que todas pueden efectuar las mismas tareas. Entonces, ¿por qué las personas eligen una computadora y no otra? La razón es que ciertas computadoras corren mas rápido que otras, algunas son más fáciles de programar, otras ya tienen programas escritos para ellas y puede resultar poco económico escribir los programas para otra computadora, y algunas tienen más memoria de manera que pueden ejecutar más programas largos con mayor velocidad. Entonces, aún cuando todas las computadoras pueden realizar las mismas tareas, no necesariamente consumen la misma cantidad de recursos al efectuar una tarea dada. Problemas No Computables Problemas de Detención Existen muchos problemas que son no computables. Esto es, no hay un algoritmo para resolver tal problema. Este es un enunciado muy fuerte. Se esta afirmando algo mucho mas profundo que cuándo se dice que no se conoce un algoritmo para resolver el problema. Se está indicando que nunca se conocerá tal algoritmo: que nunca será posible conocerlo debido a que no existe. Un problema no computable es el de Hilbert y Gödel referente a las superaciones fundamentales Pág. 5 con números. A continuación vamos a describir un problema en apariencia simple de la ciencia de la computación y se prueba que ningún algoritmo puede resolverlo. Un problema común entre las instalaciones de computadoras de todo el mundo es que al escribir programas las personas cometen errores que a menudo impiden que los programas terminen. En el habla común los programadores dicen “¡mi programa entró en un ciclo infinito!” Resulta claro que seria beneficioso si los programadores pudieran detectar la existencia de ciclos infinitos en sus programas antes de desperdiciar recursos de la computadora al ejecutarlos. Por lo tanto el problema que sería conveniente resolver es el de determinar si un programa arbitrario contiene un ciclo infinito. Planteando esto de otra forma, el problema consiste en determinar si un programa arbitrario se detiene o no. A esto se le denomina problema de detención. Su solución es un algoritmo que, dado un programa arbitrario P y sus datos de entrada D, puedan indicarnos si P con el tiempo se detendrá o no al ejecutarse con los datos de entrada D. Por el momento la solución al problema de detención que se utiliza en la mayoría de las instalaciones de computadora es registrar el tiempo que tarda cada programa mientras se está ejecutando y abortar de manera forzosa el programa si éste utiliza más tiempo del que se le asignó. Sin embargo, ésta es una solución indeseable por dos razones. En primer lugar, los programas que no terminan desperdiciarán todo el tiempo que se les haya asignado. En segundo lugar, puede suceder en ciertos programas que el programador no pueda calcular el tiempo necesario y por tanto un programa podría abortarse poco antes de que se detuviera con éxito de otra manera. Entonces, se podría esperar que las instalaciones en todo el mundo invirtieran considerables esfuerzos intentando plantear un algoritmo para resolver el problema de detención. Si lo están haciendo, desperdician su tiempo porque no existe tal algoritmo. El problema de detención es no computable. Esto puede probarse como sigue. Considérese por el momento que existe un algoritmo para resolver el problema de detención. Denótese este algoritmo como pruebadetención. Como se mencionó antes, el algoritmo tiene dos entradas P y D de manera que pruebadetención (P,D) imprimen la respuesta “bien” si el programa P terminara al ejecutarse con datos de entrada D, e imprime “mal” de otra manera. En la figura de abajo se ilustra la acción de pruebadetención. P D P ¿Se detiene P(D)? ¿Se detiene P(P)? Sí No Sí No Dar salida a “BIEN” Dar salida a “MAL” dar salida a “BIEN” dar salida a “MAL” Y detenerse y detenerse y detenerse y detenerse Ya que pruebadetención prueba la terminación de un programa P para cualesquiera datos D, es posible utilizarlo para construir un algoritmo más limitado que pruebe la terminación de P cuando los datos son P mismo. Un programa es una representación de un algoritmo y simplemente consta de una secuencia de caracteres (tales como letras y dígitos). Cualquier secuencia de caracteres puede ser la entrada a un programa de computadora. Si el programa puede o no hacer algo razonable con la entrada es otro asunto. En realidad existen muchos programas de interés práctico cuya entrada es una secuencia de caracteres que representan otro programa: son ejemplos de esto compiladores y editores. Se denotará como prueba detención a esta versión limitada dper uebadetención. Nuevapruebadetención puede escribirse como Module nuevapruebadetención(P) {Verificar si el programa P se detiene si se ejecuta con los datos P} pruebadetención(P,P) Si se considera que existe un algoritmo pruebadetención y que por tanto existe nuevapruebadetención, es posible construir el algoritmo que sigue, denominado divertido, que tiene sólo una entrada P. Pág. 6 Module divertido(P) {A fin de escribir este módulo se considera que existe pruebadetención} if nuevapruebadetención(P) da como salida “MAL” then detención else ciclo interminable P divertido ¿Se detiene P(P)? ¿Se detiene divertido(divertido)? Sí No Sí No Ciclo interminable detención ciclo interminable detención` En la figura de arriba se ilustra la acción del algoritmo divertido . Por último, se considera lo que sucede durante la ejecución de divertido(divertido): esto es, durante la ejecución de divertido con su propio texto de programa como entrada P. (Esto es legítimo ya que P puede ser cualquier secuencia de caracteres.) La ejecución de divertido(divertido) se ilustra en la figura anterior. Esta figura demuestra con claridad una contradicción, ya que ilustra por una parte que si divertido(divertido) cae en un ciclo infinito, entonces se detiene. La contradicción sólo puede resolverse al admitir que el algoritmo divertido no puede existir. Sin embargo, la única consideración que se hizo al obtener divertido fue que pruebadetención existía. Por ende si divertido no puede existir entonces tampoco puede existir pruebadetención. Por tanto se ha demostrado que no puede existir algoritmo alguno pruebadetención para resolver el problema de detención y por tanto el problema de detención no es computable. Se ha mostrado que no existe algoritmo que pueda resolver el problema de detención. ¿qué significa esto? Es seguro que existen algunos programas que sean tan simples que resulte obvio si se detienen o no. Desde luego los hay, pero existen muchos otros que de ninguna forma son tan obvios. Por ejemplo, considérese un algoritmo para probar la verdad del último teorema de Fermat. En este teorema se enuncia que no existen enteros positivos a, b y c tales que a_+b_=c_ . Por el momento no se conoce prueba a favor o en contra de este teorema, aunque Fermat afirmó tener una prueba. Un posible algoritmo para probar el teorema es Module fermat(n) {Prueba el último teorema de Fermat con la entrada n } repeat para a = 1, 2, 3,…… repeat para b = 1, 2, 3, …., a repeat para c = 2, 3, 4, …., a + b if a_+b_=c_ then dar salida a a, b, c y 2 y detenerse El algoritmo prueba de forma exhaustiva todos los enteros positivosa , b y c tales que a_+b_=c_. Si el algoritmo se detiene para una entrada específica n<2 entonces se habrá probado que el último teorema de Fermat es falso. Resulta fácil ver que el algoritmo se detendrá cuando la entrada n es 1, ya que cuando a=1, b=1 y c=2 se sabe que a1+b1=c1. De manera semejante, cuando la entrada n es 2 resulta fácil determinar que el algoritmo se detendrá, ya que a+b=c cuando a=3, b=4 y c=5. Cuando la entrada n es 3 no resulta tan fácil determinar si el algoritmo se detendrá o no. Sin embargo, con ingenio es probar que el algoritmo nunca se detendrá. ¿Qué sucede cuando n=37? De nuevo, una gran cantidad de ingenio humano pude mostrar que el algoritmo nunca se detendrá. ¿Qué pasa si n es muy grande? Por el momento nadie lo sabe. El ejemplo ilustra que en algunos casos el problema de detención es fácil de resolver. En otros es muy difícil, y se necesita mucha creatividad. En algunos casos más, tal como una entrada muy grande al algoritmo anterior, el problema de detención aún está por resolverse. El punto importante es que no existe un método puramente mecánico (esto es, no hay un algoritmo) que garantice que resuelva el problema de detención en todo caso. Desde luego, es posible diseñar un algoritmo que resuelva el problema de detención en algunos casos, pero es seguro que el algoritmo fallará con algunas otras entradas. En realidad no es tan difícil mostrar que cualquier algoritmo propuesto para el problema de detención fallará cuando Pág. 7 se tenga una cantidad infinita de entradas, resulta aún más interesante el hecho de que existe un algoritmo que, dado cualquier algoritmo propuesto para el problema de detención, puede producir una entrada en la que fallará el algoritmo propuesto, si no que no es muy difícil determinar en donde fallará. En este análisis se ha manifestado la diferencia entre un algoritmo de rutina y la aplicación de la creatividad humana a la solución de un problema. Descubrir Problemas No Computables Acaba de considerarse un problema que carece de solución algorítmica. El problema de detención no puede resolverse por medio de cualquier programa escrito en cualquier lenguaje para cualquier computadora. La pregunta es espontánea, a la que ahora se pasará es qué otros problemas no son computables. El método de prueba de la sección anterior (diagonalización que está relacionado con la prueba de Cantor de que existen más números reales que enteros), es tedioso y tal vez difícil de seguir. Por tanto, en vez de repetir una prueba semejante para cada problema no computable, tan solo se mostrará que si el problema de que se trata fuera computable, entonces también lo sería el problema de detención. Desde luego se sabe que el problema de detención no es computable por lo que tampoco lo será el problema de que se trate. Recuérdese que el problema de detención consiste en determinar si un programa arbitrario P se detendrá o no al ejecutarse con datos arbitrarios de entrada D. Una cuestión relacionada es si un programa arbitrario P se detendrá o no con todas las entradas. A esto se le denomina problema de totalidad. Se dice que P es total si P(D) se detiene para todos los datos de entrada D. No es sorprendente que el problema de totalidad sea no computable. De otra forma, dados P y D cualesquiera, simplemente se podría construir un programa especial para P y D que no tomara en cuenta su entrada y simulara P(D). Este programa especial se denominará divertidopd y se escribe module divertidopd(I) {I es la entrada, pero el módulo no la emplea} se simula el programa P con la entrada de datos D Ahora preguntar si divertidopd es total equivale a preguntar si P(D) se detiene. De manera que un algoritmo para el problema de totalidad también proporcionaría el algoritmo que sigue para el problema de detención. module pruebadetención(P,D) {A fin de escribir este módulo se considera que existe un algoritmo para el problema de la totalidad} construye el texto del programa divertidopd if divertidopd es total then dar salida a “BIEN” y detenerse else dar salida a “MAL” y detenerse Sin embargo, se sabe que no existe algoritmo para el problema de detención. En consecuencia, la consideración de que existe un algoritmo que resuelva el problema de totalidad es falsa. Por tanto se ha probado que el problema de totalidad no es computable. Otro problema no computable surge en el problema de una compañía que está instalando una nueva computadora. Supóngase que la compañía tiene un gran número de programas que han estado corriendo libres de errores durante años en la computadora anterior. Los programadores acaban de escribir un conjunto de nuevos programas para las mismas tareas que se correrán en la nueva computadora. ¿Cómo es posible que la compañía se asegure de que los nuevos programas sean tan confiables como los anteriores? Resulta claro que la compañía necesita un algoritmo que tome dos programas cualesquiera, uno anterior y uno nuevo, y los compare para determinar si efectúan el mismo trabajo (es decir para la misma entrada produzcan la misma salida). A esto se le denomina problema de equivalencia. Por desgracia, el problema de equivalencia no es computable. Dicho de otra forma, dado cualquier P, podría construirse simplemente para ese P un programa especial que simule P y dé a “13” si P se detiene con el tiempo. (Desde luego si P no se detiene, el programa que efectúa la simulación tan solo continúa simulando P para siempre.) A este programa especial podría denominársele divertidop y escribirse module divertidop(D) {Da salida a “13” si P(D) se detiene alguna vez} simular el programa P con los datos de entrada D {el paso anterior puede entrar en un ciclo interminable, pero si no lo hace entonces…} Pág. 8 dar salida a “13” Considérese ahora un programa simple que siempre da salida a “13” module simple(D) {D es la entrada, pero el modulo no la toma en cuenta dando salida a “13”} salida “13” Ahora preguntar si divertidop es equivalente a simple es lo mismo que preguntar si P es total. La razón es que si P se detiene con toda entrada, entonces divertidop dará salida a “13” con toda entrada, mientras que si existe alguna entrada para la que P no se detiene, entonces divertidop no se detendrá y no dará salida a “13” con esa entrada. De manera que un algoritmo para el problema de equivalencia también proporcionará un algoritmo en el problema de totalidad como sigue: module total(P) {A fin de escribir este modulo se considera que existe un algoritmo para el problema de equivalencia.} construir el texto del programa divertidop construir el texto del programa simple if divertidop y simple son equivalentes then dar salida a “P es total” else dar salida a “P no es total” Sin embargo, se probó antes que no existe un algoritmo para el problema de totalidad. Por tanto la consideración de que existe un algoritmo para el problema de equivalencia es falsa. Por ende se ha probado que no existe algoritmo para resolver el problema de equivalencia. Ya por último, mencionamos los cuatro últimos grupos de problemas: • Dadas dos gramáticas de contexto libre arbitrarias, el asunto de si representan o no el mismo lenguaje de programación es no computable. En realidad, no existe algún algoritmo para indicar si existe o no cualquier secuencia de caracteres que sea gramaticalmente correcta en ambos lenguajes. Al menos podría esperarse que, dada una gramática arbitraria de contexto libre, sea posible determinar si existe cualquier secuencia no gramatical de caracteres. Pero ni siquiera esto es computable. • El problema de la palabra para Grupos.- Dado un subconjunto S de elementos de un grupo G, se trata de decidir si una expresión compuesta por elementos de S y con las operaciones del grupo es igual al elemento neutro del grupo. Durante muchos años se buscaron ejemplos de grupos finitamente presentados para los que este problema fuese indecidible. La existencia de uno de estos grupos fue encontrada por Novikov en 1955 y por Boone en 1957. En el álgebra moderna hay abundantes ejemplos de interesantes problemas no computables; una gran cantidad de ellos sobre propiedades de palabras o generadores semejantes al problema de la palabra para grupos. • Décimo problema de Hilbert. Una ecuación diofántica es la ecuación de los ceros enteros de un polinomio con coeficientes enteros. El décimo problema de Hilbert, propuesto en 1900, pregunta si hay un procedimiento efectivo que determine si una ecuación diofántica tiene o no solución. Y Matiyasevich demostró en 1970 que este problema no tiene solución. • Decibilidad de las teorías lógicas. El desarrollo de la teoría de la computabilidad ha ido íntimamente ligado al desarrollo de la lógica matemática. Esto ha sido así porque la decibilidad de los distintos sistemas lógicos es una cuestión fundamental. Es bastante fácil ver que el cálculo proposicional es decidible. Church y Turing demostraron en 1936 que el cálculo de predicados no era decidible. Por otro lado, para cada una de las distintas teorías se ha ido estudiando su posible decibilidad. Como ejemplo más ilustrativo, Tarski demostró que la teoría de los números reales era decidible. Problemas No Computables desde la Máquina de Turing El Problema de Detención La Máquina de Turing es el modelo matemático formal del concepto de algoritmo. Así que un lenguaje que no se puede resolver por Turing no puede ser resuelto por ningún algoritmo: puede Pág. 9 no haber una forma general y sistemática de expresar que cadenas están en el lenguaje y cuales no. El primer lenguaje que no puede ser resuelto por Turing que encontramos consiste en las codificaciones de ciertas máquinas de Turing; desde un punto de vista práctico, éste es un ejemplo artificial poco satisfactorio. Pero podemos demostrar que, como consecuencia de la no resolución de este lenguaje, una variedad de lenguajes más naturales que describen las máquinas de Turing y gramáticas libres de contexto deben ser también no resolutivas. Según la teoría de Church, la no resolución de estos lenguajes implica que las correspondientes preguntas no pueden ser respondidas mediante algoritmos de ningún tipo. Por ejemplo, siendo K aceptable por Turing, pero no resolutiva por éste, podemos ver K como un diccionario infinito que responde a preguntas del tipo: ¿acepta la máquina de Turing M la entrada w? Ya que no hay ninguna máquina de Turing que decida K, podemos concluir que no hay algoritmo que resuelva, , para una máquina de Turing arbitraria y una entrada w, si M acepta o no w. Éste es uno de los problemas no computables más famosos: el problema de detención(halting problem) para máquinas de Turing. Nótese que este resultado imposible de resolver de ninguna manera implica que no puede haber ciertas circunstancias bajo las que es posible predecir si una máquina de Turing parará en una cadena de entrada. Podríamos examinar la codificación de la máquina, por ejemplo, para comprobar si el estado de parada h esta representado en algún lugar; si no, la máquina no puede aceptar ninguna cadena de entrada. Estoe y otros análisis más ejemplos podrían ofrecer más información; pero los resultados de esta sección afirma que cualquiera de estos análisis deben finalmente ser interminables u ofrecer resultados incorrectos: no hay ningún método completamente general que resuelva todos los casos correctamente. Además, hay ciertas máquinas particulares para las que no hay un método general para decir, dada una entrada, si la máquina aceptará o parará en tal entrada. Esto surge del hecho de que K es aceptable por Turing pero no resolutiva. Así que si M es una máquina de Turing que acepta K, entonces no puede existir una máquina de Turing que resuelva si una entrada arbitraria dada es aceptada por M o no. A partir de esto podemos afirmar: • No hay ningún algoritmo para determinar, dada una máquina M y una entrada w, si M acepta a w. • Para cierta máquina de Turing fijada M, no hay ningún algoritmo para determinar, dada una entrada w, si M acepta a w. Otros Problemas que No Pueden Ser Resueltos por Máquinas de Turing Los siguientes problemas sobre máquinas de Turing no son computables: • Dada una máquina de Turing M, ¿parará en la cinta vacía? • Dada una máquina de Turing, ¿hay una cadena en la que M parará? • Dada una máquina de Turing M,¿parará en cada cadena de entrada? • Dadas dos máquinas de Turing M1 y M2, ¿pararán en las mismas cadenas de entrada? • Dada una máquina de Turing M, ¿es el lenguaje M libre de contexto? ¿Es resolutivo por Turing? Casi ninguna pregunta no trivial que alguien podría preguntar sobre máquinas de Turing es improbable tener una respuesta que venga dada por un algoritmo. Ya que hemos considerado las máquinas de Turing como versiones formales de algoritmos, esto supone que muchas preguntas sobre algoritmos no pueden ser respondidas por algoritmos. Una pregunta típica de este tipo es la última. Traducida a términos más generales, ésta dice que cualquier tipo de lenguaje puede ser usado para expresar todos los procedimientos computacionales, y no hay forma sistemática de decir si un conjunto de instrucciones dado realmente describe un procedimiento que garantiza terminar y ofrecer una respuesta, no importa que entrada se dé. Evidentemente, resultados implican que las posibilidades son inherentemente limitadas para programas computacionales que analizan y predicen el comportamiento de otros programas computacionales. Por ejemplo, el problema de verificación del programa, que es, determinar si un programa computacional funciona correctamente bajo todas circunstancias, no puede resolverse en general, aunque se ha empleado mucho esfuerzo en el desarrollo de métodos para verificar tipos de programas restringidos. Problemas No Computables Sobre Gramáticas Libres de Contexto Debido a la estrecha relación entre gramáticas y máquinas de Turing, la no resolución de algunos problemas sobre gramáticas es fácil de demostrar. Cada uno de los siguientes problemas son no computables: Pág. 10 • Para una gramática arbitraria dada G y una cadena w, determinar si w pertenece a L(G). • Para cierta gramática fijada G y una cadena arbitraria w, determinar si w ι L(G). • Para dos gramáticas arbitrarias G1 y G2, determinar si L(G1)=L(G2). • Para una gramática arbitraria G, determinar si L(G)= Λ Cualquier procedimiento de decisión de estos problemas inmediatamente implicaría la resolución de un problema no computable sobre máquinas de Turing. Por ejemplo, supongamos que el primero fuera computable. Entonces podríamos proceder como sigue a determinar, para cualquier máquina de Turing M y una cadena w, si M acepta a w. Simplemente produciríamos una gramática G tal que L(G) sea el lenguaje aceptado por M. Entonces en vez de preguntar si M acepta a w, preguntar si w ι L(G); las dos preguntas tienen la misma respuesta. Así que la resolución del problema primero contradiría el teorema que dice que el siguiente problema, antes expuesto, no es computable: dada una máquina de Turing M y una entrada w, ¿para M en la entrada w?. Ocurriría lo mismo con el resto de los problemas.
