Tesis de Church-Turing

Todo algoritmo o procedimiento efectivo es Turing-computable.

La tesis

Existen muchas versiones similares (no necesariamente equivalentes) de la tesis de Church-Turing.

En general, en este texto nos referiremos a esta tesis como la tesis de Church-Turing o la tesis de Church, indistintamente.

Aunque originalmente la tesis que Alonzo Church formulara dice:

Tesis de Church: "(Church-Turing) A function of positive integers is effectively calculable only if recursive."

Cuya traducción sería: Una función de enteros positivos es efectivamente calculable sólo si es recursiva.

Y debido a que hay una variedad de formulaciones de la tesis de Church-Turing, usaremos, en general, una formulación simple y aceptada como dicha tesis, que se obtiene a partir de las revisiones conjuntas entre Alonzo Church y Alan M. Turing de sus respectivos trabajos:

Versión de la Tesis de Church-Turing más utilizada: Todo algoritmo o procedimiento efectivo es Turing-computable.

Otra versión simplificada de la anterior es: Todo lo que es computable es Turing-computable.'''

Aunque el problema queda trasladado de "algoritmo" o "procedimiento efectivo" a "computable".

Definición: Es Turing-computable aquello computable por una máquina de Turing.

La discusión acerca de las distintas verisones de la Tesis de Church-Turing, así como de las formulaciones originales se puede consultar en http://plato.stanford.edu/entries/church-turing/.

El propósito de la tesis

La versión de la tesis más usada establece que las máquinas de Turing realmente capturan la noción de lo que es un algoritmo o un procedimiento efectivo llevado a cabo por un humano o por una máquina.

Origen de la tesis

Modelos equivalentes a la máquina de Turing MT son: máquinas de Turing con una cinta infinita hacia una dirección, máquinas de Turing con una cinta infinita hacia ambas direcciones, máquinas de Turing con múltiples cintas, máquinas de Turing con múltiples pilas, máquinas de enumeración, entre otras.

Ejemplos de que la tesis de Church-Turing parece verdadera son muchos, desde el hecho de que todo algoritmo es computable hasta el hecho de que incluso modelos teóricos que parecen mucho más poderosos (y lo son pero en otros sentidos de complejidad), como lo es la computación cuántica, son reducibles finalmente a máquinas de Turing. Tal y como se ha visto hasta ahora, los distintos intentos directos o indirectos de crear modelos distintos a una máquina de Turing, todos son equivalentes a máquinas de Turing (o de menor poder computacional).

Los lenguajes que son aceptados por una máquina de Turing son exactamente aquellos generados por todas las gramáticas formales. El cálculo Lambda, por ejemplo, es una forma de definir funciones. Las funciones que pueden ser computadas con el cálculo Lambda son exactamente las que pueden ser computadas con máquinas de Turing. Estos tres tipos, las máquinas de Turing, las gramáticas o lenguajes formales y el cálculo Lambda son muy distintos y fueron desarrollados de manera ajena uno del otro, sin embargo, son equivalentes pues tienen el mismo poder para resolver problemas. Esto generalmente se toma como evidencia a favor de la tesis de Church-Turing.

Las computadoras electrónicas o digitales comunes son también equivalentes o reducibles a máquinas de Turing, si tuvieran disponible un número ilimitado de memoria (o sea que por la memoria aún una máquina de Turing es rigurosamente más poderosa aunque en la práctica puede pensarse que a la computadora se le puede proveer indefinidamente de memoria).

De esto se deduce también que todo lo que se hace sobre las computadoras electrónicas actuales es equivalente (en el sentido descrito) a una máquina de Turing, por ejemplo, todos los lenguajes de programación, las técnicas de computación evolutiva: algoritmos genéticos, programación genética o estrategias evolutivas, e incluso las redes neuronales implementadas en computadoras digitales.

Otras máquinas equivalentes a una máquina de Turing incluyen: máquinas de Turing con más de una cinta, máquinas de Turing con cintas n-dimensionales, máquinas de Turing con un número limitado de estados y símbolos, autómatas finitos con dos pilas, autómatas finitos con dos contadores, gramática formal, sistema Post, cálculo Lambda, funciones recursivas parciales, autómatas celulares (el juego de la vida de Conway o el autómata celular con una dimensión, dos estados, tres celdas por vecino y la regla 110), máquinas de Turing probabilistas, máquinas de Turing no deterministas y computadoras cuánticas (los tres últimos ejemplos utilizan una Definición ligeramente distinta de aceptación de lenguaje pues aceptan una cadena si existe tan solo un cómputo que la acepta o la mayoría la acepta y entonces es equivalente a máquina de Turing).

¿Por qué es una tesis?

Aunque se asume como cierta, la tesis de Church-Turing no puede ser probada, por eso es una tesis. Ello debido a que “procedimiento efectivo” y “algoritmo” no son conceptos dentro de ninguna teoría matemática y no son definibles fácilmente. La evidencia de su verdad es abundante pero no definitiva. Precisamente la tesis de Church establece que la definición de algoritmo o procedimiento efectivo es una máquina de Turing.

Será de particular interés de este texto explorar modelos para los cuales esta tesis no es verdadera, con la intención de estudiar y analizar las implicaciones posibles en la lógica y la aritmética.

Se ha acordado que un procedimiento efectivo o algoritmo consiste en un número finito y preciso de pasos descrito en un número finito de símbolos que podría ser también ejecutado por un ser humano. En general, la ejecución de un algoritmo no requiere de mayor inteligencia que la necesaria para entender y seguir las instrucciones (incluso sólo seguir).

Ejemplos de métodos efectivos o algoritmos abundan, por ejemplo la suma, resta, multiplicación o división son algoritmos de operaciones aritméticas. El algoritmo de Euclides para obtener el máximo común divisor de dos números naturales es otro ejemplo. Sin embargo, nada de esto ha sido una definición formal pues no es claro qué significa “instrucción precisa” o cuál es el tipo de inteligencia necesaria para seguir las instrucciones. Por esta misma razón, la idea abstracta de una máquina que funciona como parámetro para decidir cuándo algo es un algoritmo o procedimiento efectivo es de gran valor, esto es una máquina de Turing.

Éxito de la tesis

De hecho, la tesis de Church-Turing ha sido tan exitosa que la mayoría la supone verdadera. Los términos derivados de ella, como método efectivo y computable son comúnmente utilizados, cuando en realidad computable se refiere a Turing-computable, en el salto entre uno y otro se encuentra la tesis de Church, y entre muchos otros conceptos y términos comúnmente utilizados en la teoría de la computabilidad o funciones recursivas.

La tesis de Church-Turing tiene además profundas implicaciones. Cuando la tesis es aplicada a la física tiene diversos significados: que el universo es una máquina de Turing y por lo tanto no es posible construir físicamente una máquina con mayor poder computacional o que compute funciones no recursivas (la capacidad de cómputo que puede contener el universo está acoplado al tipo de universo en el que vivimos). A esto se le ha llamado tesis de Church-Turing fuerte. Otra posible interpretación es que el universo no es una máquina de Turing, es decir, las leyes del universo no son computables pero esto no afecta la posibilidad de crear una máquina más poderosa que una máquina de Turing (universo desacoplado al poder computacional de los dispositivos que contiene). Otra posibilidad es que el universo sea una hipercomputadora y entonces sea posible la construcción de máquinas más poderosas que las máquinas de Turing usando como entrada los resultados de dicha súper computadora: el universo o la naturaleza. Para ello posiblemente bastaría con que el universo fuera continuo e hiciera uso de esa continuidad (otra pregunta es qué tan densa es su continuidad).

¿Es falsa la tesis de Church-Turing?

Recientemente se han propuesto modelos teóricos que pretenden refutar la tesis de Church, por ejemplo el de las ARNN, que ha sido el más serio. Sin embargo no muestran la efectividad necesaria, aún, para refutar con argumentos sólidos la tesis de Church. Es claro que es más "fácil" probar la falsedad de la tesis que la verdad de la misma. Basta con exponer un método efectivo o algoritmo que no sea Turing-computable. Esto no es tan fácil pero es más "fácil" que probar la verdad de la tesis, ya que parece imposible negar la posibilidad lógica de que sea falsa. Existe una tesis relativizada de Church-Turing que depende de los grados de Turing definidos por máquinas de Turing con oráculos. Los oráculos son medios formales que suponen que se le facilita cierta información a la máquina de Turing para resolver algún problema, esto define una jerarquía que se ha estudiado tanto en la teoría de la Computabilidad como en la Teoría de la Complejidad.

Bibliografía y Referencias

Stanford Encyclopedia of Philosophy
Turing, Alan, On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Series 2, 42 (1936), pp 230-265.
Church, A. 1932. A set of Postulates for the Foundation of Logic. Annals of Mathematics, second series, 33, 346-366.
- 1936a. An Unsolvable Problem of Elementary Number Theory. American Journal of Mathematics, 58, 345-363.
- 1936b. A Note on the Entscheidungsproblem. Journal of Symbolic Logic, 1, 40-41.
- 1937a. Review of Turing 1936. Journal of Symbolic Logic, 2, 42-43.
- 1937b. Review of Post 1936. Journal of Symbolic Logic, 2, 43.
- 1941. The Calculi of Lambda-Conversion. Princeton: Princeton University Press.

Kleene, S.C. 1935. A Theory of Positive Integers in Formal Logic, American Journal of Mathematics, 57, 153-173, 219-244.
- 1936. Lambda-Definability and Recursiveness. Duke Mathematical Journal, 2, 340-353.
- 1952. Introduction to Metamathematics. Amsterdam: North-Holland.
- 1967. Mathematical Logic. New York: Wiley.

Gödel, K., 1934, On Undecidable Propositions of Formal Mathematical Systems, lecture notes taken by Kleene and Rosser at the Institute for Advanced Study, reprinted in Davis, M. (ed.) 1965, The Undecidable, New York: Raven.

Gourt Home::Gourt :: Tesis de Church-Turing