next up previous contents
Next: Universalidad y problemas Up: Sobre la Teoría Previous: Sobre la Teoría

Los comienzos de la Teoría. La Tesis de Church-Turing

El primer paso en la búsqueda de las respuestas a estas preguntas está en el estudio de los modelos de computación que serán los que nos harán preciso el concepto de algoritmo. Los modelos abstractos de computación tienen su origen en los años 30, bastante antes de que existieran los ordenadores modernos, en el trabajo de los lógicos Church, Gödel, Kleene, Post, y Turing. Estos primeros trabajos han tenido una profunda influencia no solo en el desarrollo teórico de las C.C., sino que muchos aspectos de la práctica de la computación que son ahora lugar común de los informáticos, fueron presagiados por ellos; incluyendo la existencia de ordenadores de propósito general, la posibilidad de interpretar programas, la dualidad entre software y hardware, y la representación de lenguajes por estructuras formales basados en reglas de producción.

El punto de partida de estos primeros trabajos fueron las cuestiones fundamentales que D. Hilbert formuló en 1928, durante el transcurso de un congreso internacional:

1.- ¿Son completas las matemáticas, en el sentido de que pueda probarse o no cada aseveración matemática?

2.- ¿Son las matemáticas consistentes, en el sentido de que no pueda probarse simultaneamente una aseveración y su negación ?

3.- ¿Son las matemáticas decidibles, en el sentido de que exista un método definido que se pueda aplicar a cualquier aseveración matemática, y que determine si dicha aseveración es cierta?.

La meta de Hilbert era crear un sistema matemático formal "completo" y "consistente", en el que todas las aseveraciones pudieran plantearse con precisión. Su idea era encontrar un algoritmo que determinara la verdad o falsedad de cualquier proposición en el sistema formal. A este problema le llamó el `Entscheidungsproblem'. Si Hilbert hubiera podido cumplir su objetivo, cualquier problema que estuviera bien definido se resolvería simplemente al ejecutar dicho algoritmo.

Por desgracia para Hilbert, en la década de 1930 se produjeron una serie de investigaciones que mostraron que esto no era posible. Las primeras noticias en contra de esta idea surgieron en 1931 cuando K. Gödel publicó su famoso Teorema de Incompletitud.

Teorema de incompletitud de Gödel. Todo sistema de primer orden consistente que contenga los teoremas de la aritmética y cuyo conjunto de (números de Gödel de) axiomas sea recursivo no es completo.

Para cualquier sistema de ese tipo, Gödel construye una fórmula que es satisfacible pero que no puede ser probada en el sistema. Como consecuencia no será posible encontrar el sistema formal deseado por Hilbert en el marco de la lógica de primer orden, a no ser que se tome un conjunto no recursivo de axiomas. El hecho de tener que considerar un conjunto no recursivo de axiomas escapaba a la mente de los matemáticos puesto que, incluso en la actualidad, no se conoce la forma de decidir en tales conjuntos si una fórmula es o no un axioma, y en consecuencia, tampoco si una demostración es o no válida. Ello no obstante, aún quedaba la posibilidad de pensar en sistemas deductivos más potentes que los sistemas de primer orden.

Una posterior versión, más general, del teorema de incompletitud de Gödel elimina esta posibilidad:

Teorema de incompletitud de Gödel (generalización). Ningún sistema deductivo que contenga los teoremas de la aritmética, y con los axiomas recursivamente enumerables puede ser consistente y completo a la vez.

Esto hace pensar, a nivel intuitivo, que no va a ser posible definir un sistema formal consistente y completo para las aseveraciones matemáticas. Los trabajos que siguieron al resultado de Gödel aportaron evidencias que reafirman esa idea intuitiva.

Un aspecto a destacar dentro del teorema de incompletitud de Gödel, debido a su gran relevancia en el posterior desarrollo de la teoría de la computabilidad, fué la idea de codificación. Se indica un método (numeración de Gödel) mediante el cual se asigna un número de código (entero positivo) a cada fórmula bien formada del sistema (fbf) y a cada sucesión finita de fórmulas bien formadas, de tal modo que la fbf o sucesión finita de fbf se recupera fácilmente a partir de su número de código. A través de este código, los enunciados referentes a enteros positivos, pueden considerarse como enunciados referentes a números de código de expresiones, o incluso referentes a las propias expresiones. Esta misma idea fué posteriormente utilizada para codificar algoritmos como enteros positivos, y así poder considerar un algoritmo, cuyas entradas fuesen enteros positivos, como un algoritmo cuyas entradas fuesen algoritmos.

El siguiente paso importante dentro de la teoría de la computabilidad lo constituye la aparición casi simultanea en 1936 de varias caracterizaciones independientes de la noción de calculabilidad efectiva. Estos artículos correspondian a los trabajos de Church, Kleene, Turing y Post. Los tres primeros mostraban problemas que eran efectivamente indecidibles; Church y Turing probaron además que el Entscheidungsproblem era un problema indecidible.

La noción de función efectivamente calculable que Church proponía era la de función -definible. Este concepto tiene su origen en un sistema lógico que en 1932-33 Church introdujo para fundamentar las matemáticas. Church empleó una notación formal que el denominó `cálculo lambda' para transformar todas las fórmulas matemáticas a una forma estandar. La demostración de teoremas se convierte así en una transformación de una cadena de símbolos en otra, en cálculo lambda, según un conjunto de reglas formales. Este sistema resultó ser inconsistente, pero la capacidad para expresar-calcular funciones numéricas como términos del sistema llamó pronto la atención de él y sus colaboradores. Así, Church habla en 1934 de la noción de función `efectivamente calculable' como función -definible.

