Máquinas de Turing

La máquina de Turing es un dispositivo abstracto con un control finito y una cinta ilimitada que captura la noción intuitiva de un algoritmo, y sirve como modelo de referencia estándar para lo que es computable.

Definition

Una máquina de Turing consta de un conjunto finito de estados y una cinta bidireccional infinita de celdas; en cada paso lee el símbolo bajo su cabezal, escribe un símbolo, se mueve a la izquierda o a la derecha, y cambia de estado según una función de transición, deteniéndose cuando entra en un estado de aceptación o rechazo.

Scope

Este tema abarca la definición y el funcionamiento de las máquinas de Turing, las configuraciones y los cálculos, la robustez del modelo bajo variantes como múltiples cintas y no determinismo, la máquina de Turing universal que puede simular cualquier otra, y la codificación de máquinas como datos que hace posible la autorreferencia y los argumentos de indecidibilidad.

Core questions

• ¿Cómo un simple dispositivo de lectura-escritura-movimiento captura la noción completa de algoritmo?
• ¿Por qué muchas variantes del modelo calculan exactamente las mismas funciones?
• ¿Qué es una máquina universal y por qué es significativa su existencia?
• ¿Cómo la codificación de máquinas como cadenas permite pruebas sobre su propio comportamiento?

Key theories

Universalidad

Existe una única máquina de Turing universal que, dada una codificación de cualquier máquina y su entrada, simula el cálculo de esa máquina, prefigurando la computadora de programa almacenado en la que los programas son datos en sí mismos.

Robustez del modelo

La adición de cintas, múltiples cabezales, cintas bidimensionales o no determinismo no cambia la clase de funciones computables, por lo que la máquina de Turing captura una noción de computación que es insensible a tales detalles.

Clinical relevance

La máquina de Turing es el criterio con el que se mide el poder de los lenguajes de programación y las arquitecturas de computadoras, y la máquina universal es el ancestro conceptual de la computadora de programa almacenado de propósito general en la que se basa toda la computación moderna.

History

Turing introdujo sus máquinas en 1936 para precisar lo que significa que un número sea computable y para resolver el problema de decisión de Hilbert. La idea de una máquina universal, en la que una descripción almacenada controla un dispositivo general, influyó en el diseño de von Neumann de la computadora de programa almacenado una década después.

Key figures

• Alan Turing
• Emil Post
• John von Neumann

Seminal works

• turing1937
• sipser2013

Frequently asked questions

¿Es una máquina de Turing una computadora real?

No, es una abstracción matemática con cinta ilimitada y sin preocupación por la velocidad o el costo de la memoria. Su valor es conceptual: precisa exactamente lo que se puede computar en principio, y cualquier tarea que una computadora real pueda realizar, una máquina de Turing también puede realizarla si se le da suficiente cinta y tiempo.

¿Por qué es importante la máquina de Turing universal?

Demuestra que una máquina fija puede llevar a cabo el comportamiento de cualquier otra cuando se le da la descripción de esa máquina como entrada. Esta es la base teórica de la computadora programable de propósito general, donde el software son datos alimentados a un único dispositivo interpretador en lugar de recablear para cada tarea.