Читать книгу Computación y programación funcional - Camilo Chacón Sartori - Страница 15

Producto de la equivalencia entre los dos modelos, el cálculo lambda y la máquina de Turing, aparece el concepto de la tesis de Church-Turing, que reza lo siguiente:

Cualquiera que sea la función computable (algoritmo), esta es equivalente a una máquina de Turing.

Es decir, para que una función sea computable debe ser sí o sí computable por una máquina de Turing. En la actualidad, esto se sigue cumpliendo, y es difícil adherirse a la idea de que la tesis sea falsa, aunque es formalmente indemostrable. Esto radica en la incapacidad actual de definir qué es un «método efectivo» o «algoritmo», ya que no son conceptos fácilmente definibles. Simplemente se asume que cualquier algoritmo es una máquina de Turing.

Sobre esto, B. A. Trakhtenbrot, en su artículo: «Algorithms» de 1960, dijo lo siguiente sobre la incapacidad de demostrar esta tesis o hipótesis:

¿Cuál es la base de esta importante hipótesis? No podemos comprobarla como lo hacemos con un teorema matemático, puesto que es una declaración sobre el concepto general de algoritmo, que no está definido de manera precisa y no es, por tanto, un objeto propio de la discusión matemática. (Trakhtenbrot, 1960)

Sin embargo, en las últimas décadas se han añadido más datos que la han confirmado, por ejemplo, la equivalencia con otros modelos de computación (por ejemplo, lenguajes de programación), los cuales se suelen llamar «Turing completo».