La Tesis de Church-Turing es una formulación hipotética de la equivalencia entre los conceptos de función computable y máquina de Turing, que si se expresa en lenguaje corriente, sería “todo algoritmo es equivalente a una máquina de Turing”.
El concepto inicial de la máquina de Turing, misma que no existe físicamente, sino como descripción formal, se tienen los siguientes modos:
•Máquinas de Turing con más de una cinta
•Máquinas de Turing con contas 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 aceptados por una máquina de Turing son los que se pueden generar por una gramática formal.
Entre los lenguajes formales aceptados por una máquina de Turing existen:
•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
•Computadoras cuánticas
Los tres últimos ejemplos funcionan con una definición un poco distinta de aceptación de lenguaje, ya que aceptan una cadena si existe un solo cómputo que la acepta o la mayoría la acepta, entonces es equivalente a la máquina de Turing.
Aunque se asume como cierta, la tesis de Church-Turing no puede ser probada debido a que no se poseen los medios necesarios, por ello es una tesis. Debido a que “procedimiento efectivo” y “algoritmo” no son conceptos dentro de ninguna teoría matemática y no son definibles fácilmente.
Esta tesis ha ganado gran éxito porque la mayoría la considera como verdadera. Los términos que se derivan de ella como método efectivo y computable son comúnmente utilizados, en realidad, computable se refiere a Turing-Computable, en el salto entre uno y otro se encuentra la tesis de Church.
