Page 174 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

ro que sería indispensable sería un lenguaje formal claro y preciso, por lo que mucho de su trabajo
posterior se dirigió hacia ese objetivo. En 1928, David Hilbert y Wilhelm Ackermann propusieron la
pregunta en su formulación anteriormente mencionada.

Una fórmula lógica de primer orden es llamada universalmente válida o lógicamente válida si se de-
duce de los axiomas del cálculo de primer orden. El teorema de completitud de Gödel establece que
una fórmula lógica es universalmente válida en este sentido si y solo si es cierta en toda interpreta-
ción de la fórmula en un modelo.

Antes de poder responder a esta pregunta, hubo que definir formalmente la noción de algoritmo.
Esto fue realizado por Alonzo Church en 1936 con el concepto de calculabilidad efectiva, basado
en su cálculo lambda, y por Alan Turing, basándose en la máquina de Turing. Los dos enfoques son
equivalentes, en el sentido de que con ellos se pueden resolver exactamente los mismos problemas.
La respuesta negativa al Entscheidungsproblem fue dada por Alonzo Church en 1936 e indepen-
dientemente después (ese mismo año) por Alan Turing. Church demostró que no existe algoritmo
(definido según las funciones recursivas) que decida para dos expresiones del cálculo lambda si son
equivalentes o no. Church para esto se basó en el trabajo previo de Stephen Kleene. Por otra parte,
Turing redujo este problema al problema de la parada para las máquinas de Turing. Generalmente se
considera que la prueba de Turing ha tenido más influencia que la de Church. Ambos trabajos se vie-
ron influidos por trabajos anteriores de Kurt Gödel sobre el teorema de incompletitud, especialmente
por el método de asignar números a las fórmulas lógicas para poder reducir la lógica a la aritmética.

El argumento de Turing es como sigue: supóngase que se tiene un algoritmo general de decisión
para la lógica de primer orden. Se puede traducir la pregunta sobre si una máquina de Turing termina
con una fórmula de primer orden, que entonces podría ser sometida al algoritmo de decisión. Pero
Turing ya había demostrado que no existe algoritmo general que pueda decidir si una máquina de
Turing se para.

Es importante notar que si se restringe el problema a una teoría de primer orden específico con predi-
cados, constantes y axiomas, es posible que exista un algoritmo de decisión para la teoría. Algunos
ejemplos de teorías decidibles son la aritmética de Presburger y los sistemas estáticos de tipos de
los lenguajes de programación.

Sin embargo, la teoría general de primer orden para los números naturales, conocida como la arit-
mética de Peano, no puede ser decidida con ese tipo de algoritmo. Esto se deduce del argumento
de Turing resumido más arriba.

Además, el teorema de Gödel mostró que no existe algoritmo cuya entrada pueda ser cualquier
proposición acerca de los enteros y cuya salida es o no verdadera. Siguiendo de cerca a Gödel,
otros matemáticos —como Alonzo Church, Sephen Kleene, Emil Post y Alan Turing— 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 se pueden resolver por medio de computadoras es que
se obtuvieron en la década de 1930: ¡antes de que se hubiera construido la primera computadora!

168