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.