Tesis de Church-Turing

En teoría de la computabilidad, la tesis de Church-Turing formula hipotéticamente la equivalencia entre los conceptos de función computable y máquina de Turing, que expresado en lenguaje corriente vendría a ser "todo algoritmo es equivalente a una máquina de Turing". No es un teorema matemático, es una afirmación formalmente indemostrable que, no obstante, tiene una aceptación prácticamente universal.

Introducción

En la década de 1930, uno de los problemas más estudiados por los matemáticos era el Entscheidungsproblem propuesto por David Hilbert: dada una proposición en un sistema formal, ¿existe un algoritmo tal que pueda decidir si la proposición es cierta (y por tanto es un teorema del sistema) o por el contrario es falsa? En 1936 Alonzo Church y Alan Turing probaron, de forma independiente, la imposibilidad de la existencia de tal algoritmo, usando el cálculo lambda en el caso de Church y la máquina de Turing en el caso de Turing. Posteriormente el concepto inicial de dicha "máquina" (que no tiene existencia física, realmente es una descripción formal) fue ampliada de diversos modos:

• 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,
• máquinas de Turing probabilistas,
• máquinas de Turing no deterministas.

Los lenguajes formales que son aceptados por una máquina de Turing son todos aquellos que pueden ser generados por una gramática formal. Por otro lado, las funciones que pueden ser computadas con el cálculo Lambda de Church son exactamente aquellas que pueden ser computadas con una máquina de Turing. Estos tres formalismos, las máquinas de Turing, los lenguajes formales y el cálculo Lambda han sido desarrollados de forma independiente y sin embargo se ha probado que son equivalentes; esta notable coincidencia parece indicar que la tesis de Church-Turing es cierta, siendo la noción de algoritmo o procedimiento efectivo de cómputo equivalente a la noción de cómputo en una máquina de Turing.

Entre los lenguajes formales que son aceptados por una máquina de Turing se pueden citar:

• autómatas finitos con dos pilas;
• autómatas finitos con dos contadores;
• la gramática formal;
• el sistema Post;
• el cálculo Lambda;
• funciones recursivas parciales;
• autómatas celulares: como 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;
• computadoras cuánticas.

Donde 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 ya que no se poseen los medios necesarios, 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.

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

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.

Detractores

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 computable en el sentido de Turing (i.e. Turing-computable).

Aunque exponer un algoritmo que no sea Turing-computable no es tan fácil, pero, es más "fácil" que probar la verdad de la tesis, ya que parece imposible negar que sea verdadera a pesar de que eso es una posibilidad lógica.

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.

Implicaciones

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.

Una posible interpretación válida 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. 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), usando como entrada los resultados de dicha súper computadora:

El universo o la naturaleza.

Véase también

• Máquina de Turing
• Tiempo polinómico
• Complejidad computacional

Bibliografía

• 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. Ámsterdam: 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.

Enlaces externos

• Stanford Encyclopedia of Philosophy (en inglés)

• Datos: Q309157
• Multimedia: Turing machines / Q309157