Page 10 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

10

COMPUTABILIDAD

El primer tema que cae claramente dentro del campo de la teoría de la computación es el de
computabilidad. Iniciada por Gödel, Church, Post, Turing y Kleene, tiene sus raíces en la lógica
matemática.

Al iniciar el siglo xx, los matemáticos estaban a punto de efectuar grandes descubrimientos. Los
logros de los siguientes 40 años estaban destinados a sacudir las bases de las matemáticas y
tuvieron consecuencias que se extendieron al campo de las ciencias de la computación, aún por
nacer.

A principios de siglo xx se empezó a pensar sobre tópicos matemáticos que no tenían respuestas.
Georg Cantor (1845-1918), había inventado por entonces la teoría de conjuntos, pero al mismo
tiempo descubrió algunas paradojas inquietantes. Algunos de sus planteamientos podían ser
comprensibles (como que hay “infinitos” de distinto tamaño), pero otros no (por ejemplo, que
algún conjunto sea mayor que el conjunto universal). Esto dejo una nube de duda a los
matemáticos que ellos necesitaban disipar.

El punto de partida de despeje de dudas fueron las cuestiones fundamentales que David Hilbert
(1845-1918) 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
simultáneamente 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 o falsa?

La meta de Hilbert era crear un sistema axiomático lógico-matemático completo y
consistente, del cual podrían deducirse todas las matemáticas, esto es, cualquier
teorema matemático podría derivarse de los axiomas aplicando una serie finita de
reglas, es decir, mediante un proceso algorítmico o computacional. Su idea era
encontrar un algoritmo que determinara la verdad o falsedad de cualquier teorema
en el sistema formal. A este problema le llamo el ‘entscheidungs problem’.
David 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 surgen en 1931 con Kurt Gödel
(1906-1978) y su teorema de incompletitud: “Todo sistema de primer orden
consistente que contenga los teoremas de la aritmética y cuyo conjunto de
axiomas sea recursivo no es completo”. Como consecuencia no será posible
encontrar el sistema formal deseado por Hilbert en el marco de la lógica de primer
orden. Kurt Gödel

Una versión posterior y más general del teorema de Gödel elimina la posibilidad de considerar
sistemas deductivos más potentes que los sistemas de primer orden, demostrando que no pueden
ser consistentes y completos a la vez.