Máquinas de Turing
¿Qué es una máquina de Turing?
Una máquina de Turing es una máquina hipotética destinada a simular cualquier algoritmo informático, sin importar la complejidad. La máquina, como la pensó el matemático Alan Turing en 1936, es un marco relativamente simple que consiste en una cinta infinitamente larga que actúa como la memoria de la computadora. La cinta, que inicialmente comienza en blanco, puede tener impreso un 1 o un 0. Como las variables para imprimir están limitadas a 1, 0 y en blanco, la máquina de Turing se conoce como una máquina de tres símbolos.
¿Cómo funciona una máquina de Turing?
Una máquina de Turing tiene tres operaciones básicas cuando el cabezal de la máquina se coloca sobre la cinta. La máquina puede leer el símbolo en el cuadrado, editar el símbolo en el cuadrado a un nuevo valor o mover la cinta hacia la izquierda o hacia la derecha para leer o editar el cuadrado adyacente. Además, a cada valor se le puede asignar una acción asociada. Por ejemplo, si el símbolo que se lee es un 1, entonces la máquina escribirá 0 y moverá la cinta hacia la derecha, sin embargo, si el símbolo que se lee es un 0, escribirá un 1. Este proceso se llama inversión, ya que invierte los valores binarios.
Estado de la máquina
Una máquina de Turing continuaría procesando valores binarios sin cesar a menos que tenga un punto definido de finalización. El programa que le dice a la máquina cuándo detenerse se llama estado de la máquina. Por ejemplo, de manera similar en que cada símbolo se traduce en una acción, un estado agrupa un conjunto de definiciones para cada símbolo binario. Cuando un 0 y un 1 tienen instrucciones definidas dentro del estado inicial, un estado secundario puede tener instrucciones alternativas. Cuando se lee cada símbolo, la máquina ejecuta la instrucción de escritura, la instrucción de movimiento, y luego pasa al siguiente estado (que puede tener o no instrucciones similares para cada símbolo).
Tabla de instrucciones
Un programa para una máquina de Turing es simplemente un conjunto de instrucciones para leer los símbolos binarios en la cinta. Estas instrucciones se definen en lo que se denomina tabla de instrucciones o tabla de estado. Cada instrucción en la mesa le dice a la máquina qué escribir, en qué dirección mover la cinta y en qué estado debe moverse a continuación. En consecuencia, una instrucción puede indicar que la máquina debe detenerse y completar el programa.
Fuente: https://deepai.org/machine-learning-glossary-and-terms/turing-machine
