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

...