máquina de Turing
Una máquina de Turing es un modelo matemático de computación que describe una máquina abstracta [1] que manipula símbolos en una tira de cinta de acuerdo con una tabla de reglas. [2] A pesar de la simplicidad del modelo, es capaz de implementar cualquier algoritmo informático . [3]
La máquina opera en una cinta de memoria infinita [4] dividida en celdas discretas , [5] cada una de las cuales puede contener un solo símbolo extraído de un conjunto finito de símbolos llamado el alfabeto de la máquina. Tiene una "cabeza" que, en cualquier punto de la operación de la máquina, se coloca sobre una de estas celdas y un "estado" seleccionado de un conjunto finito de estados. En cada paso de su operación, la cabeza lee el símbolo en su celda. Luego, según el símbolo y el estado actual de la máquina, la máquina escribe un símbolo en la misma celda y mueve la cabeza un paso hacia la izquierda o hacia la derecha, [6]o detiene el cálculo. La elección de qué símbolo de reemplazo escribir y en qué dirección moverse se basa en una tabla finita que especifica qué hacer para cada combinación del estado actual y el símbolo que se lee.
La máquina de Turing fue inventada en 1936 por Alan Turing , [7] [8] quien la llamó "a-machine" (máquina automática). [9] Fue el asesor de doctorado de Turing, Alonzo Church , quien más tarde acuñó el término "máquina de Turing" en una reseña. [10] Con este modelo, Turing pudo responder negativamente a dos preguntas:
Por lo tanto, al proporcionar una descripción matemática de un dispositivo muy simple capaz de realizar cálculos arbitrarios, pudo demostrar las propiedades de la computación en general y, en particular, la incomputabilidad del Entscheidungsproblem ("problema de decisión"). [13]
Las máquinas de Turing demostraron la existencia de limitaciones fundamentales en el poder de la computación mecánica. [14] Si bien pueden expresar cálculos arbitrarios, su diseño minimalista los hace inadecuados para el cálculo en la práctica: las computadoras del mundo real se basan en diferentes diseños que, a diferencia de las máquinas de Turing, usan memoria de acceso aleatorio .
La completitud de Turing es la capacidad de un sistema de instrucciones para simular una máquina de Turing. Un lenguaje de programación que es Turing completo es teóricamente capaz de expresar todas las tareas que pueden realizar las computadoras; casi todos los lenguajes de programación son Turing completos si se ignoran las limitaciones de la memoria finita.
