Castores Afanosos

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.

...