Tesis De Church y Turing Pdf

Tesis de Church-Turing
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 probarmatemáticamente que para cualquier programa de computadora es posible crear una máquina de Turing equivalente. Esta prueba resulta de la Tesis de Church-Turing.
Eso implica 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.
Aunque no se puede dar ninguna prueba formal de que una máquina puedatener esa propiedad, Turing dió un elevado número de argumentos a su favor, en base a lo cual presentó la tesis como un teorema demostrado. Además, utilizó su concepto de máquina para demostrar que existen funciones que no son calculables por un método definido y en particular, que el Entscheidungsproblem era uno de esos problemas.
La tesis
Aunque originalmente la tesis que Alonzo Church formularadice:
• 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 es computable es Turing-computable.

La tesis de Church-Turing se refiere a la noción de un método efectivo o mecánica de lalógica y las matemáticas. "Eficaz" y "mecánico" El sinónimo de términos de arte en estas disciplinas: no llevar a su sentido cotidiano. Un método o procedimiento, M, para lograr algún resultado deseado se denomina "efectivo" o "mecánico" por si acaso
1. M se establece en términos de un número finito de instrucciones exactas (cada instrucción que se expresa por medio de un número finito de símbolos);2. M, si se lleva a cabo sin errores, el resultado deseado en un número finito de pasos;
3. M puede (en la práctica o en principio) se llevarán a cabo por un ser humano sin la ayuda de ninguna maquinaria ahorrar papel y lápiz;
4. M no exige conocimiento o el ingenio por parte del ser humano, llevarlo a cabo.
Descripción alternativa
Una máquina de Turing no determinista adivina el caminocorrecto y luego
comprueba que efectivamente es correcto.
Origen de la tesis
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áquinasde 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 dedefinir 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 resolverproblemas. 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 (es decir, puede procesar una línea infinita de datos). O sea que por la memoria aún una máquina de Turing es rigurosamente más poderosa aunque en la...