INTRODUCCIÓN

En las Unidades precedentes se han estudiado lo que se puede considerar las máquinas abstractas que permiten solucionar ciertos tipos de algoritmos, los algoritmos en los que no puede recordarse más que una cantidad fija de información y otros en los que la información desarrollada durante la ejecución del algoritmo puede recuperarse solo en concordancia con la regla “lifo” últimos en entrar primeros en salir, en esta unidad se describe una maquina abstracta, llamada Máquina de Turing , que es aceptada de manera amplia como modelo general de computación, aunque las operaciones básicas de esta máquina son comparables en su sencillez a las de las máquinas estudiadas en las unidades anteriores, las nuevas maquinas pueden realizar una amplia variedad de operaciones de cómputo.

Además de aceptar lenguajes les es posible computar funciones y de conformidad con la tesis de Church-Turing, ejecutar casi cualquier procedimiento algorítmico concebible.

¿Por qué creemos que las máquinas de Turing son una buena formalización del concepto de algoritmo?

• Porque cada programa de una máquina de Turing puede ser implementado.
• Porque todos los algoritmos conocidos han podido ser implementados en máquinas de Turing.
• Porque todos los otros intentos por formalizar este concepto fueron reducidos a las máquinas de Turing.
• Los mejores intentos resultaron ser equivalentes a las máquinas de Turing.
• Todos los intentos “razonables” fueron reducidos eficientemente.
• Tesis de Church: Algoritmo = Máquina de Turing.