INTRODUCCIÓN
El problema del Castor Laborioso o The Busy Beaver Game es un juego fácil de entender pero difícil de jugar.
El juego fue propuesto por Tibor Radó y está pensado para máquinas de Turing.
No es un simple juego para entretenerse. Una solución general al problema implicaría un paso importante en el área de la computación.
Condiciones del juego:
Objetivo:
La parte variable del problema es el número de estados que podemos utilizar.
Definimos la función P: N => N donde el valor de entrada es el número de estados y el de salida el número de 1s máximo que puede generar la máquina de Turing con los estados dados.
El estado final está excluido por lo que para N = 1 la máquina de Turing tiene los estados q0 y qf pero qf no se utiliza ya que en el momento que la máquina de Turing llega a este estado se para.
No es un simple juego para entretenerse. Una solución general al problema implicaría un paso importante en el área de la computación.
Tibor Radó
Tibor Radó nació en Budapest y entre 1913 y 1915 asistió al Instituto Politécnico donde estudió ingeniería civil. En la primera guerra mundial él se convirtió en el primer lugarteniente de la armada húngara y fue capturado en el frente ruso. Escapó del campo de prisioneros de Siberia y, viajando miles de millas atravesando el Antártico, logró regresar a Hungaria.
Él consiguió un doctorado en la universidad Franz Joseph en 1923. Estuvo un pequeño tiempo como profesor en la universidad y apoyó en el campo de la investigación junto a la fundación Rockefeller en Alemania.
En 1929 se trasladó a los Estados Unidos y dio una conferencia en la universidad de Harvard y en el Instituto Rice antes de obtener un puesto en el departamento de matemáticas en la universidad estatal de Ohio en 1930.
En 1935 se le concedió la ciudadanía Americana. Durante la segunda guerra mundial fue un científico del gobierno de los Estados Unidos, interrumpiendo su carrera académica. Se convirtió en presidente del departamento de matemáticas de la universidad estatal de Ohio en 1948.
En la década de 1920 demostró que las superficies tenían una triangulación esencial única. En 1933 publicó "On the Problem of Plateau" (Sobre el problema de Plateau) y donde dio una solución al problema de Plateau, y en 1935, "Subharmonic Functions" (Funciones subarmónicas). Su trabajo se centró en la ciencia informática en la última década de su vida.
En Mayo de 1962 publicó uno de sus más famosos artículos en el periódico "Bell System Technical": "the busy beaver funciton" (el juego del castor laborioso) y la no computabilidad recogidos en su publicación "On Non-Computable Functions" (Funciones no computables).
Murió en Nueva Smyrna Beach, Florida.
En 1929 se trasladó a los Estados Unidos y dio una conferencia en la universidad de Harvard y en el Instituto Rice antes de obtener un puesto en el departamento de matemáticas en la universidad estatal de Ohio en 1930.
En 1935 se le concedió la ciudadanía Americana. Durante la segunda guerra mundial fue un científico del gobierno de los Estados Unidos, interrumpiendo su carrera académica. Se convirtió en presidente del departamento de matemáticas de la universidad estatal de Ohio en 1948.
En la década de 1920 demostró que las superficies tenían una triangulación esencial única. En 1933 publicó "On the Problem of Plateau" (Sobre el problema de Plateau) y donde dio una solución al problema de Plateau, y en 1935, "Subharmonic Functions" (Funciones subarmónicas). Su trabajo se centró en la ciencia informática en la última década de su vida.
En Mayo de 1962 publicó uno de sus más famosos artículos en el periódico "Bell System Technical": "the busy beaver funciton" (el juego del castor laborioso) y la no computabilidad recogidos en su publicación "On Non-Computable Functions" (Funciones no computables).
Murió en Nueva Smyrna Beach, Florida.
Juego
Condiciones del juego:
- Utilizar una máquina de Turing para resolverlo.
- La cinta puede tomar 2 valores {0,1} o {B,1}.
- La cinta debe estar llena de blancos o 0s.
- La máquina puede desplazarse en cualquier dirección sin restricciones (es válido el desplazamiento a la izquierda desde la primera posición).
Objetivo:
- Crear el mayor número de 1s posible.
- La máquina debe detenerse.
La parte variable del problema es el número de estados que podemos utilizar.
Definimos la función P: N => N donde el valor de entrada es el número de estados y el de salida el número de 1s máximo que puede generar la máquina de Turing con los estados dados.
El estado final está excluido por lo que para N = 1 la máquina de Turing tiene los estados q0 y qf pero qf no se utiliza ya que en el momento que la máquina de Turing llega a este estado se para.
Este juego no está aún resuelto, es decir, no se conoce la función descrita antes.
Existen soluciónes para un número de estados menor a 5 y cotas inferiores para un número de estados menor a 7.
También utilizaremos la función S igual a P sólo que ésta devuelve el número de pasos realizados por la máquina.
Estas son los valores exactos y las cotas inferiores:
N = 1, P = 1, S = 1
N = 2, P = 4, S = 6
N = 3, P = 6, S = 21
N = 4, P = 13, S = 107
N = 5, P = 4098, S = 47,176,870
N = 6, P = 4,6x10^1439, S = 2,5x10^2879
Como podemos observar es un crecimiento muy difícil de calcular.
Si colocásemos la cinta y por cada paso de la máquina la fuésemos clonando desplazándola hacia abajo quedarían las siguientes formas:
Para un estado:
La cinta queda con un sólo uno.
Para dos estados:
Para tres estados:
Para cuatro estados:
Aplicaciones
Sabemos que una máquina puede ser representada como una máquina de Turing de N estados donde la cinta es la memoria y la memoria sólo puede tener 1s y 0s. En máquina de Turing sería 1s y blancos.
Sabemos que una máquina de Turing con N estados no puede realizar más de S(N) pasos ya que, si los realizase, querría decir que habría entrado en un bucle infinito.
Sabiendo lo anterior podemos saber si una máquina parará o no ejecutándola ya que si la máquina en algún momento realiza más de S(N) pasos querrá decir que ha entrado en un bucle infinito.
Bibliografía
Trabajo realizado por David Domínguez Barbero.
Hola, ¿Por qué en el ejemplo para un estado, q1 es aceptado? Nunca se daría ese caso, ya que la cinta está completa de 0's.
ResponderEliminarA ese autómata finito le sobra la transición q1 1;1;R -> q1
Eliminar