Tesis de church

Fue formulada por Alan Turing y Alonzo Church, de forma independiente a mediados del siglo XX, y a pesar de que existen múltiples formulaciones equivalentes, se utilizara 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:
Puesto que se puede probar matemáticamente que paracualquier programa de computadora es posible crear una máquina de Turing equivalente. Esta prueba resulta de la Tesis de Church-Turing, es decir:
• Todo lo que es computable (entendiéndose computable como "Lo que se puede tomar en cuenta o evaluar") es Turing-computable.
Eso implica que las máquinas de Turing realmente capturan la noción de lo que es un algoritmo o un procedimiento efectivollevado a cabo por un humano o por una máquina.

La tesis
Aunque originalmente la tesis que Alonzo Church formulara dice:
• Una función de enteros positivos es efectivamente calculable sólo si es recursiva.
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 escomputable es Turing-computable.

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-Turingparece 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 auna 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 sercomputadas 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 digitalescomunes son también equivalentes o reducibles a máquinas de Turing, si tuvieran disponible un número ilimitado de memoria (es decir, puede procesar una linea infinita de datos). 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 quetodo lo que se hace sobre las computadoras electrónicas actuales es equivalente (en el sentido descrito) a una máquina de Turing incompleta (ya que como se menciono, no tienen memoria infinita), 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 encomputadoras 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.
• La gramática formal
• El sistema Post
•...