Busy beaver

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 ⟨esta máquina de Turing⟩?". 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 máquina tiene n estados "operativos" más un estado de parada, donde n es un entero positivo, y uno de los n estados se distingue como el estado inicial. (Normalmente, los estados se etiquetan con 1, 2, ..., n, siendo el estado 1 el estado inicial, o con A, B, C, ..., siendo el estado A el estado inicial).
La máquina utiliza una única cinta bidireccional infinita (o ilimitada).
El alfabeto de la cinta es {0, 1}, donde 0 representa el símbolo en blanco.
La función de transición de la máquina toma dos entradas:
- el estado actual que no es de parada,
- el símbolo en la celda actual de la cinta,
y produce tres salidas:
- un símbolo para escribir sobre el símbolo en la celda actual de la cinta (puede ser el mismo símbolo que el símbolo sobrescrito),
- una dirección para moverse (izquierda o derecha; es decir, desplazarse a la celda de cinta una posición a la izquierda o a la derecha de la celda actual), y un estado al que transitar (que puede ser el estado de parada).

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 $n$ 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 $n$ 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 $n$ 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 ${\text{num}}(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 ${\text{espacio}}(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 ${\text{num}}(n)\leq \Sigma (n)\leq {\text{espacio}}(n)\leq S(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 (sucesión A333479 en OEIS) 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, ${\displaystyle \Sigma$ , se define de modo que $\Sigma (n)$ 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 $n$ del tipo descrito anteriormente, que se detienen al iniciarse en una cinta en blanco.

Es evidente que $\Sigma$ 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 ( $σ (M)= Σ(n)$ ) 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 $f:\mathbb {N} \to \mathbb {N}$ 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 (sucesión A028444 en OEIS). 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: 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 $n > Σ(k)$ . 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 $Σ(10⇈10)= n$ , e infinitas proposiciones verdaderas pero indemostrables de la forma $Σ(10⇈10) < n$ .

Función del máximo número de desplazamientos S

Además de la función Σ, Radó [1962] 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:

$s (M)$ = el número de desplazamientos que M realiza antes de detenerse, para cualquier $M \in E n$ ,
$S (n)= max{s (M)| M \in E n}$ = 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.

Radó demostró que S no es computable por la misma razón que Σ no lo es: crece más rápido que cualquier función computable. Lo demostró simplemente observando que, para cada n, S(n) ≥ Σ(n). Cada desplazamiento puede escribir un 0 o un 1 en la cinta, mientras que Σ cuenta un subconjunto de los desplazamientos que escribieron un 1, es decir, aquellos que no habían sido sobrescritos cuando la máquina de Turing se detuvo; por consiguiente, S crece al menos tan rápido como Σ, que ya se había demostrado que crecía más rápido que cualquier función computable.

Lin y Radó utilizaron la siguiente relación entre Σ y S (Estudios Computacionales de Problemas de Máquinas de Turing, 1965) para demostrar que Σ(3) = 6 y que S(3) = 21: Para un n dado, si se conoce S(n), entonces todas las máquinas de Turing de n estados pueden (en principio) ejecutarse hasta S(n) pasos, momento en el cual cualquier máquina que aún no se haya detenido nunca se detendrá. En ese punto, al observar qué máquinas se han detenido con la mayor cantidad de 1s en la cinta (es decir, las máquinas más activas), se obtiene de sus cintas el valor de Σ(n). El enfoque utilizado por Lin y Radó para el caso de n = 3 fue conjeturar que S(3) = 21 (tras conjeturar sin éxito 18), y luego simular todas las máquinas de 3 estados esencialmente diferentes (82.944 máquinas, equivalentes a 2¹⁰3⁴) hasta 21 pasos. Encontraron 26.073 máquinas que se detuvieron, incluyendo una que se detuvo solo después de 21 pasos. Al analizar el comportamiento de las máquinas que no se detuvieron dentro de los 21 pasos, lograron demostrar que ninguna de esas máquinas se detendría jamás, y la mayoría de ellas seguían un patrón determinado. Esto demostró la conjetura de que S(3) = 21, y también determinó que Σ(3) = 6, valor que alcanzaron varias máquinas, todas deteniéndose después de 11 a 14 pasos.

En 2016, Adam Yedidia y Scott Aaronson obtuvieron la primera cota superior (explícita) sobre el mínimo n para el cual S(n) es indemostrable en el conjunto de Zermelo-Fraenkel. Para ello construyeron una máquina de Turing de 7910 estados cuyo comportamiento no puede probarse basándose en los axiomas usuales de la teoría de conjuntos (los axiomas de Zermelo-Fraenkel con el axioma de elección), bajo hipótesis de consistencia razonables (propiedad de Ramsey estacionaria, equivalente a la existencia de cardenales sutiles arbitrariamente grandes). Stefan O'Rear luego la redujo a 1919 estados, con la dependencia de la propiedad de Ramsey estacionaria eliminada, y más tarde a 748 estados. En julio de 2023, Riebel lo redujo a 745 estados. Se informan mejoras adicionales en el sitio web del BB Challenge .

Prueba de la incomputabilidad de S(n) y Σ(n)

Supóngase que S(n) es una función computable y sea EvalS una máquina de Turing que evalúa S(n). Dada una cinta con n unos, producirá S(n) unos en la cinta y luego se detendrá. Sea Clean una máquina de Turing que limpia la secuencia de unos escrita inicialmente en la cinta. Sea Double una máquina de Turing que evalúa la función n + n. Dada una cinta con n unos, producirá 2n unos en la cinta y luego se detendrá.

Sean las opciones disponibles Double | EvalS | Clean, y sea n₀ el número de estados de esta máquina. Sea Create_n₀ una máquina de Turing que crea n₀ unos en una cinta inicialmente en blanco. Esta máquina puede construirse de manera trivial para tener n₀ estados (el estado i escribe 1, mueve el cabezal a la derecha y cambia al estado i + 1, excepto el estado n₀, que se detiene). Sea N la suma n₀ + n₀.

Sea BadS la composición Create_n₀ | Double | EvalS | Clean. Nótese que esta máquina tiene N estados. Partiendo de una cinta inicialmente en blanco, primero crea una secuencia de n₀ unos y luego la duplica, produciendo una secuencia de N unos. A continuación, EvalS producirá S(N) unos en la cinta, y finalmente borrará todos los unos y se detendrá. Pero la fase de limpieza continuará al menos S(N) pasos, por lo que el tiempo de funcionamiento de BadS es estrictamente mayor que S(N), lo cual contradice la definición de la función S(n).

La imposibilidad de calcular Σ(n) puede demostrarse de forma similar. En la demostración anterior, se debe intercambiar la máquina "EvalS" por "EvalΣ" y "Clean" por "Increment", una máquina de Turing simple que busca el primer 0 en la cinta y lo reemplaza por un 1.

La incomputabilidad de S(n) también se puede establecer haciendo referencia al problema de la parada en la cinta vacía. Este problema consiste en decidir, para cualquier máquina de Turing, si se detendrá o no al comenzar con una cinta vacía. El problema de la parada en una cinta vacía es equivalente al problema de la parada estándar y, por lo tanto, también es incomputable. Si S(n) fuera computable, se podría resolver el problema de la parada en la cinta vacía simplemente ejecutando cualquier máquina de Turing con n estados durante S(n) pasos; si aún no se ha detenido, nunca lo hará. Por lo tanto, dado que el problema de la parada en una cinta vacía no es computable, se deduce que S(n) también debe ser incomputable.

Incomputabilidad de espacio(n) y num(n)

Tanto las funciones ${\text{espacio}}(n)$ como ${\text{num}}(n)$ son incomputables. Esto se puede demostrar para ${\text{espacio}}(n)$ observando que cada casilla de cinta en la que una máquina de Turing escribe un uno, también debe visitarla; en otras palabras, $\Sigma (n)\leq {\text{espacio}}(n)$ . Se puede demostrar que la función ${\text{num}}(n)$ es incomputable probando, por ejemplo, que ${\text{espacio}}(n)<{\text{num}}(3n+3)$ : esto se puede hacer diseñando una máquina de Turing de (3n+3) estados que simule el campeón del espacio de n estados y luego la use para escribir al menos ${\text{espacio}}(n)$ unos contiguos en la cinta.

Generalizaciones

Se pueden definir fácilmente análogos de la función de desplazamiento en cualquier lenguaje de programación, siempre que los programas se puedan describir mediante cadenas de bits y se pueda contar el número de pasos de un programa. Por ejemplo, el juego del castor ocupado también se puede generalizar a dos dimensiones utilizando máquinas de Turing en cintas bidimensionales, o a máquinas de Turing que pueden permanecer en el mismo lugar y moverse a la izquierda y a la derecha. Alternativamente, se puede definir una "función del castor ocupado" para diversos modelos de computación con complejidad de Kolmogórov. Esto se logra tomando ${BB}(n)$ como el mayor entero $m$ tal que $K_{L}(m)\leq n$ , donde $K_{L}(m)$ es la longitud del programa más corto en $L$ que produce $m$ : ${BB}(n)$ es, por lo tanto, el mayor entero que un programa con longitud $n$ o menor puede producir en $L$ .

La máquina de 6 estados y 2 símbolos de mayor duración que posee la propiedad adicional de invertir el valor de la cinta en cada paso produce 6147 1s después de 47 339 970 pasos. Así, para la clase de máquina de Turing Inversa (RTM), S_RTM(6) = 47 339 970 y Σ_RTM(6) = 6147. De igual modo, se podría definir una función análoga a la función Σ para una máquina de registro como el mayor número que puede estar presente en cualquier registro al detenerse, para un número dado de instrucciones.

Diferentes números de símbolos

Una generalización sencilla es la extensión a máquinas de Turing con m símbolos en lugar de solo dos (0 y 1). Por ejemplo, una máquina de Turing ternaria con m = 3 símbolos tendría los símbolos 0, 1 y 2. La generalización a máquinas de Turing con n estados y m símbolos define las siguientes funciones generalizadas de castor ocupado:

Σ(n, m): el mayor número de valores distintos de cero que puede imprimir una máquina de n estados y m símbolos, iniciada en una cinta inicialmente en blanco, antes de detenerse, y
S(n, m): el mayor número de pasos que puede dar una máquina de n estados y m símbolos, iniciada en una cinta inicialmente en blanco, antes de detenerse.

Por ejemplo, la máquina de 3 estados y 3 símbolos que más tiempo ha tardado en ejecutarse, 119 112 334 170 342 540 pasos antes de detenerse.

Máquinas de Turing no deterministas

Tiempos de parada máximos y estados del caso p, 2 estados, 2-colores NDTM
p	Pasos	Estados
1	2	2
2	4	4
3	6	7
4	7	11
5	8	15
6	7	18
7	6	18

El problema puede extenderse a una máquina de Turing no determinista buscando el sistema con el mayor número de estados en todas las ramas o la rama con el mayor número de pasos. La cuestión de si una NDTM dada se detendrá sigue siendo computacionalmente irreducible, y el cálculo necesario para encontrar una NDTM que se detenga es significativamente mayor que en el caso determinista, ya que hay múltiples ramas que deben considerarse. Para un sistema de 2 estados y 2 colores con p casos o reglas, la tabla de la derecha muestra el número máximo de pasos antes de la parada y el número máximo de estados únicos creados por la NDTM.

Aplicaciones

Problemas matemáticos abiertos

Además de plantear un juego matemático bastante desafiante, las funciones Σ(n) y S(n) ofrecen un enfoque completamente nuevo para resolver problemas de matemáticas puras. Muchos problemas abiertos en matemáticas podrían, en teoría, pero no en la práctica, resolverse sistemáticamente dado el valor de S(n) para un n suficientemente grande. Teóricamente hablando, el valor de S(n) codifica la respuesta a todas las conjeturas matemáticas que pueden ser verificadas en tiempo infinito por una máquina de Turing con menos de n estados.

Considérese cualquier conjetura $\Pi _{1}^{0}$ : cualquier conjetura que pueda ser refutada mediante un contraejemplo entre un conjunto de casos numerable (por ejemplo, la conjetura de Goldbach). Escríbase entonces un programa informático que pruebe secuencialmente esta conjetura para valores crecientes. En el caso de la conjetura de Goldbach, se consideraría cada número par igual a 4 de forma secuencial y se comprobaría si es o no la suma de dos números primos. Supóngase que este programa se simula en una máquina de Turing de n estados. Si se encuentra un contraejemplo (un número par igual a 4 que no es la suma de dos primos en el presente ejemplo), se detiene e indica que no lo es. Sin embargo, si la conjetura es verdadera, el programa nunca se detendrá. Este programa se detiene "solo" si encuentra un contraejemplo.

Ahora bien, este programa se simula en una máquina de Turing de n estados, por lo que si se conoce S(n), se puede decidir (en un tiempo finito) si se detendrá o no simplemente ejecutando la máquina esa cantidad de pasos. Y si, después de S(n) pasos, la máquina no se detiene, se sabe que nunca lo hará y, por lo tanto, que no hay contraejemplos a la conjetura dada (es decir, no hay números pares que no sean la suma de dos primos). Esto probaría que la conjetura es verdadera. Así, valores específicos (o límites superiores) para S(n) podrían usarse, en teoría, para resolver sistemáticamente muchos problemas abiertos en matemáticas.

Sin embargo, los resultados actuales sobre el problema del castor ocupado sugieren que esto no será práctico por dos razones:

Es extremadamente difícil demostrar valores para la función del castor ocupado (y para la función del máximo de desplazamientos). Cada valor exacto conocido de S(n) se demostró enumerando cada máquina de Turing de n estados y probando si cada una se detiene o no. Habría que calcular S(n) mediante algún método menos directo para que fuera realmente útil.
Los valores de S(n) y otras funciones de castor ocupado se vuelven muy grandes, muy rápidamente. Mientras que el valor de S(5) es solo 47.176.870, el valor de S(6) es más que $^{^{^{^{9}2}2}}2$ , es decir, 2 elevado a la 2 elevado a la 2 elevado a la 9, que es al menos 2 pentado a la 5. El valor de S(25), que es el número de pasos que el programa capaz de verificar la conjetura de Goldbach necesitaría ejecutar para dar una respuesta concluyente, es incomprensiblemente enorme, y no remotamente posible escribirlo, y mucho menos materializar una máquina capaz de ejecutar el programa en el universo observable.

Consistencia de las teorías

Otra propiedad de S(n) es que ninguna teoría teoría axiomatizada aritméticamente correcta y computable puede demostrar todos los valores de la función. Específicamente, dada una teoría $T$ computable y aritméticamente correcta, existe un número $n_{T}$ tal que para todo $n\geq n_{T}$ , ninguna afirmación de la forma $S(n)=k$ puede demostrarse en $T$ . Esto implica que para cada teoría existe un valor máximo específico de S(n) que puede demostrar. Esto es cierto porque para cada teoría de este tipo $T$ , una máquina de Turing con $n_{T}$ estados puede diseñarse para enumerar cada demostración posible en $T$ . Si la teoría es inconsistente, entonces todas las afirmaciones falsas son demostrables, y la máquina de Turing puede recibir la condición de detenerse si, y solo si, encuentra una prueba de, por ejemplo, $0=1$ . Cualquier teoría que demuestre el valor de $S(n_{T})$ demuestra su propia consistencia, violando el segundo teorema de incompletitud de Gödel. Esto puede usarse para colocar varias teorías en una escala, por ejemplo los diversos axiomas de cardinales grandes en conjuntos de Zermelo-Fraenkel: si a cada teoría $T$ se le asigna como su número $n_{T}$ , las teorías con valores mayores de $n_{T}$ demuestran la consistencia de aquellas por debajo de ellas, colocando todas esas teorías en una escala infinita numerable.

Ejemplos notables

Se ha construido una máquina de Turing binaria de 745 estados que se detiene si y solo si es inconsistente con la teoría de Zermelo-Fraenkel.
Se ha construido una máquina de Turing de 744 estados que se detiene si y solo si la hipótesis de Riemann es falsa.
Se construyó una máquina de Turing de 43 estados que se detiene si y solo si la conjetura de Goldbach es falsa. Esta se redujo posteriormente a una máquina de 27 estados, luego a una de 25 estados, y posteriormente se demostró y verificó formalmente en el lenguaje de demostración de teoremas Lean.
Se ha construido una máquina de Turing de 15 estados que se detiene si y solo si se cumple que la conjetura formulada por Paul Erdős en 1979 es falsa: para todo n > 8, existe al menos un dígito 2 en la representación en base 3 de 2ⁿ.
Se ha descubierto una máquina de Turing de 6 estados que se detiene si y solo si las aplicaciones repetidas de ${\textstyle x_{n+1}=\left\lfloor {\frac {3x_{n}}{2}}\right\rfloor +2}$ a partir de 4 producen el doble de valores impares que pares. Posteriormente se la denominó "Antihydra".

Tesis física de Church-Turing

Las propiedades de crecimiento de la función Busy Beaver tienen implicaciones para el comportamiento de los sistemas físicos, asumiendo la veracidad de la tesis física de Church–Turing. Si la tesis física de Church-Turing es válida y todas las funciones físicamente computables son Turing-computables, entonces ninguna magnitud física directamente medible puede crecer más rápido que la función Busy Beaver, ya que ninguna función Turing-computable puede crecer más rápido que ella. Las funciones simples de $BB(n)$ también impondrían un límite inferior a las tasas de crecimiento, así como límites superiores e inferiores a las tasas de convergencia.

Resultados conocidos

Límites inferiores

Máquinas de Green

En 1964, Milton Green desarrolló una cota inferior para la variante de conteo de unos de la función del castor ocupado, que se publicó en las actas del simposio IEEE de 1964 sobre teoría de circuitos de conmutación y diseño lógico. Heiner Marxen y Jürgen Buntrock la describieron como "una cota inferior no trivial (no recursiva primitiva)". Esta cota inferior se puede calcular, pero es demasiado compleja para expresarla como una sola expresión en términos de n. Esto se realizó con un conjunto de máquinas de Turing, cada una de las cuales demostró la cota inferior para un $n$ determinado. Cuando $n = 8$ el método da como resultado:

\Sigma (8)\geq 3\times (7\times 3^{92}-1)/2\approx 8.248\times 10^{44}.

En contraste, la mejor cota inferior actual (a fecha de 2026) para $\Sigma (6)$ es $2\uparrow \uparrow \uparrow 5$ , donde las $\uparrow$ forman parte de la representación en notación flecha de Knuth. Esto representa $2\uparrow \uparrow 2\uparrow \uparrow 2\uparrow \uparrow 4$ . El valor de $\Sigma (8)$ es probablemente mucho mayor.

El límite inferior de Green se demostró mediante una construcción recursiva de una serie de máquinas de Turing, cada una de las cuales estaba compuesta por una más pequeña con dos estados adicionales que aplicaban repetidamente la máquina más pequeña a la cinta de entrada. Definiendo el valor del castor ocupado de ⁠ $N$ ⁠ estados en una cinta que contiene $m$ unos como $B_{N}(m)$ (la salida final de cada máquina es su valor en $m=0$ , porque una cinta en blanco tiene 0 unos), las relaciones de recursión son las siguientes:

{\begin{aligned}B_{N}(0)&=1,\\B_{1}(m)&=m+1,\\B_{N}(m)&=1+B_{N-2}(1+B_{N}(m-1)).\end{aligned}}

Esto conduce a dos fórmulas para calcular el límite inferior $G(N)$ dado por la máquina ⁠ $N$ ⁠:

{\begin{aligned}G(N)&=B_{N-2}(B_{N-2}(1)){\text{ para N impar }},{\text{y}}\\G(N)&=1+B_{N-3}(1+B_{N-3}(1)){\text{ para N par}}.\end{aligned}}

El límite inferior de Green ⁠ $G(N)$ ⁠ también puede relacionarse con la función de Ackermann. En particular,

A(N,N)<G(4N+3)<A(2N+1,4)

para todos los enteros positivos ⁠ $N$ ⁠.

Relaciones entre las funciones de la máquina de Turing

Es trivial que $S (n) \geq Σ(n)$ , ya que una máquina que escribe $Σ(n)$ unos debe emplear al menos $Σ(n)$ pasos para hacerlo. Es posible establecer varios límites superiores para el tiempo $S (n)$ con el número de unos $Σ(n)$ :

$S(n)\leq (n+1)\times \Sigma (5n)\times 2^{\Sigma (5n)}$ (Rado)
$S(n)\leq \Sigma (9n)$ (Buro)
$S(n)\leq (2n-1)\times \Sigma (3n+3)$ (Ben-Amram, Julstrom y Zwick)

Al definir $num(n)$ como el número máximo de unos que una máquina de Turing de $n$ estados puede generar de forma contigua, en lugar de en cualquier posición (el mayor número unario que puede generar), es posible demostrar que

{\begin{aligned}\operatorname {num} (n)&<\Sigma (n)\\S(n)&<\operatorname {num} (n+o(n))\\S(n)&<\operatorname {num} (3n+6)\end{aligned}}

Ben-Amram y Petersen, 2002, también proporcionan una cota asintóticamente mejorada para $S (n)$ . Existe una constante $c$ tal que para todo $n \geq 2$ ,

S(n)\leq \Sigma \left(n+\left\lceil {\frac {8n}{\log _{2}n}}\right\rceil +c\right).

Valores exactos y cotas inferiores y superiores

La siguiente tabla muestra los valores exactos y algunas cotas inferiores conocidas para S(n), Σ(n) y otras funciones de la máquina de Turing de dos símbolos. En esta tabla se utilizan máquinas de Turing de dos símbolos. Las entradas marcadas con "?" son al menos tan grandes como las demás entradas a la izquierda (ya que todas las máquinas de n estados son también máquinas de (n+1) estados) y no mayores que las entradas superiores (porque S(n) ≥ espacio(n) ≥ Σ(n) ≥ num(n)). Por lo tanto, se sabe que espacio(6) es mayor que 2 $\uparrow \uparrow \uparrow$ 5, puesto que espacio(n) ≥ Σ(n) y Σ(6) > 2 $\uparrow \uparrow \uparrow$ 5. 47 176 870 es una cota superior para espacio(5), porque S(5) = 47 176 870 () y S(n) ≥ espacio(n). 4098 es una cota superior para num(5), ya que Σ(5) = 4098 y Σ(n) ≥ num(n). La última entrada marcada como "?" es num(6), porque Σ(n) > (6) > 2 $\uparrow \uparrow \uparrow$ 5, pero Σ(n) ≥ num(n), lo mismo ocurre con num(7).

Valores de las funciones de Busy Beaver
Función	2 estados	3 estados	4 estados	5 estados	6 estados	7 estados
S(n)	6	21	107	47 176 870	> 2 $\uparrow \uparrow \uparrow$ 5	> 2 $\uparrow ^{11}$ 2 $\uparrow ^{11}$ 3
espacio(n)	4	7	16	12289	> 2 $\uparrow \uparrow \uparrow$ 5 espacio(n) ≥ Σ(n)	> 2 $\uparrow ^{11}$ 2 $\uparrow ^{11}$ 3
Σ(n)	4	6	13	4098	> 2 $\uparrow \uparrow \uparrow$ 5	> 2 $\uparrow ^{11}$ 2 $\uparrow ^{11}$ 3
num(n)	4	6	12	165	?	?

El problema del castor ocupado de 5 estados fue descubierto por Heiner Marxen y Jürgen Buntrock en 1989, pero no fue hasta 2024 que un colectivo matemático aficionado en línea lo reconoció como el quinto mejor problema del castor ocupado, mediante una demostración formalizada en Coq.

Lista de castores ocupados

Véase también: Ejemplos de máquinas de Turing

Estas son tablas de reglas para máquinas de Turing que generan Σ(1) y S(1), Σ(2) y S(2), Σ(3) (pero no S(3)), Σ(4) y S(4), Σ(5) y S(5), y la mejor cota inferior conocida para Σ(6) y S(6).

En las tablas, las columnas representan el estado actual y las filas el símbolo leído de la cinta. Cada entrada es una cadena de tres caracteres que indica el símbolo a escribir en la cinta, la dirección de movimiento y el nuevo estado (en ese orden). El estado de parada se muestra como H.

Cada máquina comienza en el estado A con una cinta infinita que contiene solo ceros. Por lo tanto, el símbolo inicial leído de la cinta es un 0.

Clave de resultado: (comienza en la posición del texto con raya superior, termina en la posición del texto con raya inferior

Castor ocupado de 1 estado y 2 símbolos
	A
0	1RH
1	(no usado)

Resultado: 0 0 1 0 0 (1 paso, un "1" en total)

Castor ocupado de 2 estados y 2 símbolos
	A	B
0	1RB	1LA
1	1LB	1RH

Resultado: 0 0 1 1 1 1 0 0 (6 pasos, cuatro "1" en total)

Castor ocupado de 3 estados y 2 símbolos
	A	B	C
0	1RB	0RC	1LC
1	1RH	1RB	1LA

Resultado: 0 0 1 1 1 1 1 1 0 0 (14 pasos, seis "1" en total).

Esta es una de varias máquinas no equivalentes que generan seis "1". A diferencia de las máquinas anteriores, esta es muy eficiente para Σ, pero no para S. (S(3) = 21, y la máquina obtiene solo cinco "1".)

Castor ocupado de 4 estados y 2 símbolos
	A	B	C	D
0	1RB	1LA	1RH	1RD
1	1LB	0LC	1LD	0RA

Resultado: 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 (107 pasos, trece "1" en total)

Castor ocupado de 5 estados y 2 símbolos
	A	B	C	D	E
0	1RB	1RC	1RD	1LA	1RH
1	1LC	1RB	0LE	1LD	0LA

Resultado: 4098 "1" con 8191 "0" intercalados en 47.176.870 pasos.

Obsérvese en la imagen de la derecha cómo esta solución es cualitativamente similar a la evolución de algunos autómatas celulares.

Actual mejor contendiente de 6 estados y 2 símbolos
	A	B	C	D	E	F
0	1RB	1RC	1LD	1RA	0LD	1RA
1	1RA	1RH	0RF	0LE	1RC	0RE

Resultado: más de 2↑↑↑5 "1" en más de 2↑↑↑5 pasos, donde 2↑↑↑5 = 2↑↑2↑↑2↑↑2↑↑2 y ↑↑ representa una tetración.

Visualizaciones

En la siguiente tabla, las reglas para cada castor ocupado (que maximiza S) se representan visualmente, con cuadrados naranjas que corresponden a un "1" en la cinta y blancos a un "0". La posición de la cabeza se indica mediante el ovoide negro, y la orientación de la cabeza representa el estado. Las cintas individuales se disponen horizontalmente, con el tiempo avanzando de arriba abajo. El estado de parada se representa mediante una regla que mapea un estado a sí mismo (la cabeza no se mueve).

Evolución de castores ocupados con 1 a 4 estados

Reglas para el castor ocupado de un solo estado

Reglas para el castor ocupado de dos estados

Reglas para el castor ocupado de tres estados

Reglas para el castor ocupado de cuatro estados

Evolución del castor ocupado de un estado hasta detenerse. El estado inicial desencadena una parada, en la que se escribe un único "1" antes de la terminación.

Evolución del castor ocupado de 2 estados hasta detenerse

Evolución del castor ocupado de 3 estados hasta detenerse

Evolución del castor ocupado de 4 estados hasta detenerse. La línea inferior de la imagen izquierda se extiende hasta la línea superior de la imagen derecha. El último paso escribe "1" antes de detenerse (no se muestra).

Véase también

Referencias

1 2 «Story # space-time-diagrams». The Busy Beaver Challenge (en inglés). Consultado el 9 de julio de 2024.
1 2 3 4 5 Weisstein, Eric W. «Busy Beaver». Wolfram MathWorld. Archivado desde el original el 7 de diciembre de 2023. Consultado el 21 de noviembre de 2023.
1 2 3 Brubaker, Ben (2 de julio de 2024). «Amateur Mathematicians Find Fifth 'Busy Beaver' Turing Machine». Quanta Magazine (en inglés). Consultado el 3 de julio de 2024.
1 2 3 4 5 6 7 8 9 10 11 12 Radó, Tibor (mes de mayo de 1962). «On non-computable functions». Bell System Technical Journal 41 (3): 877-884. doi:10.1002/j.1538-7305.1962.tb00480.x. Archivado desde el original el 12 de octubre de 2021. Consultado el 7 de julio de 2022.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 Aaronson, Scott (29 de septiembre de 2020). «The Busy Beaver Frontier». SIGACT News 51 (3): 32-54. ISSN 0163-5700. doi:10.1145/3427361.3427369. Archivado desde el original el 5 de julio de 2022.
1 2 3 4 5 6 7 8 Pavlus, John (10 de diciembre de 2020). «How the Slowest Computer Programs Illuminate Math's Fundamental Limits». Quanta Magazine (en inglés). Archivado desde el original el 10 de diciembre de 2020. Consultado el 11 de diciembre de 2020.
1 2 3 Leng, Yijun. «GitHub Repository 'goldbach_tm27'». GitHub.
1 2 3 Aaronson, Scott (5 de julio de 2023). «Life, blogging, and the Busy Beaver function go on». Shtetl-Optimized. Archivado desde el original el 28 de agosto de 2023. Consultado el 27 de agosto de 2023.
1 2 3 Riebel, Johannes (mes de marzo de 2023). The Undecidability of BB(748): Understanding Gödel's Incompleteness Theorems (Tesis de Bachelor's). Universidad de Augsburgo. Archivado desde el original el 17 de septiembre de 2024. Consultado el 24 de septiembre de 2024.
1 2 3 4 5 6 7 Ben-Amram, A. M.; Julstrom, B. A.; Zwick, U. (1 de agosto de 1996). «A note on busy beavers and other creatures». Mathematical Systems Theory (en inglés) 29 (4): 375-386. ISSN 1433-0490. doi:10.1007/BF01192693.
1 2 3 4 5 6 7 8 Aaronson, Scott (2 de julio de 2024). «BusyBeaver(5) is now known to be 47,176,870». Shtetl-Optimized (en inglés estadounidense). Consultado el 4 de julio de 2024.
1 2 3 Wolfram, Stephen (4 de febrero de 2021). «Multiway Turing Machines». www.wolframphysics.org (en inglés). Archivado desde el original el 7 de julio de 2022. Consultado el 7 de julio de 2022.
↑ Chaitin, 1987, p. 2.
↑ Boolos, Burgess & Jeffrey, 2007. "Computability and Logic"
1 2 3 Lin, Shen; Rado, Tibor (mes de abril de 1965). «Computer studies of Turing machine problems». Journal of the ACM 12 (2): 196-212. S2CID 17789208. doi:10.1145/321264.321270.
↑ Yedidia, Adam; Aaronson, Scott (mes de mayo de 2016). «A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory». arXiv:1605.04343 [cs.FL].
↑ Aron, Jacob (11 de mayo de 2016). «This Turing machine should run forever unless maths is wrong». New Scientist (en inglés estadounidense). Archivado desde el original el 20 de octubre de 2016. Consultado el 25 de septiembre de 2016.
↑ Version from May 3rd contained 7918 states: Aaronson, Scott (3 de mayo de 2016). «The 8000th Busy Beaver number eludes ZF set theory». Shtetl-Optimized. Archivado desde el original el 27 de septiembre de 2016. Consultado el 25 de septiembre de 2016.
↑ Friedman, Harvey M. (15 de enero de 2001). «Subtle cardinals and linear orderings». Annals of Pure and Applied Logic 107 (1): 1-34. ISSN 0168-0072. doi:10.1016/S0168-0072(00)00019-1.
1 2 3 Aaronson, Scott (3 de mayo de 2016). «Three announcements». Shtetl-Optimized. Consultado el 27 de abril de 2018.
↑ «sorear/metamath-turing-machines: Metamath proof enumerators and other things». GitHub. 13 de febrero de 2019. Archivado desde el original el 17 de abril de 2021. Consultado el 19 de mayo de 2018.
↑ «Reversal Turing machine». skelet.ludost.net. Consultado el 10 de febrero de 2022.
↑ «A060843 - OEIS». oeis.org. Consultado el 19 de febrero de 2026.
↑ Pascal Michel's Busy Beaver Competitions Archivado el 6 de octubre de 2023 en Wayback Machine., página que enumera a los mejores contendientes conocidos.
↑ Michel, Pascal (14 de diciembre de 2015). «Problems in number theory from busy beaver competition». Logical Methods in Computer Science 11 (4): 10.
↑ Chaitin, 1987, p. 3.
↑ Bischoff, Manon (25 de julio de 2024). «Mathematicians Have Finally Found the Fifth 'Busiest Beaver'». Scientific American. Consultado el 10 de septiembre de 2025.
↑ Aaronson, Scott (28 de junio de 2025). «BusyBeaver(6) is really quite large». Shtetl-Optimized (en inglés estadounidense). Consultado el 16 de julio de 2025.
↑ Stérin, Tristan; Woods, Damien (2021). «Hardness of busy beaver value BB(15)». arXiv:2107.12475 [cs.LO].
↑ Erdös, Paul (1979). «Some unconventional problems in number theory». Mathematics Magazine 52 (2): 67-70. JSTOR 2689842. doi:10.1080/0025570X.1979.11976756. Archivado desde el original el 13 de junio de 2022. Consultado el 7 de julio de 2022.
↑ «Antihydra». BusyBeaverWiki (en inglés). Consultado el 18 de junio de 2025.
1 2 Ord, Toby (2024). «Bounds on the rates of growth and convergence of all physical processes». arXiv:2410.10928 [physics.hist-ph].
↑ Karmela Padavic-Callaghan (1 de noviembre de 2024). «There may be a cosmic speed limit on how fast anything can grow». New Scientist.
↑ Brady, Allen H. (mes de marzo de 1998). «Heiner Marxen and Jürgen Buntrock. Attacking the busy beaver 5. Bulletin of the European Association for Theoretical Computer Science, no. 40 (Feb.1990), pp. 247–251. – Pascal Michel. Busy beaver competition and Collatz-like problems. Archive for mathematical logic, vol. 32 (1993), pp. 351–367». The Journal of Symbolic Logic (book review) (en inglés) 63 (1): 331-332. ISSN 0022-4812. JSTOR 2586607. doi:10.2307/2586607. Archivado desde el original el 5 de julio de 2024. Consultado el 5 de julio de 2024. Free HTML version by author Archivado el 9 de octubre de 2006 en Wayback Machine.
1 2 3 4 Green, Milton W. (11 de noviembre de 1964). «A lower bound RADO's sigma function for binary turing machines». 1964 Proceedings of the Fifth Annual Symposium on Switching Circuit Theory and Logical Design. IEEE Computer Society. pp. 91-94. doi:10.1109/SWCT.1964.3.
1 2 3 4 5 6 7 8 Michel, Pascal. «Historical survey of Busy Beavers». Consultado el 24 de enero de 2026.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Ben-Amram, A. M.; Petersen, H. (2002). «Improved bounds for functions related to busy beavers». Theory of Computing Systems 35 (1): 1-11. MR 1879169. doi:10.1007/s00224-001-1052-0.
1 2 3 Blanchard, Justin; Briggs, Daniel; Deka, Konrad; Fenner, Nathan; Forster, Yannick; Georgiev, Georgi; House, Matthew L.; Hunter, Rachel et ál. (15 de septiembre de 2025). «Determination of the fifth Busy Beaver value». arXiv:2509.12337 [cs.LO].
↑ «0RB1LD_1LC1RB_1LD1RE_1LA1LE_1LZ0RC - BusyBeaverWiki». wiki.bbchallenge.org. Consultado el 17 de julio de 2026.
↑ «[July 2nd 2024] We have proved 'BB(5)= 47,176,870'». The Busy Beaver Challenge (en inglés). 2 de julio de 2024. Archivado desde el original el 2 de julio de 2024. Consultado el 2 de julio de 2024.
↑ Brubaker, Ben (2 de julio de 2024). «Amateur Mathematicians Find Fifth ‘Busy Beaver’ Turing Machine». Quanta Magazine (en inglés). Consultado el 4 de febrero de 2026.
↑ Shen Lin (1963). Computer studies of Turing machine problems (Tesis de Ph.D.). Universidad Estatal de Ohio.

Bibliografía

Radó, Tibor (mes de mayo de 1962). «On non-computable functions». Bell System Technical Journal 41 (3): 877-884. doi:10.1002/j.1538-7305.1962.tb00480.x. Archivado desde el original el 12 de octubre de 2021. Consultado el 7 de julio de 2022.
Aquí Radó definió por primera vez el problema del castor ocupado y demostró que era incomputable y que crecía más rápido que cualquier función computable.
Lin, Shen; Radó, Tibor (mes de abril de 1965). «Computer Studies of Turing Machine Problems». Journal of the ACM 12 (2): 196-212. S2CID 17789208. doi:10.1145/321264.321270.
Los resultados de este artículo ya habían aparecido parcialmente en la tesis doctoral de Lin de 1963, bajo la dirección de Radó. Lin y Radó demuestran que S(3) = 6 y S(3) = 21 al probar que todas las máquinas de Turing de 3 estados y 2 símbolos que no se detienen en 21 pasos nunca se detendrán. (La mayoría se demuestran automáticamente mediante un programa informático; sin embargo, 40 se demuestran mediante inspección humana).
Brady, Allen H. (mes de abril de 1983). «The determination of the value of Rado's noncomputable function Σ(k) for four-state Turing machines». Mathematics of Computation 40 (162): 647-665. JSTOR 2007539. doi:10.1090/S0025-5718-1983-0689479-6.
Brady demuestra que S(4) = 13 y S(4) = 107. Brady define dos nuevas categorías para máquinas de Turing de 3 estados y 2 símbolos que no se detienen: árboles de Navidad y contadores. Utiliza un programa informático para demostrar que todas las máquinas, excepto 27 que se ejecutan durante más de 107 pasos, son variantes de árboles de Navidad y contadores, y se puede demostrar que se ejecutan infinitamente. Las últimas 27 máquinas (denominadas "rechazadas") se demuestran mediante inspección personal por el propio Brady que no se detienen.
Machlin, Rona; Stout, Quentin F. (mes de junio de 1990). «The complex behavior of simple machines». Physica D: Nonlinear Phenomena 42 (1–3): 85-98. Bibcode:1990PhyD...42...85M. doi:10.1016/0167-2789(90)90068-Z. hdl:2027.42/28528. Archivado desde el original el 30 de enero de 2012. Consultado el 7 de julio de 2022.
Machlin y Stout describen el problema del castor ocupado y muchas técnicas utilizadas para encontrar castores ocupados (que aplican a máquinas de Turing de 4 estados y 2 símbolos, verificando así la demostración de Brady). Sugieren cómo estimar una variante de la probabilidad de parada de Chaitin (O).
Marxen, Heiner; Buntrock, Jürgen (mes de febrero de 1990). «Attacking the Busy Beaver 5». Bulletin of the EATCS 40: 247-251. Archivado desde el original el 9 de octubre de 2006. Consultado el 19 de enero de 2020.
Marxen y Buntrock demuestran que S(5) = 4098 y S(5) = 47 176 870 y describen en detalle el método que utilizaron para encontrar estas máquinas y probar que muchas otras nunca se detendrán.
Green, Milton W. (1964). «A lower bound RADO's sigma function for binary turing machines». 1964 Proceedings of the Fifth Annual Symposium on Switching Circuit Theory and Logical Design. pp. 91-94. doi:10.1109/SWCT.1964.3. Archivado desde el original el 3 de febrero de 2019. Consultado el 7 de julio de 2022.
Green construye recursivamente máquinas para cualquier número de estados y proporciona la función recursiva que calcula su puntuación (calcula s), proporcionando así una cota inferior para S. El crecimiento de esta función es comparable al de Función de Ackermann.
Dewdney, Alexander K. (1984). «A computer trap for the busy beaver, the hardest working Turing machine». Scientific American 251 (2): 10-17.
Los programas del castor ocupado se describen en Alexander Dewdney en «Scientific American», agosto de 1984, páginas 19-23, también en marzo de 1985, pág. 23 y abril de 1985, pág. 30.
Chaitin, Gregory J. (1987). «Computing the Busy Beaver Function». En Cover, T. M.; Gopinath, B., eds. Open Problems in Communication and Computation. Springer. pp. 108-112. ISBN 978-0-387-96621-2. Archivado desde el original el 30 de diciembre de 2017. Consultado el 7 de julio de 2022.
Brady, Allen H. (1995). «The Busy Beaver Game and the Meaning of Life». En Herken, Rolf, ed. The Universal Turing Machine: A Half-Century Survey (2nd edición). Wien, New York: Springer-Verlag. pp. 237-254. ISBN 978-3-211-82637-9.
En este artículo, Brady (conocido por su trayectoria en cuatro estados) describe parte de la historia de este fenómeno y denomina a su búsqueda «El juego del castor ocupado». Describe otros juegos (por ejemplo, autómata celular y Juego de la vida). De particular interés es «El juego del castor ocupado en dos dimensiones» (pág. 247). Con 19 referencias.
Booth, Taylor L. (1967). Sequential Machines and Automata Theory. New York: Wiley. ISBN 978-0-471-08848-6.
Véase el Capítulo 9, Máquinas de Turing. Un libro complejo, dirigido a ingenieros eléctricos y técnicos especializados. Trata sobre recursión, recursión parcial con referencia a las máquinas de Turing y el problema de la parada. Una referencia en Booth atribuye el problema del castor ocupado a Rado. Booth también define el problema del castor ocupado de Rado en los "problemas básicos" 3, 4, 5 y 6 del Capítulo 9, pág. 396. El problema 3 consiste en "demostrar que el problema del castor ocupado es irresoluble... para todos los valores de n".
Ben-Amram, A. M.; Petersen, H. (2002). «Improved Bounds for Functions Related to Busy Beavers». Theory of Computing Systems 35: 1-11. S2CID 10429773. doi:10.1007/s00224-001-1052-0. «citeseerx: 10.1.1.136.5997».
Límites mejorados.
Lafitte, G.; Papazian, C. (mes de junio de 2007). «The fabric of small Turing machines». Computation and Logic in the Real World, Proceedings of the Third Conference on Computability in Europe. pp. 219-227. «citeseerx: 10.1.1.104.3021».
Este artículo contiene una clasificación completa de las máquinas de Turing de 2 estados y 3 símbolos, y por lo tanto, una demostración para el castor ocupado (2, 3): S(2, 3) = 9 y S(2, 3) = 38.
Boolos, George S.; Burgess, John P.; Jeffrey, Richard C. (2007). Computability and Logic (Fifth edición). Cambridge University Press. ISBN 978-0-521-87752-7.
Kropitz, Pavel (2010). Problém Busy Beaver (Tesis de Bachelor) (en eslovaco). Charles University in Prague.
Se describen las ideas, los algoritmos y su implementación, junto con la descripción de los experimentos que examinan las máquinas de Turing de 5 y 6 estados mediante ejecución paralela en una computadora de 31 núcleos y, finalmente, los mejores resultados para la máquina de Turing de 6 estados.

Enlaces externos

Wikiversity dispone de información sobre el castor trabajador

Página de Heiner Marxen, quien, junto con Jürgen Buntrock, encontró los registros mencionados para una máquina de Turing de 5 y 6 estados.
Estudio histórico de Pascal Michel sobre los resultados del desafío Busy Beaver, que incluye los mejores resultados y algunos análisis.
Definición de la clase RTM: Máquinas de Turing de Inversión, una subclase simple y robusta de las máquinas de Turing.
"El problema del castor ocupado: un nuevo ataque del milenio Archivado el 31 de marzo de 2025 en Wayback Machine." (archivado) en el Laboratorio RAIR de Rensselaer. Este trabajo halló varios registros nuevos y estableció varios valores para la formalización cuádruple.
El sitio web de Daniel Briggs archive y el foro para resolver el problema del castor ocupado de 5 estados y 2 símbolos, basado en la lista de máquinas no regulares Skelet (Georgi Georgiev).
Ligocki, Shawn (17 de julio de 2021). «Collatz-like behavior of Busy Beavers». sligocki (en inglés). Consultado el 12 de julio de 2022.
Aaronson, Scott (1999), «¿Quién puede nombrar el número más grande?»
Weisstein, Eric W. «Busy Beaver». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.
Máquinas de Turing del Castor Ocupado - Computerphile, YouTube
Pascal Michel. La competición del Castor Ocupado: un estudio histórico. 70 páginas. 2017. <hal-00396880v5>
OEIS sequence A060843 (Busy Beaver problem)
Busy Beaver Challenge Wiki page

Datos: Q1427965
Multimedia: Busy beavers / Q1427965

[Story_#_space-time-diagrams-1] 1 2 «Story # space-time-diagrams». The Busy Beaver Challenge (en inglés). Consultado el 9 de julio de 2024.

[:2-2] 1 2 3 4 5 Weisstein, Eric W. «Busy Beaver». Wolfram MathWorld. Archivado desde el original el 7 de diciembre de 2023. Consultado el 21 de noviembre de 2023.

[:4-3] 1 2 3 Brubaker, Ben (2 de julio de 2024). «Amateur Mathematicians Find Fifth 'Busy Beaver' Turing Machine». Quanta Magazine (en inglés). Consultado el 3 de julio de 2024.

[rado-4] 1 2 3 4 5 6 7 8 9 10 11 12 Radó, Tibor (mes de mayo de 1962). «On non-computable functions». Bell System Technical Journal 41 (3): 877-884. doi:10.1002/j.1538-7305.1962.tb00480.x. Archivado desde el original el 12 de octubre de 2021. Consultado el 7 de julio de 2022.

[:62-5] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Aaronson, Scott (29 de septiembre de 2020). «The Busy Beaver Frontier». SIGACT News 51 (3): 32-54. ISSN 0163-5700. doi:10.1145/3427361.3427369. Archivado desde el original el 5 de julio de 2022.

[:1-6] 1 2 3 4 5 6 7 8 Pavlus, John (10 de diciembre de 2020). «How the Slowest Computer Programs Illuminate Math's Fundamental Limits». Quanta Magazine (en inglés). Archivado desde el original el 10 de diciembre de 2020. Consultado el 11 de diciembre de 2020.

[yijun-7] 1 2 3 Leng, Yijun. «GitHub Repository 'goldbach_tm27'». GitHub.

[AaronsonJuly2023-8] 1 2 3 Aaronson, Scott (5 de julio de 2023). «Life, blogging, and the Busy Beaver function go on». Shtetl-Optimized. Archivado desde el original el 28 de agosto de 2023. Consultado el 27 de agosto de 2023.

[:3-9] 1 2 3 Riebel, Johannes (mes de marzo de 2023). The Undecidability of BB(748): Understanding Gödel's Incompleteness Theorems (Tesis de Bachelor's). Universidad de Augsburgo. Archivado desde el original el 17 de septiembre de 2024. Consultado el 24 de septiembre de 2024.

[:6-10] 1 2 3 4 5 6 7 Ben-Amram, A. M.; Julstrom, B. A.; Zwick, U. (1 de agosto de 1996). «A note on busy beavers and other creatures». Mathematical Systems Theory (en inglés) 29 (4): 375-386. ISSN 1433-0490. doi:10.1007/BF01192693.

[:5-11] 1 2 3 4 5 6 7 8 Aaronson, Scott (2 de julio de 2024). «BusyBeaver(5) is now known to be 47,176,870». Shtetl-Optimized (en inglés estadounidense). Consultado el 4 de julio de 2024.

[NDTM-12] 1 2 3 Wolfram, Stephen (4 de febrero de 2021). «Multiway Turing Machines». www.wolframphysics.org (en inglés). Archivado desde el original el 7 de julio de 2022. Consultado el 7 de julio de 2022.

[FOOTNOTEChaitin19872-13] Chaitin, 1987, p. 2.

[14] Boolos, Burgess & Jeffrey, 2007. "Computability and Logic"

[:10-15] 1 2 3 Lin, Shen; Rado, Tibor (mes de abril de 1965). «Computer studies of Turing machine problems». Journal of the ACM 12 (2): 196-212. S2CID 17789208. doi:10.1145/321264.321270.

[16] Yedidia, Adam; Aaronson, Scott (mes de mayo de 2016). «A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory». arXiv:1605.04343 [cs.FL].

[17] Aron, Jacob (11 de mayo de 2016). «This Turing machine should run forever unless maths is wrong». New Scientist (en inglés estadounidense). Archivado desde el original el 20 de octubre de 2016. Consultado el 25 de septiembre de 2016.

[:0-18] Version from May 3rd contained 7918 states: Aaronson, Scott (3 de mayo de 2016). «The 8000th Busy Beaver number eludes ZF set theory». Shtetl-Optimized. Archivado desde el original el 27 de septiembre de 2016. Consultado el 25 de septiembre de 2016.

[19] Friedman, Harvey M. (15 de enero de 2001). «Subtle cardinals and linear orderings». Annals of Pure and Applied Logic 107 (1): 1-34. ISSN 0168-0072. doi:10.1016/S0168-0072(00)00019-1.

[Aaronson3-20] 1 2 3 Aaronson, Scott (3 de mayo de 2016). «Three announcements». Shtetl-Optimized. Consultado el 27 de abril de 2018.

[21] «sorear/metamath-turing-machines: Metamath proof enumerators and other things». GitHub. 13 de febrero de 2019. Archivado desde el original el 17 de abril de 2021. Consultado el 19 de mayo de 2018.

[22] «Reversal Turing machine». skelet.ludost.net. Consultado el 10 de febrero de 2022.

[23] «A060843 - OEIS». oeis.org. Consultado el 19 de febrero de 2026.

[michel_comp-24] Pascal Michel's Busy Beaver Competitions Archivado el 6 de octubre de 2023 en Wayback Machine., página que enumera a los mejores contendientes conocidos.

[25] Michel, Pascal (14 de diciembre de 2015). «Problems in number theory from busy beaver competition». Logical Methods in Computer Science 11 (4): 10.

[FOOTNOTEChaitin19873-26] Chaitin, 1987, p. 3.

[j906-27] Bischoff, Manon (25 de julio de 2024). «Mathematicians Have Finally Found the Fifth 'Busiest Beaver'». Scientific American. Consultado el 10 de septiembre de 2025.

[28] Aaronson, Scott (28 de junio de 2025). «BusyBeaver(6) is really quite large». Shtetl-Optimized (en inglés estadounidense). Consultado el 16 de julio de 2025.

[29] Stérin, Tristan; Woods, Damien (2021). «Hardness of busy beaver value BB(15)». arXiv:2107.12475 [cs.LO].

[30] Erdös, Paul (1979). «Some unconventional problems in number theory». Mathematics Magazine 52 (2): 67-70. JSTOR 2689842. doi:10.1080/0025570X.1979.11976756. Archivado desde el original el 13 de junio de 2022. Consultado el 7 de julio de 2022.

[31] «Antihydra». BusyBeaverWiki (en inglés). Consultado el 18 de junio de 2025.

[ord-bounds-32] 1 2 Ord, Toby (2024). «Bounds on the rates of growth and convergence of all physical processes». arXiv:2410.10928 [physics.hist-ph].

[33] Karmela Padavic-Callaghan (1 de noviembre de 2024). «There may be a cosmic speed limit on how fast anything can grow». New Scientist.

[34] Brady, Allen H. (mes de marzo de 1998). «Heiner Marxen and Jürgen Buntrock. Attacking the busy beaver 5. Bulletin of the European Association for Theoretical Computer Science, no. 40 (Feb.1990), pp. 247–251. – Pascal Michel. Busy beaver competition and Collatz-like problems. Archive for mathematical logic, vol. 32 (1993), pp. 351–367». The Journal of Symbolic Logic (book review) (en inglés) 63 (1): 331-332. ISSN 0022-4812. JSTOR 2586607. doi:10.2307/2586607. Archivado desde el original el 5 de julio de 2024. Consultado el 5 de julio de 2024. Free HTML version by author Archivado el 9 de octubre de 2006 en Wayback Machine.

[:7-35] 1 2 3 4 Green, Milton W. (11 de noviembre de 1964). «A lower bound RADO's sigma function for binary turing machines». 1964 Proceedings of the Fifth Annual Symposium on Switching Circuit Theory and Logical Design. IEEE Computer Society. pp. 91-94. doi:10.1109/SWCT.1964.3.

[pascal.chronological-36] 1 2 3 4 5 6 7 8 Michel, Pascal. «Historical survey of Busy Beavers». Consultado el 24 de enero de 2026.

[:8-37] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Ben-Amram, A. M.; Petersen, H. (2002). «Improved bounds for functions related to busy beavers». Theory of Computing Systems 35 (1): 1-11. MR 1879169. doi:10.1007/s00224-001-1052-0.

[bb5-paper-38] 1 2 3 Blanchard, Justin; Briggs, Daniel; Deka, Konrad; Fenner, Nathan; Forster, Yannick; Georgiev, Georgi; House, Matthew L.; Hunter, Rachel et ál. (15 de septiembre de 2025). «Determination of the fifth Busy Beaver value». arXiv:2509.12337 [cs.LO].

[39] «0RB1LD_1LC1RB_1LD1RE_1LA1LE_1LZ0RC - BusyBeaverWiki». wiki.bbchallenge.org. Consultado el 17 de julio de 2026.

[40] «[July 2nd 2024] We have proved 'BB(5)= 47,176,870'». The Busy Beaver Challenge (en inglés). 2 de julio de 2024. Archivado desde el original el 2 de julio de 2024. Consultado el 2 de julio de 2024.

[41] Brubaker, Ben (2 de julio de 2024). «Amateur Mathematicians Find Fifth ‘Busy Beaver’ Turing Machine». Quanta Magazine (en inglés). Consultado el 4 de febrero de 2026.

[42] Shen Lin (1963). Computer studies of Turing machine problems (Tesis de Ph.D.). Universidad Estatal de Ohio.