Page 12 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

12

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.

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. A la vista de estos
resultados, la Tesis de Church-Turing es aceptada como un axioma en la teoría de la computación
y ha servido como punto de partida en la investigación de los problemas que se pueden resolver
mediante un algoritmo.

Una de las cuestiones más estudiadas en la teoría de la computabilidad ha sido la posibilidad de
construir programas que decidan si un determinado algoritmo posee o no una determinada
propiedad. Por ejemplo, responder de forma automática a cuestiones como:

 ¿Calculan los algoritmos a y b la misma función?
(Problema de la equivalencia).

 ¿Parará el algoritmo a para una de sus entradas?
(Problema de la parada)

 ¿Parará el algoritmo a para todas sus entradas?
(Problema de la totalidad)

 ¿Calcula el algoritmo a la función f?
(Problema de la verificación)

Conforme se fueron obteniendo demostraciones individuales de la no computabilidad de cada una
de estas cuestiones, fue creciendo la sensación de que casi cualquier pregunta interesante acerca
de algoritmos era no computable. El teorema de rice, confirma esta sensación: “considérese
cualquier propiedad que no sea trivial acerca de la función calculada por un algoritmo,
entonces la cuestión de si la función calculada por un algoritmo arbitrario verifica dicha
propiedad es no computable”.