Máquinas de Turing
Pulsa aquí para obtener el emulador de máquina de Turing
Actualmente existen gran cantidad de ordenadores, capaces de realizar sorprendentes funciones. Todos ellos, sin embargo, están basados en un simplísimo artilugio imaginario capaz de hacer cualquier operación matemática computable; esto es, que se pueda realizar de una forma totalmente mecánica. Son las máquinas de Turing.
Alan M. Turing
Biografía
Alan Mathison Turing nació en 1912, y muy pronto mostró una extraordinaria intuición científica.
Mientras su padre se hallaba en Madrás, trabajando para el Indian Civil Service, Turing ganó numerosos premios escolares, y más tarde una beca que le llevaría al King's College de Cambridge. Fue aquí cuando empezó a interesarse seriamente por los problemas de lógica matemática.
En 1931, el matemático checo Kurt Godel descubrió que había teoremas matemáticos que eran verdaderos aún cuando no se pudiesen probar. Ante esto, Alan Turing se puso a investigar aquellos que sí podían ser probados. Quería intentar demostrar la vieja idea de que las matemáticas no son un arte misterioso, sino una ciencia exacta regida por reglas lógicas.
Para hacerlo, ideó una máquina imaginaria capaz de realizar de manera totalmente mecánica los procesos que normalmente llevaría a cabo un matemático. Había una máquina para cada proceso; así, había una máquina que sumaba, otra que multiplicaba, etc. Estas máquinas acabarían por recibir el nombre de "Máquinas de Turing". Básicamente, lo que quería era hacer una lista de los problemas que una máquina sería capaz de resolver siguiendo reglas lógicas. Si esta lista abarcaba todos los problemas matemáticos, entonces su tesis quedaría demostrada, y con ella la teoría de la computabilidad.
Tras estudiar con detenimiento el funcionamiento de sus máquinas, concluyó que era posible diseñar un artilugio único capaz de cumplir las funciones de cualquier otra máquina de Turing. A ésta se le llamó la "Máquina Universal de Turing".
Al estallar la Segunda Guerra Mundial, Turing fue alejado del mundo académico y reclutado por la Escuela de Códigos y Cifrados del gobierno británico. Las actividades que realizaba consistían de manera primordial en descifrar el código militar alemán ENIGMA. Para ello desarrolló el invento más secreto de dicha guerra: el Colossus, primer ordenador electromecánico del mundo. Más adelante, sería destinado a los Estados Unidos con el fin de crear unos códigos seguros para las comunicaciones transatlánticas entre los países aliados.
Acabada la guerra, Turing colaboró en la construcción del ENIAC. Posteriormente recibió el encargo de empezar a trabajar en la construcción de un ordenador totalmente británico, destinado al National Physical Laboratory, y que recibiría el nombre de ACE (Automatic Computing Engine).
Esta máquina tardó mucho tiempo en ser construida, pero era superior a ENIAC en muchas características. Frustrado por el lento avance, dimitió y se fue a vivir a Manchester, colaborando en el proyecto del MARK I, el ordenador de la universidad. Al mismo tiempo, era asesor de la compañía Ferranti y, por tanto, colaboró en la construcción de los primeros ordenadores fabricados en Gran Bretaña.
En 1952, Turing fue acusado de homosexualidad, y dos años más tarde se suicidó.
Uso del simulador
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 unos en 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
- ESPACIO retorna 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 cuenta lo 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 en cinco. 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 un sentido, 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) colocadas en 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 viene definido 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 pasa la máquina, que debe ser un número del 0 al 99, o bien el símbolo de la arroba ( @ ), que indicará estado de detención. Por último, nos preguntará el sentido en que debe moverse la cabeza, a lo que responderemos < , para indicar izquierda, o bien > , para indicar derecha. Si el nuevo estado es el de detención ( @ ), el ordenador añadirá automáticamente el símbolo < (no tiene razón de ser el querer meter un sentido, pues en estado de detención el programa para la ejecución con un mensaje y vuelve al menú principal).
Cuando se ha cambiado un bloque, el cursor pasa automáticamente al bloque de la derecha, siguiente en orden creciente de estado. Si estamos en un bloque del borde, pasará al primero de la línea siguiente. Esto permite programar la máquina con más comodidad, al no tener que desplazar el cursor hasta el siguiente bloque.
Para volver al menú principal, se debe pulsar ESPACIO.
EJECUCION NORMAL: Pone en marcha la máquina sobre la cinta, tomando como posición inicial la que tenía el cursor al salir de la opción ACTUALIZAR LA CINTA. Si no se había escogido aún dicha opción, se pondrá en marcha en la parte central.
La ejecución terminará en cualquiera de los siguientes casos:
- La máquina llega al estado de detención (o estado @). Imprime el mensaje "LA MAQUINA SE HA DETENIDO".
- La máquina se sale de la cinta por cualquiera de los dos lados. Imprime el mensaje "LA MAQUINA SE HA ESCAPADO".
- Se llega al número límite de ciclos de ejecución. Este límite es seleccionable en el apartado OPCIONES del menú.
- Se pulse la tecla ENTER.
EJECUCION PASO A PASO: Realiza la ejecución paso a paso, esperando a que se pulse una tecla antes de calcular el siguiente ciclo. Muestra, además, el estado actual de la máquina y el número de ciclo. Es una opción muy útil para depurar programas. La ejecución terminará en los mismos casos que la ejecución normal, volviendo al menú principal.
OPCIONES: Permite seleccionar el número máximo de ciclos que puede ejecutarse el programa actual. Si excede de siete cifras, el programa avisará con un mensaje, pidiendo que lo teclee de nuevo.
También permite seleccionar el estado en el que la máquina empezará su ejecución. Por defecto, este estado es el cero, pero puede cambiarse a voluntad. Obviamente, no puede ser el estado de detención (@).
SALIR: Devuelve el control al BASIC.
¿Qué son y cómo funcionan?
Una máquina de Turing consiste, básicamente, en una cinta infinita, dividida en casillas. Sobre esta cinta hay un dispositivo capaz de desplazarse a lo largo de ella a razón de una casilla cada vez. Este dispositivo cuenta con un cabezal capaz de leer un símbolo escrito en la cinta, o de borrar el existente e imprimir uno nuevo en su lugar. Por último, contiene además un registro capaz de almacenar un estado cualquiera, el cual viene definido por un símbolo. Los símbolos que definen el estado del dispositivo no tienen por que coincidir con los símbolos que se pueden leer o escribir en la cinta. En los programas presentados en el artículo, los posibles símbolos a leer o escribir en la cinta son el 0 y el 1, y los posibles estados se representan con letras mayúsculas. En el emulador, existe un cambio en la representación del estado, usando para ello los números del 0 al 99, para permitir un mayor número de ellos.
La máquina tiene un funcionamiento totalmente mecánico y secuencial. Lo que hace es leer el símbolo que hay en la casilla que tiene debajo. Después toma el símbolo del estado en que se encuentra. Con estos dos datos accede a una tabla, en la cual lee el símbolo que debe escribir en la cinta, el nuevo estado al que debe pasar y si debe desplazarse a la casilla izquierda o derecha.
Para comprender mejor, vamos a ver un simple ejemplo: sea la máquina de Turing capaz de leer o escribir los símbolos 0 y 1 en la cinta (en la definición original de Turing, el número de símbolos a usar podía ser cualquiera, con la única condición de ser un número finito, y no tenían por qué ser números; sin embargo, en aplicaciones prácticas se suelen limitar a estos dos), y que puede tener los estados A, B y C (una máquina de Turing puede tener cualquier número de estados; la única condición es que sea un número finito). Supongamos que definimos la siguiente tabla:
estado símbolo nuevo nuevo sentido de inicial leído estado símbolo avance A 0 B 1 DERECHA A 1 B 0 IZQUIERDA B 0 A 1 DERECHA B 1 C 0 DERECHA C 0 A 0 IZQUIERDA C 1 C 0 DERECHA
La cual vamos a simplificar de la siguiente manera:
0 1
A B,1,> B,0,<
B A,1,> C,0,>
C A,0,< C,0,>
Hemos puesto los posibles estados en columna, y los posible símbolos en fila, y hemos expresado el nuevo estado, símbolo y sentido todo junto. El sentido lo expresamos con la dirección en la que apunta el símbolo < o >.
Vamos a poner nuestra máquina sobre esta cinta:
cabezal
v
... 0 0 0 0 0 1 0 0 0 0 ...
Indicaremos el estado actual de la máquina encima del cabezal. Veamos los sucesivos pasos de esta máquina si partimos del estado A:
1) A El estado es A y leemos un cero;
v luego debemos cambiar al estado B,
... 0 0 0 0 0 1 0 0 0 0 ... escribir un 1 y movernos a la derecha
2) B El estado es B y leemos un cero;
v luego debemos cambiar al estado A,
... 0 0 0 1 0 1 0 0 0 0 ... escribir un 1 y movernos a la derecha
3) A El estado es A y leemos un uno;
v luego debemos cambiar al estado B,
... 0 0 0 1 1 1 0 0 0 0 ... escribir un 0 y movernos a la izquierda
4) B El estado es B y leemos un uno;
v luego debemos cambiar al estado C,
... 0 0 0 1 1 0 0 0 0 0 ... escribir un 0 y movernos a la izquierda
5) C El estado es C y leemos un uno;
v luego debemos cambiar al estado C,
... 0 0 0 1 0 0 0 0 0 0 ... escribir un 0 y movernos a la derecha
6) C El estado es C y leemos un cero;
v luego debemos cambiar al estado A,
... 0 0 0 0 0 0 0 0 0 0 ... escribir un 0 y movernos a la izquierda
7) A El estado es A y leemos un cero;
v luego debemos cambiar al estado B,
... 0 0 0 0 0 0 0 0 0 0 ... escribir un 1 y movernos a la derecha
La ejecución de esta máquina seguiría indefinidamente, rellenando la cinta con unos y ceros de una manera más o menos aleatoria. Realmente, una máquina de Turing útil debería poder detenerse; esto es, tener un estado en el que se detiene. Dicho estado se alcanzaría igual que cualquier otro estado. Esto es, supongamos que el estado D es el de paro; lo único que debemos hacer es que, cuando la máquina halla terminado el cálculo, pase a estado D; de este modo se detiene y permite examinar la cinta para buscar el resultado.
Vemos que esta máquina no hace gran cosa. Sin embargo, una máquina de Turing puede hacer cosas útiles, tales como sumar dos números, multiplicarlos, copiarlos, etc. Disponiendo de una máquina con el suficiente número de estados, podríamos hacer con ella cualquier operación que un ordenador normal pudiese realizar.
Las máquinas de Turing plantean una deducción bastante curiosa: dado que en ellas se puede realizar cualquier trabajo computable, es posible programarlas para que simulen el comportamiento de un potente ordenador. Y como una máquina de Turing puede ser codificada en CUALQUIER ordenador, por pequeño que sea, sería posible (si disponemos de memoria suficiente, claro) emular en nuestro ordenador de casa una máquina de Turing que simule un superordenador. Esto significa que todos los ordenadores pueden realizar exactamente el mismo tipo de tareas, y que los cálculos que pueda realizar el más grande los puede llevar a cabo también el más pequeño. La única diferencia sería, obviamente, la velocidad.
Suma de dos números
Una de las tareas más simples que puede llevar a cabo una máquina de Turing es la suma de dos números. Para ello debemos definir primero una convención para representar dichos números en la cinta. En principio, podríamos pensar que, al usar los símbolos 0 y 1, podemos representar los números directamente en binario; sin embargo, la cantidad de operaciones necesarias para trabajar con ellos hace que el número de estados de la máquina sumadora crezca sorprendentemente, debido a que es un sistema de numeración posicional.
Para simplificar el proceso, vamos a representar cada número por una cadena con tantos unos como indique dicho número; así, para representar el tres, escribiríamos tres unos seguidos; para un cinco, cinco unos.
Veamos como podemos sumarlos. Si tenemos dos números en una cinta, separados uno de otro por un cero, la forma más fácil de sumarlos sería convertir uno de los unos de los extremos en cero, y cambiar el cero de separación por un uno. De este modo tendríamos una cadena formada por tantos unos como indica la suma de los dos números originales. Veámoslo con un ejemplo:
sumemos tres y cinco:
cinta inicial:
0000111011111000
ponemos un cero en el lugar del uno de la izquierda:
0000011011111000
ponemos un uno en el lugar del cero de separación:
0000011111111000
el resultado: ocho unos, el número ocho.
Para implementar esto, supondremos que la máquina se encuentra a la izquierda. Empezaremos en el estado A. El estado inicial no tiene por qué ser necesariamente el primero de la lista de estados, pero es costumbre que sea así. De todos modos, si no es el primero, una simple reordenación del programa resuelve el problema.
Dado que el cabezal no tiene por qué estar inmediatamente antes del primer número, sino que puede estar más alejada, debemos asegurarnos de que llega hasta él sin alterar nada. Lo que debemos hacer es que, mientras lea un cero y esté en estado A, escriba un cero (así no altera nada), vuelva a estado A, y se mueva una casilla a la derecha.
En cuanto llegue al primer número, se encontrará un uno que es preciso convertir a cero antes de seguir. Por tanto, si se encuentra en estado A y encuentra un uno, debe escribir un cero y moverse a la derecha para acercarse al cero de separación. Pero hay que tener en cuenta que, si permaneciese en estado A, como después del primer uno vienen más, los pondría todos a cero; por tanto, debemos añadir un nuevo estado: el B. En cuanto encuentre un uno en estado A, deberá pasar a este nuevo estado B.
Una vez que ha puesto ese uno a cero, debe desplazarse hasta llegar al cero de separación, pero sin alterar nada; luego, si estando en estado B encuentra un uno, debe poner un uno, moverse a la derecha, y pasar de nuevo a estado B. Pero en cuanto detecte un cero, significa que ha llegado a la separación, luego si estando en B encuentra un cero, debe ponerlo a uno.
Ahora que la suma está terminada, la máquina debe pararse, pasando al estado correspondiente. Le denominaremos @ (arroba), para distinguirlo de otros posibles estados. En cuanto lo alcanza, la máquina ya no leerá ningún símbolo más ni se desplazará.
Veamos el programa de esta máquina de sumar:
0 1
A 0,A,> 0,B,>
B 1,@ 1,B,>
Copia de una cadena de unos a continuación de ella misma
Puede ser útil para algunas aplicaciones obtener una copia de un número a continuación de él mismo, bien sea como parte del proceso, bien porque éste lo modifica y queremos mantener el original inalterado.
Una posibilidad para copiar una cadena de N unos es usar una máquina de N estados; sin embargo, esto hace aumentar su número de manera poco menos que incontrolable; por eso nos conviene hallar un sistema que no consuma tantos estados, y, sobre todo, que funcione para cualquier cadena, no solo para las de longitud N.
Una de las maneras más cómodas es usar un cero como contador. Esto es: colocamos un cero en lugar del primer uno de la cadena, nos desplazamos hasta el final de ella, colocamos un uno, y volvemos hasta donde esté el cero. Lo cambiamos a un uno, pasamos a la siguiente casilla, ponemos un cero y repetimos el proceso. De este modo, el cero se irá corriendo a lo largo de la cadena original, y cada vez que se desplace una posición, aparecerá un nuevo uno al final de la cadena copiada. La máquina se detendrá en cuanto intente poner un cero en el lugar que ocupe otro cero en vez de un uno, pues significará que ha llegado al cero de separación de la cadena original y la cadena copia.
Veamos un programa que cumple lo expuesto, comentado:
0 1
A 0,A,> Nos movemos hacia la derecha 0,B,> Ponemos un cero en el
hasta el principio de la cadena. primer uno de la cadena.
B 0,C,> Vamos a la derecha, a través de 1,B,> Vamos desde el marcador
la separación entre cadenas. hasta la separación.
C 1,D,< Ponemos un uno en el extremo 1,C,> Vamos hacia la derecha
de la cadena copia. de la cadena copia.
D 0,E,< Vamos hacia la izquierda desde 1,D,< Vamos hacia la izquierda
la separación. por la copia.
E 1,H,< El marcador está a la izquierda 1,F,< Vamos hacia la izquierda
de la separación. Fin de la copia. desde la separación.
F 1,G,> Iniciamos el cambio de lugar 1,F,< Seguimos hasta encontrar
del marcador. el marcador.
H ----- Nunca se da esta condición. No 0,B,> Terminamos el desplaza-
programar o poner un bloque miento del marcador y
ficticio. recomenzamos.
I 0,@ La cadena ya está copiada. 1,I,> Nos movemos hasta el
la máquina debe detenerse. inicio de la cadena original.
Producto de dos números
Vamos a aprovecharnos de la rutina de copia para hacer una rutina de multiplicación.
Si analizamos el producto de dos números, vemos que se trata simplemente de sumar el primero a sí mismo tantas veces como indica el segundo. Y como trabajando con nuestro particular sistema de numeración, la suma no es más que unir dos cadenas, vemos que esta es una tarea perfecta para nuestra rutina de copiado.
La manera de hacerlo es muy simple: debido a una casualidad totalmente intencionada :-) , si hay dos números seguidos (con el cero de separación entre ellos, claro) y mandamos a nuestra rutina que copie el primero (el de más a la izquierda, en nuestro caso), lo hará a continuación del segundo, pero sin separarlo; en otras palabras, habrá sumado al segundo una copia del primero. De este modo, si activamos la rutina de copia sobre el segundo número a multiplicar, tantas veces como indique el primero, lo que haremos será sumar el segundo número a sí mismo tantas veces como indique el primero. Los habremos multiplicado.
Para que la rutina de copia se active tantas veces como indica el primer número, haremos un contador con un cero, de la misma manera que hicimos en la propia rutina de copia. Así de fácil.
Veamos un programa de máquina de Turing que lo hace. Los estados de la A a la H son los mismos que los de la rutina de copia, para ahorrar espacio en el artículo. Esto significa que la máquina no se debe poner en marcha en el estado A, sino en el estado J.
0 1 0 1
I 0,L,< 1,I,< M 1,N,> 1,M,<
J 0,J,> 0,K,> N ----- 0,K,>
K 0,A,> 1,K,> O 0,@ 1,O,<
L 1,O,< 1,M,<
El bloque ----- significa que esa condición nunca puede darse, por lo que se debe dejar sin rellenar o bien poner un bloque ficticio.
La rutina borracintas
Un programa que, en principio, no pasa de ser una mera curiosidad, es el programa borracintas. Lo único que hace es colocar la cinta de una máquina de Turing a cero, eliminando todos los posibles unos que pudiese contener. Dado que el número de unos existentes no lo podemos conocer a priori, y dado que la cinta es infinita, ésta máquina, para que realmente sea eficiente, no podrá detenerse nunca. De todos modos, el número de unos no puede ser infinito, pues entonces nunca conseguiríamos borrar totalmente la cinta (por mucho tiempo que tuviésemos la máquina en funcionamiento, siempre quedarían unos sin borrar). Veamos como diseñarla.
Una posible opción sería hacer una máquina de un solo estado que, encuentre lo que encuentre, escriba un cero y pase a la casilla siguiente. Su listado sería:
0 1
A 0,A,> 0,A,>
Vemos, sin embargo, que esta máquina no es totalmente efectiva, pues sólo elimina los unos que se hallen a la derecha de la posición de origen. Podríamos diseñar una máquina borracintas que trabaje hacia la izquierda, y usar primero una y luego otra; pero como la cinta es infinita, nunca sabríamos cuando podemos parar, pues pueden quedar aún unos por eliminar. Por eso debemos diseñar otra máquina más versátil que ésta.
La segunda versión de la máquina borracintas usa dos estados. Se trata de una unión de las dos máquinas borracintas anteriores. Lo que hace es desplazarse en un sentido hasta que encuentra un uno. En cuanto llega a él lo cambia por un cero y se desplaza en el sentido contrario hasta encontrar otro uno, repitiendo el proceso. Su listado sería:
0 1 0 1
A 0,A,> 0,B,< B 0,B,< 0,A,>
Si bien esta máquina es notablemente superior, vemos que puede darse el caso de que haya más unos hacia el lado derecho de la posición inicial que hacia el lado izquierdo (no olvidemos que el número de unos es finito). Si se diese esta situación, en cuanto se acabasen los unos en uno de los lados, la máquina se escaparía por él, dejando los del otro lado sin borrar. Por fortuna, en esta vida todo tiene solución, y este problema no iba a ser menos.
Para conseguir eliminar todos los unos, podemos hacer que, cada vez que la máquina encuentre uno, lo ponga a cero, coloque un uno en la siguiente posición, e invierta su sentido. De este modo, los nuevos unos se comportarán como barreras. Cada vez que la máquina llega a una, la desplaza una posición e invierte su sentido. De este modo, la máquina siempre recorrerá por igual los dos sentidos.
Una precaución consiste en colocar al principio dos unos seguidos, pues puede ocurrir que en uno de los dos sentidos no haya unos, y la máquina se pierda. De este modo, al colocar esos dos unos, inicializamos las barreras. A cada vuelta, las barreras se irán ensanchando más. Cuando una barrera se pone encima de un uno, lo anula, de modo que al siguiente paso del cabezal quedará eliminado.
El programa puede ser el siguiente:
0 1 0 1
A 1,B,> 1,B,> D 1,E,> 1,E,>
B 1,C,< 1,C,< E 0,E,> 0,F,>
C 0,C,< 0,D,< F 1,C,< 1,C,<
Los estados A y B sirven para inicializar las dos barreras. El código del programa empieza en C, desplazándose hacia la izquierda hasta encontrar un uno, momento en que lo cambia por un cero y pasa al estado D, que pone un uno una posición más hacia la izquierda e inicia el desplazamiento hacia la derecha, pasando al estado E. En el, el cabezal se desplaza hacia la derecha hasta encontrar un uno, cambiándolo por un cero y pasando al estado F en la siguiente casilla. En este estado, se pone un uno y se comienza el desplazamiento hacia la izquierda, volviendo al estado C y cerrando el bucle.
Los castores afanosos
El problema del castor afanoso es uno de los más interesantes, trabajando con máquinas de Turing. Un castor afanoso es, simplemente, una máquina de Turing de N estados, la cual, una vez puesta en marcha sobre una cinta totalmente a cero, imprime más unos que cualquier otra máquina de Turing de N estados. Además de esto, debe cumplir la condición de detenerse tras haber impreso la serie de unos. No es indispensable que los unos estén seguidos en la cinta; puede haber ceros de separación entre ellos.
Tal vez alguien piense que es un problema trivial; sin embargo, es la base de la teoría de la computabilidad de una función. Precisamente, el máximo número de unos que puede imprimir una máquina de Turing de N estados es una función no computable; es decir, si queremos hacer un castor afanoso de N estados, no podemos saber, a priori, cual es el número de unos que imprimirá.
Se sabe el máximo de unos para las máquinas de 1,2,3 y 4 estados, que son 1, 4 , 6 y 13 unos, respectivamente. Para más estados, el número exacto no se puede determinar.
Vamos a ver los programas de algunos castores afanosos:
Castor afanoso de 1 estado:
0 1
A 1,@ 1,@
Castor afanoso de 2 Estados:
0 1
A 1,B,> 1,B,<
B 1,A,< 1,@
Castor afanoso de 3 estados:
0 1
A 1,B,> 1,C,<
B 1,A,< 1,B,>
C 1,B,< 1,@
El problema del castor afanoso de 5 estados:
Para intentar resolver el problema del castor afanoso de cinco estados, en 1982 se anunció un concurso. Para participar, había que presentar un castor afanoso pentaestado, y ganaría el que más unos fuese capaz de imprimir antes de detenerse.
El vencedor del concurso, celebrado en enero de 1983, fue la máquina presentada por Uwe Schult, la cual fue capaz de imprimir 501 unos en la cinta. Su programa es el siguiente:
0 1 0 1
A 1,B,> 0,C,< D 0,E,> 1,@
B 1,C,> 1,D,> E 1,C,< 1,A,>
C 1,A,< 0,B,>
Una vez puesta en marcha, parece seguir un curso cíclico, a medida que va aumentando el número de unos de la cinta. De hecho, parece que nunca se va a detener; sin embargo, como castorcito afanoso que es, se detiene una vez cumplida su misión: imprimir 501 unos.
Pero... como (casi) siempre ha ocurrido en la historia de la computación, ante una solución a un problema, siempre existe otra que es, o mejor, o más simple. Dos años después, el 21 de diciembre de 1984, George Uhing descubrió una máquina de Turing pentaestado capaz de imprimir 1915 unos antes de detenerse. Como es lógico, el programa de Uwe Schult quedó sin el título de castor, otorgándoselo al nuevo algoritmo. Me hubiera gustado poder incluir su listado, pero no he tenido manera de encontrarlo.
Y así sigue la cosa. Posiblemente algún día aparecerá una nueva máquina de Turing pentaestado capaz de imprimir un número mayor de unos, proclamándose nueva campeona.
¿Quien puede predecir cual será el límite de estos ingenios?
Esta obra está bajo una licencia de Creative Commons Reconocimiento-CompartirIgual 4.0 Internacional.