Maquina de Turing

Acompañando a este artículo va un simulador de máquina de Turing. Por razones de transportabilidad entre distintos modelos de ordenadores, está escrito integramente en BASIC, a pesar de lo cual mantiene una velocidad perfectamente adecuada. Para usarlo, es necesario usar el editor QBASIC de Microsoft o el compilador QUICKBASIC, de la misma casa.

Al arrancar el programa, la pantalla se llenaráde ceros, mientras en la parte inferior de la pantalla aparece el mensaje "IMPRIMIENDO CINTA". Esa línea es la zona de mensajes. Los ceros son la presentación de la cinta de la máquina en pantalla.

A continuación aparece un menú con las siguientes opciones:

LIMPIAR LA CINTA: Borra todos los unos impresos en la cinta, dejándola rellena de ceros.

ACTUALIZAR LA CINTA: Sirve para colocar unosen las zonas que nos interesen, para definir una situación inicial para la máquina. Los controles son los siguientes:

P mueve el cursor una posición a la derecha
O mueve el cursor una posición a la izquierda
Q mueve el cursor una posición hacia arriba
A mueve el cursor una posición hacia abajo
1 escribe un uno en la posición del cursor
0 escribe un cero en la posición del cursor
ESPACIOretorna al menú principal, y toma la posición actual del cursor como la posición en la que pondrá la máquina en marcha.
PROGRAMAR LA MAQUINA: Sirve para introducir la tabla de posibilidades para la máquina. Aparece ésta en pantalla, inicialmente toda a cero, y a los lados del primer grupo aparecen dos símbolos # en inverso. Son el cursor.

Para realizar la programación, hay que tener en cuentalo siguiente:

El emulador puede manejar hasta cien estados, nombrados con los números del cero (0) al noventa y nueve (99). Obviamente, un programa para el simulador no tiene por qué usarlos todos.
El estado de detención no se simboliza con un número, sino con el símbolo de la arroba (@ , código ASCII: 64). Es un estado específico, y es el que reconoce el emulador como estado de detención.Los únicos símbolos que puede imprimir en la cinta son el cero (0) y el uno (1).
El sentido de avance de la cinta se indica con los símbolos < (izquierda) y > (derecha).
En pantalla aparece la tabla que define la máquina actual, dispuesta de una manera especial: en la parte superior aparecen los números del cero al cuatro, y a la izquierda los números del cero al noventa y cinco, de cinco encinco. Esos números especifican el estado en que se debe encontrar la máquina para que ejecute la instrucción indicada.

En la parte superior, debajo de cada número, aparecen un cero y un uno. Son los símbolos que debe encontrar la máquina en la cinta para que ejecute la instrucción indicada. Por último, debajo de cada cero o uno aparecerá un bloque de instrucciones, compuesto por dos números y unsentido, representado por los signos < y >.

Veamos un ejemplo para que quede claro: la pantalla tendrá este aspecto:

0 1 2 3
0 1 0 1 1 0 1 0
0 A B C D
5 E F
10 G H
15
20
25
Las instrucciones (o el bloque) colocadasen la posición de la letra A se ejecutarán si la máquina está en estado cero y encuentra un cero en la cinta; las de la posición de la B, si la máquina está en estado cero y encuentra un uno; las de C, si está en estado 1 (1+0) y encuentra un cero; las de F si está en estado 5 (5+0) y encuentra un uno; las de G, si está en estado 12 (10+2) y encuentra un cero...

Vemos que el estado vienedefinido por la suma de las cifras de la izquierda y de la parte superior.

Para realizar una modificación, se debe situar el cursor (representado por dos signos # en fondo inverso, uno a cada lado) en el bloque a cambiar, y pulsar ENTER. El programa nos pedirá el nuevo símbolo a escribir en la cinta, a lo que debemos responder 1 o 0, seguido de ENTER; después nos preguntará el nuevo estado al que...