Definición: ¿Qué significa la máquina de Turing?
Una máquina de Turing es una máquina teórica que manipula símbolos en una tira de cinta, basándose en una tabla de reglas. Aunque la máquina de Turing es simple, se puede adaptar para replicar la lógica asociada con cualquier algoritmo informático. También es particularmente útil para describir las funciones de la CPU dentro de una computadora.
Alan Turing inventó la máquina de Turing en 1936 y se refirió a ella como "una máquina" o máquina automática.
Techinfo explica la máquina de Turing
La máquina de Turing no está destinada a ser una tecnología informática funcional; en cambio, está pensado como una máquina hipotética que representa una máquina de computación. La máquina de Turing puede ayudar a los científicos informáticos a comprender los límites de la computación mecánica.
Las máquinas de Turing modelan matemáticamente un dispositivo que funciona mecánicamente mediante una cinta. Esta cinta incluye símbolos que la máquina puede escribir y leer, uno tras otro, con la ayuda de un cabezal de cinta.
Más específicamente, una máquina de Turing incluye lo siguiente:
- Cinta: una cinta que se divide en celdas, una al lado de la otra. Cada celda incluye un símbolo de un determinado alfabeto finito. El alfabeto incluye un símbolo en blanco único, así como uno o más símbolos más. El volumen de cinta necesario para el cálculo siempre se incluye en la máquina de Turing.
- Cabeza: una cabeza que puede escribir y leer símbolos en la cinta. En ciertos modelos, la cabeza se mueve mientras la cinta está fija.
- Registro estatal: un registro estatal para almacenar el estado de la máquina de Turing. Existe un estado de inicio especial a través del cual se inicializa el registro de estado.
- Tabla finita: una tabla finita (a veces denominada función de transición o tabla de acciones) de instrucciones, que generalmente son quintuples, pero ocasionalmente se cuadriplican.