En ciencia computacional teórica, el juego del castor ocupado (nombre original en inglés: busy beaver) busca obtener un programa de un tamaño dado, que (según la definición) produzca la mayor cantidad de salida posible o se ejecute durante el mayor número de pasos antes de detenerse. Dado que es fácil concebir un programa en bucle infinito que produzca una salida infinita o se ejecute durante un tiempo infinito, dichos programas se excluyen del juego. En lugar de lenguajes de programación tradicionales, los programas utilizados en el juego son máquinas de Turing de n estados, uno de los primeros modelos de computación matemáticos.
Las máquinas de Turing consisten en una cinta infinita y un conjunto finito de estados que sirven como el "código fuente" del programa. Producir la mayor cantidad de datos se define como escribir la mayor cantidad de unos en la cinta, también conocido como obtener la puntuación más alta, y ejecutar durante el mayor tiempo se define como tomar la mayor cantidad de pasos para detenerse. El juego del castor ocupado de n estados consiste en encontrar la máquina de Turing de n estados que ejecute n estados y finalmente se detenga. Se supone que dichas máquinas comienzan en una cinta en blanco, y se supone que la cinta contiene solo ceros y unos (una máquina de Turing binaria). El objetivo del juego es programar un conjunto de transiciones entre estados buscando la puntuación más alta o el tiempo de ejecución más largo, asegurándose de que la máquina se detenga finalmente.
Decidir el tiempo de ejecución o la puntuación del n-simo castor ocupado no es computable. De hecho, tanto las funciones Σ(n) como S(n) finalmente se vuelven mayores que cualquier función computable. Esto tiene implicaciones en teoría de la computabilidad, en el problema de la parada y en la teoría de la complejidad computacional. El concepto de castor ocupado fue introducido por primera vez por Tibor Radó en su artículo de 1962, "Sobre funciones no computables".
Una implicación del juego del castor ocupado es que, si fuera posible calcular las funciones Σ(n) y S(n) para todo n, entonces esto resolvería todas las conjeturas matemáticas que pueden ser reducidas a un problema de parada, por ejemplo, en una forma de "¿se detiene ?". Por ejemplo, existe una máquina de Turing de 27 estados que verifica la conjetura de Goldbach para cada número y se detiene ante un contraejemplo; si esta máquina no se detuviera tras ejecutarse durante S(27) pasos, entonces debe ejecutarse indefinidamente, resolviendo así la conjetura. Muchos otros problemas, incluyendo la hipótesis de Riemann (744 estados) y la consistencia de la teoría de conjuntos de Zermelo-Fraenkel (745 estados), pueden expresarse de forma similar, donde como máximo se deben verificar infinitos casos numerables.
Definición técnica El juego del castor ocupado de n estados (o juego BB-n), introducido en el artículo de Tibor Radó de 1962, involucra una clase de máquinas de Turing, cada una de las cuales debe cumplir con las siguientes especificaciones de diseño:
La ejecución de la máquina consiste en comenzar en el estado inicial, con la celda actual de la cinta siendo cualquier celda de una cinta en blanco (todas las posiciones cero), y luego iterar la función de transición hasta que se alcance el estado de parada (si es que se alcanza). Si y solo si la máquina finalmente se detiene, el número de unos que quedan en la cinta se denomina la puntuación de la máquina. Un castor ocupado de n estados, BB-n o simplemente "castor ocupado", es una máquina de Turing que gana el juego del castor ocupado de n estados. Según la definición, obtiene la puntuación más alta (denotada por Σ(n)) o se ejecuta durante el mayor tiempo (S(n)), entre todas las posibles máquinas de Turing de n estados.
Ejemplo
Las reglas para una máquina de Turing de 1 estado podrían ser: En el estado 1, si el símbolo actual es 0, escribe un 1, avanza un espacio a la derecha y vuelve al estado 1. En el estado 1, si el símbolo actual es 1, escribe un 0, avanza un espacio a la derecha y se detiene.
Esta máquina de Turing se desplazaría hacia la derecha, intercambiando el valor de todos los bits que recorre. Dado que la cinta inicial está compuesta solo por ceros, generaría una cadena infinita de unos. Esta máquina no sería una máquina de Turing competitiva porque se ejecuta indefinidamente en una cinta en blanco.
Funciones En su artículo original de 1962, Radó definió dos funciones relacionadas con el juego del castor ocupado: la función de puntuación Σ(n) y la función de desplazamientos S(n). Ambas toman un número de estados de la máquina de Turing y producen la puntuación máxima alcanzable por una máquina de Turing con ese número de estados, según alguna medida. La función de puntuación Σ(n) proporciona el número máximo de unos que una máquina de Turing con estados puede producir antes de detenerse, mientras que la función de desplazamientos S(n) proporciona el número máximo de desplazamientos (o, equivalentemente, pasos, ya que cada paso incluye un desplazamiento) que una máquina de Turing con estados puede realizar antes de detenerse. Demostró que ambas funciones no eran computables, porque cada una crecía más rápido que cualquier función computable. La función BB(n) se ha definido como cualquiera de estas funciones, por lo que esa notación no se utiliza en este artículo.
También se pueden definir otras funciones incomputables midiendo el rendimiento de las máquinas de Turing de maneras distintas al tiempo o al número máximo de unos: Por ejemplo: La función se define como el número máximo de unos contiguos que una máquina de Turing que se detiene puede escribir en una cinta en blanco. En otras palabras, este es el mayor unary number que una máquina de Turing de n estados puede escribir en una cinta. La función se define como el número máximo de casillas de cinta que una máquina de Turing que se detiene puede «leer» (es decir, visitar) antes de detenerse. Esto incluye la casilla inicial, pero no una casilla a la que la máquina solo llega después de la transición de parada (si la transición de parada está anotada con una dirección de movimiento), ya que esa casilla no influye en el comportamiento de la máquina. Este es el valor máximo de complejidad espacial de una máquina de Turing de «n» estados. Estas cuatro funciones juntas se encuentran en la relación . También se pueden definir más funciones ejecutando el juego en diferentes máquinas de computación, como máquinas de Turing de 3 símbolos, máquinas de Turing no deterministas, cálculo lambda o incluso lenguajes de programación arbitrarios.
Función de puntuación Σ La función de puntuación cuantifica la puntuación máxima que puede alcanzar un castor ocupado de un tamaño dado. Esta es una función no computable, porque crece asintóticamente más rápido que cualquier función computable.
La función de puntuación, , se define de modo que sea la puntuación máxima alcanzable (el número máximo de unos que finalmente aparecen en la cinta) entre todas las máquinas de Turing de dos símbolos y dos estados del tipo descrito anteriormente, que se detienen al iniciarse en una cinta en blanco.
Es evidente que es una función bien definida: para cada n, existen como máximo un número finito de máquinas de Turing de n estados como las anteriores, salvo isomorfismos, y por lo tanto, como máximo un número finito de tiempos de ejecución posibles.p. 880
Según la definición basada en la puntuación, cualquier máquina de Turing M de dos símbolos y dos estados que alcance la puntuación máxima () se denomina "busy beaver" (castor ocupado). Para cada n, existen al menos 4(n − 1)! castores ocupados de n estados.
Dado cualquier castor ocupado de n estados, se obtiene otro simplemente cambiando la dirección de desplazamiento en una transición de parada, un tercero invirtiendo uniformemente todas las direcciones de desplazamiento, y un cuarto invirtiendo la dirección de parada del castor ocupado con todas las direcciones intercambiadas. Además, una permutación de todos los estados excepto Inicio y Parada produce una máquina que alcanza la misma puntuación. Teóricamente, podría haber más de un tipo de transición que conduzca al estado de parada, pero en la práctica sería un desperdicio, ya que solo hay una secuencia de transiciones de estado que produce el resultado deseado.
No computabilidad El artículo de Radó de 1962 demostró que si es cualquier función computable, entonces Σ(n) > f(n) para todo n suficientemente grande, y por lo tanto, que Σ no es una función computable.
Además, esto implica que es un problema indecidible mediante un algoritmo general si una máquina de Turing arbitraria es un castor ocupado. Tal algoritmo no puede existir, ya que su existencia permitiría calcular Σ, lo cual es una imposibilidad demostrada. En particular, dicho algoritmo podría usarse para construir otro algoritmo que calcularía Σ de la siguiente manera: para cualquier n dado, se probarían todas las máquinas de Turing de 2 símbolos y n estados hasta encontrar una máquina de Turing de n estados; esta máquina se simularía para determinar su puntuación, que por definición es Σ(n).
Aunque Σ(n) es una función incomputable, existen algunos valores pequeños de n para los cuales es posible obtener sus valores y demostrar su corrección. No es difícil demostrar que Σ(0) = 0, Σ(1) = 1, Σ(2) = 4, y con creciente dificultad se puede demostrar que Σ(3) = 6, Σ(4) = 13 y Σ(5) = 4098 . Aún no se ha determinado Σ(n) para ningún caso de n > 5, aunque se han establecido límites inferiores (véase la sección valores conocidos más adelante).
Complejidad e imposibilidad de demostrar Σ Una variante de la complejidad de Kolmogórov se define de la siguiente manera:Boolos, Burgess & Jeffrey, 2007. "Computability and Logic" la complejidad de un número n es el número más pequeño de estados necesarios para una máquina de Turing de clase BB que se detiene con un solo bloque de n 1s consecutivos en una cinta inicialmente en blanco. La variante correspondiente de la complejidad de Kolmogórov establece que, en el contexto de un sistema axiomático dado para los números naturales, existe un número k tal que no se puede probar que ningún número específico tenga una complejidad mayor que k, y por lo tanto que no se puede probar ningún límite superior específico para Σ(k) (esto último se debe a que "la complejidad de n es mayor que k" se probaría si se probara que . Como se menciona en la referencia citada, para cualquier sistema axiomático de matemáticas ordinarias, el valor más pequeño k para el cual esto es cierto es mucho menor que 10⇈10. En consecuencia, en el contexto de las matemáticas ordinarias, ni el valor ni ningún límite superior de Σ(10⇈10) pueden demostrarse.
El teorema de incompletitud de Gödel se ilustra con este resultado: en un sistema axiomático de matemáticas ordinarias, existe una proposición verdadera pero indemostrable de la forma , e infinitas proposiciones verdaderas pero indemostrables de la forma .
Función del máximo número de desplazamientos S Además de la función Σ, Radó introdujo otra función extrema para las máquinas de Turing, la función del máximo número de desplazamientos, S, definida de la siguiente manera:
= el número de desplazamientos que M realiza antes de detenerse, para cualquier , = el mayor número de desplazamientos realizados por cualquier máquina de Turing de 2 símbolos y n estados que se detiene. Dado que las máquinas de Turing normales requieren un desplazamiento en cada transición o "paso" (incluida cualquier transición a un estado de parada), la función de desplazamientos máximos es, a su vez, una función del máximo de pasos.