En ese mismo año, Gödel habia recogido la idea de Herbrand de que una una función f podría definirse por un conjunto de ecuaciones entre términos incluyendo a la función f y símbolos para funciones previamente definidas. Gödel hizo precisa esta idea requiriendo que cada valor de f se obtenga de las ecuaciones por sustitución de las variables por números y los términos libres de variables por los valores que ya se habian probado que designaban. Esto define la clase de `las funciones recursivas de Herbrand-Gödel'.

En su artículo de 1936, Church hace un esquema de la demostración de la equivalencia entre las funciones -definibles y las funciones recursivas de Herbrand-Gödel (esta equivalencia también había sido probada por Kleene ); y aventura que estas iban a ser las únicas funciones calculables por medio de un algoritmo a través de la tesis que lleva su nombre:

Tesis de Church. La clase de las funciones que pueden ser calculadas mediante un algoritmo coincide con la clase de las funciones recursivas.

Además, bajo esa tesis y utilizando la noción de función -definible, dió ejemplos de problemas de decisión irresolubles, y demostró que el Entscheidungsproblem era uno de esos problemas.

Por otra parte, en el artículo de Kleene que se publicó pocos meses despues, se demuestra formalmente la equivalencia entre funciones -definible y funciones recursivas de Herbrand-Gödel, y se dan ejemplos de problemas irresolubles utilizando la noción de función recursiva.

La tercera noción de función calculable proviene del matemático inglés A. Turing. Este era alumno de M. Newman, quien leyó las cuestiones de Hilbert en Cambridge. Turing reflexionó sobre la frase de Newman "un proceso mecánico" y en 1936 publicó su célebre trabajo "Números Computables: Una Aplicación al Entscheidungsproblem".

Turing argumentó que la tercera cuestión de Hilbert (el Entscheidungsproblem) podía atacarse con la ayuda de una máquina, al menos con el concepto abstracto de máquina. El propósito de Turing al describir las máquinas que hoy llevan su nombre, era reducir los cálculos a sus rasgos esenciales más escuetos, describiendo de un modo sencillo algunos procedimientos básicos que son manifiestamente efectivos y a los que pueda reducirse cualquier procedimiento efectivo.

Turing postuló en su artículo antes citado que había tenido éxito en hacer lo que se habia propuesto, es decir, caracterizar de un modo matemáticamente preciso, por medio de sus máquinas, la clase de las funciones calculables mediante un algoritmo, lo que se conoce hoy como

Tesis de Turing. La clase de las funciones que pueden ser calculadas mediante un método definido coincide con la clase de las funciones calculables mediante una Máquina de Turing.

Aunque no se puede dar ninguna prueba formal de que una máquina pueda tener esa propiedad, Turing dió un elevado número de argumentos a su favor, en base a lo cual presentó la tesis como un teorema demostrado. Además, utilizó su concepto de máquina para demostrar que existen funciones que no son calculables por un método definido y en particular, que el Entscheidungsproblem era uno de esos problemas.

Cuando Turing redactó su articulo, desconocia los trabajos de Church-Kleene, pero durante el proceso de revisión tuvo conocimiento de estos trabajos de forma que cuando su artículo fué publicado le anexionó un apéndice demostrando que los conceptos de función -definible y función calculable por medio de una máquina de Turing coinciden. Naturalmente a la luz de esto la Tesis de Turing resulta ser equivalente a la de Church.

Finalmente, cabe reseñar el trabajo de E. Post. Este estaba interesado en marcar la frontera entre lo que se puede hacer en matemáticas simplemente por procedimientos formales y lo que depende de la comprensión y el entendimiento. De esta forma, Post formula un modelo de procedimiento efectivo a través de los llamados sistemas deductivos normales. Estos son sistemas puramente formales en los que puede `deducirse' sucesiones finitas de símbolos como consecuencia de otras sucesiones finitas de símbolos por medio de un tipo normalizado de reglas y a partir de un conjunto de axiomas. Así pues, dada una sucesión finita de símbolos como entrada, las reglas permiten convertirla en una sucesión finita de salida. En su artículo, Post demostró resultados de incompletitud e indecibilidad en estos sistemas.

Post conocía los trabajos de Church-Kleene, si bien desconocia el trabajo de Turing, de tal forma que el modelo de procedimiento efectivo de Post, en esencia, difiere muy poco de las máquinas de Turing.

Los resultados hasta ahora citados, correspondientes al periodo 1931-36, se refieren a funciones totales. La existencia de algoritmos que con determinadas entradas nunca terminan, condujo de forma natural a considerar funciones parciales. Kleene fué el primero en hacer tal consideración en 1938. El estudio de estas funciones ha mostrado la posibilidad de generalizar todos los resultados anteriores a funciones parciales. Por otro lado, el estudio de las funciones parciales calculables ha resultado esencial para el posterior desarrollo de la materia. De hecho las funciones parciales son necesarias para la demostración del teorema del punto fijo, y en particular del primer teorema de recursión de Kleene (1952).

Posteriormente, se demostró la equivalencia entre lo que se podía calcular mediante una máquina de Turing y lo que se podía calcular mediante un sistema formal en general:

Teorema. En los sistemas deductivos donde el conjunto de reglas de producción, y el conjunto de axiomas sea recursivamente enumerable, una función (parcial) aritmética es calculable si y solo si es una función (parcial) recursiva.

A la vista de estos resultados, la Tesis de Church-Turing es aceptada como un axioma en la teoría de la computación, postulado que ha servido como punto de partida para la investigación de los problemas que se pueden resolver mediante un algoritmo.



next up previous contents
Next: Universalidad y problemas Up: Sobre la Teoría Previous: Sobre la Teoría




Wed Jan 10 14:35:14 WET 1996