Sitio Web de Héctor E. Medellín Anaya

Simulador de Máquina de Turing

Una máquina de Turing es un dispositio que consta de una cinta infinita utilizada como memoria. La cinta está dividida en celdas, cada celda puede contener un símbolo del alfabeto. El alfabeto consta de cualquier letra, número o caracter especial como !, ", $, etc. Se utiliza el carácter # para representar el espacio en blanco.

Ademas de la cinta la máquina de Turing posee una cabeza lectora-escritora que puede leer y escribir un símbolo en la cinta. La cabeza se mueve a cada paso una celda sobre la cinta hacia la derecha o hacia la izquierda. Las acciones de la cabeza son definidas por el estado en que se encuentra la máquina y el símbolo que se encuentra bajo de ella.

La máquina de Turing puede llevar a cabo cualquier cómputo que pueda realizar una computadora real. La operación de la máquina consiste en leer el símbolo de la cinta, con base en este símbolo y el estado en que se encuentra, se escribirá el mismo símbolo u otro, la cabeza se movera hacia la derecha o izquierda e irá al mismo u otro estado. Un estado especial H, llamado estadio de paro, se utiliza para detener el accionar de la máquina.

Los estados se especifican mediante una tabla de transiciones. Cada renglón de la tabla tiene dos entradas: el estado actual y el símbolo bajo la cabeza y tiene tres salidas: el símbolo que se escribirá en la cinta, la dirección del movimiento de la cabeza y el estado que sigue a continuación.

El siguiente es un ejemplo de una tabla de transiciones.

La tabla de transiciones anterior especifica una máquina que complementa un número binario. La cabeza deberá posicionarse en el primer símbolo de la izquierda del número binario.

El siguiente applet es un simulador de una máquina de Turing. Tiene controles para definir el quinteto de un estado y agregarlo a la tabla de transiciones. Si el estado actual y el símbolo de entrada coincide con algún frenglón de la tabla, se se modifican los otros tres elementos de ese renglón. El botón "Correr" inicia la ejecución de la máquina. El botón "Paso" ejecuta una sola transición. El botón "Borrar Cinta" borra el contenido de la cinta. El botón "Borrar trans." borra la transición seleccionada, para seleccionar una transición haga clic sobre el renglón correspondiente. El botón "Cargar" permite escribir o pegar un archivo de texto con la descripción de una máquina, la máquina actual se borrará. El botón salvar habre una ventana con una área de text con la descripción en texo de la máquina de Turing actual. Para modificar el contenido de la cinta, haga clic sobre la celda que desea modificar y haga clic sobre el carácter que desea insertar. Haga clic sobre el área color azul para posicionar la cabeza sobre algún símbolo en particular. Los triángulos de los extremos del área verde permiten des plazar la cinta a la derecha o izquierda. La cabeza muestra el número de estado actual de la máquina.

Características

Número de estados: 50 (0-49)

Número de transiciones: 1000

Tamaño de la cinta: 10000 caracteres

Símbolos del alfabeto: a-z, 0-9, ! " $ % & / ( ) = ? ¿ + - * [ ] , . ; : > < #(blanco)