El
problema de castor laborioso
Todos conocemos la
constancia que los castores son capaces de mantener a la hora de elaborar sus
famosas presas para así poder detener el flujo de la corriente y crear un
estanque de aguas tranquilas donde poder construir sus madrigueras.
Esta
idea de la consistencia del castor tuvo que ser la que llevo al matemático de
origen húngaro Tibor Radó (1895-1965) a bautizar como el juego del castor
laborioso o afanoso a cierto problema que planteo para una máquina de Turing.
|
 |
Planteamiento
del problema
Fue en mayo de 1962 cuando definió
que un “castor laborioso” es una máquina de Turing que cumple dos condiciones:
- Al poner al castor en funcionamiento sobre una cinta totalmente ocupada por ceros, esta termina deteniéndose.
- El número de unos que imprime no es inferior al que pueda imprimir cualquier máquina de Turing de igual número de estados que llegue a detenerse. Este número de unos se denomina como Σ(N).
La definición original del
Castor Laborioso es una máquina de Turing en formato de quíntupla con N+1 estados (N estados y
el estado final de parada). El alfabeto de la cinta tiene dos símbolos Γ Є{
blanco, 1 } y el alfabeto de entrada solo uno Π = { 1 }. La productividad de
una MT se representa como el numero de 1’s
que tiene el resultado, a partir de una cinta en blanco, cuando esta se
detiene. Las MT que no se detienen se les consideran con productividad de cero.
Σ(N) se define como la máxima productividad que se puede obtener a partir de
una máquina de Turing de N estados
¿Para
qué se usa un castor laborioso?
En 1936 Turing definió las máquina de Turing como un modelo
universal de cómputo en el que todas las funciones calculables imaginables
pueden ser calculadas por un ellas. Entonces, ¿cómo encontramos una función que no
sea calculable? Aquí es donde entra el castor laborioso ya que Tibor demostró
que si f:Nà N
es una función computable existe Σ(n)>f(n) para toda n suficientemente
grande, y por lo tanto Σ no es una función computable.
Soluciones
El problema que nos
encontramos al estudiar el castor laborioso es que este crece más deprisa que
cualquier función computable, es decir que no es computable. Por ejemplo se
conocen los valores para Σ(1)=1, Σ(2)=4, Σ(3)=6, Σ(4)=13. Pero a medida que el número
de estados aumenta el problema se va volviendo más complicado.
Castor Laborioso para
1 estado.
Castor Laborioso para 2 estados.
Castor Laborioso para 3 estados.
Castor Laborioso para 4 estados.
Las técnicas usadas actualmente para N>4 solo llevan a cabo una búsqueda parcial en el espacio de soluciones, buscando MT que establezcan un límite inferior mejor para el valor de Σ(N). Por ejemplo Marxen estableció Σ(5)>=4098. Otros estudios han conseguido establecer estos límites inferiores para un Σ(7)>=102 mediante algoritmos genéticos y escalada de la colina.
Como podemos observar se
trata de un problema no computable para N altos el cual sigue sin resolución
tras 52 años de su planteamiento y por lo que parece ser seguirá así tras
varios años más.
Martín Cambronero Honrubia
Martín Cambronero Honrubia
Bibliografía
No hay comentarios:
Publicar un comentario