máquina de Turing
Una máquina de Turing es un modelo matemático de computación que define 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, dado cualquier algoritmo informático , se puede construir una máquina de Turing capaz de implementar la lógica de ese algoritmo. [3]
La máquina opera en una cinta de memoria infinita [4] dividida en "celdas" discretas . [5] La máquina coloca su "cabeza" sobre una celda y "lee" o "escanea" [6] el símbolo allí. Luego, según el símbolo y el estado actual de la máquina en una "tabla finita" [7] de instrucciones especificadas por el usuario, la máquina primero escribe un símbolo (por ejemplo, un dígito o una letra de un alfabeto finito) en la celda ( algunos modelos permiten borrar símbolos o no escribir), [8] luego mueve la cinta una celda hacia la izquierda o hacia la derecha (algunos modelos no permiten movimiento, algunos modelos mueven la cabeza), [9]luego, según el símbolo observado y el propio estado de la máquina en la tabla, continúa con otra instrucción o detiene el cálculo. [10]
La máquina de Turing fue inventada en 1936 por Alan Turing , [11] [12] quien la llamó "a-machine" (máquina automática). [13] 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. [14] 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 probar las propiedades de la computación en general y, en particular, la incomputabilidad del Entscheidungsproblem ("problema de decisión"). [17]
Las máquinas de Turing demostraron la existencia de limitaciones fundamentales en el poder de la computación mecánica. [18] 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.
