Page 11 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

11

Los resultados de Gödel prueban que no sólo no existe un algoritmo que pueda demostrar todos
los teoremas en matemáticas, sino que, además, no todos los resultados son demostrables.
Entonces cabe plantearse las siguientes preguntas:

 ¿Qué pueden hacer los ordenadores (sin restricciones de ningún tipo)?
 ¿Cuáles son las limitaciones inherentes a los métodos automáticos de cálculo?

A estas cuestiones pretende responder la teoría de la
computabilidad. El primer paso en la búsqueda de las
respuestas a estas preguntas está en el estudio de los modelos
de computación.

Los modelos abstractos de cálculo tienen su origen en los años
30, antes de que existieran los ordenadores (el primer
computador electrónico de propósito general fue el ENIAC
que se desarrolló a partir del año 1943), en el trabajo de los
lógicos Church, Gödel, Kleene, Post, y Turing. ENIAC

Estos primeros trabajos han tenido una profunda influencia no sólo en el desarrollo teórico de las
ciencias de la computación, sino que muchos aspectos de los prácticos de la informática 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.

Alonzo Church propuso la noción de función “λ-definible” como función efectivamente
calculable. La demostración de teoremas se convierte en una transformación de una cadena de
símbolos en otra, según un conjunto de reglas formales, que se conocen como lambda calculo.

En 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 conjetura 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) y utilizando la noción
de función “λ-definible”, dio ejemplos de problemas de decisión irresolubles y demostró que el
“Entscheidungs Problem” era uno de esos problemas.

Por otra parte, Kleene, pocos meses después, demuestra de forma independiente la equivalencia
entre funciones “λ-definibles” y funciones recursivas de Herbrand-Gödel, a través del concepto
de función recursiva y da ejemplos de problemas irresolubles.

La tercera noción de función calculable proviene del matemático inglés Alan Turing (1912-1954).
Turing señaló que había tenido éxito en caracterizar de un modo matemáticamente preciso, por
medio de sus máquinas, la clase de las funciones calculables mediante un algoritmo (Funciones
Turing-Computables), lo que se conoce hoy como Tesis de Turing (1936). Aunque no se puede
dar ninguna prueba formal de que una Máquina de Turing pueda tener esa propiedad, Turing dio
un elevado número de argumentos a su favor, en base a lo cual presentó la tesis como un teorema
demostrado.

Además, utilizo su concepto de máquina para demostrar que existen problemas que no son
calculables por un método definido y en particular, que el “Entscheidungs Problem” era uno de
esos problemas. Cuando Turing conoció los trabajos de Church y Kleene, demostró que los