Castor ocupado

Este artículo tiene varios problemas. Ayúdenos a mejorarlo o a discutir estos problemas en la página de discusión . ( Aprenda cómo y cuándo eliminar estos mensajes ) Este artículo puede ser demasiado técnico para que la mayoría de los lectores lo entiendan .Por favor, ayude a mejorarlo para que sea comprensible para los no expertos , sin eliminar los detalles técnicos. ( Octubre 2016 )( Aprenda cómo y cuándo eliminar este mensaje ) Este artículo tiene un estilo de citación poco claro . The references used may be made clearer with a different or consistent style of citation and footnoting. (July 2024) (Learn how and when to remove this message) (Learn how and when to remove this message)

En informática teórica , el juego del castor atareado tiene como objetivo encontrar un programa de terminación de un tamaño determinado que (dependiendo de la definición) produzca la mayor salida posible o se ejecute durante el mayor número de pasos. ^[2] Dado que es fácil concebir un programa que se repite sin fin y produce una salida infinita o se ejecuta durante un tiempo infinito, dichos programas se excluyen del juego. ^{[2] En lugar de los lenguajes de programación tradicionales, los programas utilizados en el juego son} máquinas de Turing de n estados , ^[2] uno de los primeros modelos matemáticos de computación. ^[3]

Las máquinas de Turing consisten en una cinta infinita y un conjunto finito de estados que sirven como "código fuente" del programa. Producir la mayor cantidad de salida se define como escribir la mayor cantidad de 1 en la cinta, también conocido como lograr la puntuación más alta, y funcionar durante el mayor tiempo se define como dar la mayor cantidad de pasos para detenerse. ^[4] El juego del castor atareado de n estados consiste en encontrar la máquina de Turing que funcione durante más tiempo o con la puntuación más alta que tenga n estados y finalmente se detenga. ^[2] Se supone que estas 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). ^[2] Un jugador debe concebir un conjunto de transiciones entre estados que apunten a la puntuación más alta o al tiempo de funcionamiento más largo mientras se asegura de que la máquina se detenga eventualmente.

Un castor atareado de n estados , BB- n o simplemente "castor atareado" es una máquina de Turing que gana el juego del castor atareado de n estados. ^[5] Dependiendo de la definición, alcanza la puntuación más alta o funciona durante el tiempo más largo, entre todas las otras posibles máquinas de Turing de n estados que compiten. Las funciones que determinan la puntuación más alta o el tiempo de funcionamiento más largo de los castores atareado de n estados según cada definición son Σ(n) y S(n) respectivamente. ^[4]

Decidir el tiempo de ejecución o la puntuación del n º castor atareado es incomputable . ^[4] De hecho, ambas funciones Σ(n) y S(n) eventualmente se vuelven más grandes que cualquier función computable. ^[4] Esto tiene implicaciones en la teoría de la computabilidad , el problema de la detención y la teoría de la complejidad . ^[6] El concepto fue introducido por primera vez por Tibor Radó en su artículo de 1962, "Sobre funciones no computables". ^[4] Uno de los aspectos más interesantes del juego del castor atareado es que, si fuera posible calcular las funciones Σ(n) y S(n) para todos los n , entonces esto resolvería todas las conjeturas matemáticas que pueden codificarse como "¿esta máquina de Turing se detiene o no?". ^[5] Por ejemplo, una máquina de Turing de 27 estados podría comprobar la conjetura de Goldbach para cada número y detenerse en un contraejemplo: si esta máquina no se hubiera detenido después de funcionar durante S(27) pasos, entonces debe funcionar para siempre, resolviendo la conjetura. ^[5] Muchos otros problemas, incluida la hipótesis de Riemann (744 estados) y la consistencia de la teoría de conjuntos ZF (745 estados ^{[7] [8]} ), se pueden expresar de una forma similar, donde como máximo se necesita comprobar un número infinito numerable de casos. ^[5]

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 miembro de las cuales debe cumplir con las siguientes especificaciones de diseño:

• La máquina tiene n estados "operativos" más un estado de Detención, donde n es un entero positivo y uno de los n estados se distingue como el estado de inicio. (Normalmente, los estados se etiquetan con 1, 2, ..., n , con el estado 1 como el estado de inicio, o con A , B , C , ..., con el estado A como el estado de inicio).
• La máquina utiliza una única cinta bidireccional infinita (o ilimitada).
• El alfabeto de la cinta es {0, 1}, donde 0 sirve como símbolo en blanco.
• La función de transición de la máquina toma dos entradas:

1. el estado actual de no-Detención,
2. el símbolo en la celda de la cinta actual,

y produce tres resultados:

1. un símbolo para escribir sobre el símbolo en la celda de la cinta actual (puede ser el mismo símbolo que el símbolo sobrescrito),
2. una dirección para moverse (izquierda o derecha; es decir, desplazarse a la celda de la cinta un lugar a la izquierda o derecha de la celda actual), y
3. un estado al que se debe realizar la transición (que puede ser el estado de Detención).

"Hacer funcionar" la máquina consiste en empezar en el estado inicial, con la celda de cinta actual siendo cualquier celda de una cinta en blanco (todos 0), y luego iterar la función de transición hasta que se ingrese al estado de Detención (si es que alguna vez se ingresa). Si, y solo si, la máquina finalmente se detiene, entonces la cantidad de 1 que finalmente quedan en la cinta se denomina puntaje de la máquina . Por lo tanto, el juego del castor ocupado de n estados (BB- n ) es una competencia, según la definición, para encontrar una máquina de Turing de n estados que tenga el mayor puntaje o tiempo de ejecución posible.

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, muévete un espacio hacia la derecha y pasa al estado 1
• En el estado 1, si el símbolo actual es 1, escriba un 0, muévase un espacio a la derecha y pase a HALT

Esta máquina de Turing se movería hacia la derecha, intercambiando el valor de todos los bits por los que pasa. Como la cinta inicial está formada por todos los ceros, formaría una cadena interminable de unos. Esta máquina no sería una contendiente incansable porque funciona eternamente en una cinta en blanco.

En su artículo original de 1962, Radó definió dos funciones relacionadas con el juego del castor atareado: la función de puntuación Σ(n) y la función de desplazamientos S(n). ^[4] Ambas toman un número de estados de la máquina de Turing y generan el máximo puntaje alcanzable por una máquina de Turing de ese número de estados mediante alguna medida. La función de puntuación Σ(n) da el número máximo de 1 que una máquina de Turing de un estado puede generar antes de detenerse, mientras que la función de desplazamientos S(n) da el número máximo de desplazamientos (o equivalentemente pasos, porque cada paso incluye un desplazamiento) que una máquina de Turing de un estado puede experimentar antes de detenerse. ^[4] Demostró que ambas funciones no eran computables , porque cada una crecía más rápido que cualquier función computable. ^[4] La función BB(n) se ha definido como cualquiera de estas funciones, ^{[ cita requerida ]} por lo que esa notación no se utiliza en este artículo.${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$

También se pueden definir otras funciones no computables a partir de la medición del rendimiento de las máquinas de Turing de otras maneras que no sean el tiempo o el número máximo de unos. ^[9] Por ejemplo: ^[9]

• La función se define como el número máximo de unos contiguos que una máquina de Turing que está parada puede escribir en una cinta en blanco. En otras palabras, este es el número unario más grande que una máquina de Turing de n estados puede escribir en una cinta.${\displaystyle {\text{num}}(n)}$
• La función se define como el número máximo de cuadrados de cinta que una máquina de Turing que se detiene puede leer (es decir, visitar) antes de detenerse. Esto incluye el cuadrado inicial, pero no un cuadrado al que la máquina solo llega después de la transición de detención (si la transición de detención está anotada con una dirección de movimiento), porque ese cuadrado no influye en el comportamiento de la máquina. Esta es la complejidad espacial máxima de una máquina de Turing de n estados.${\displaystyle {\text{space}}(n)}$

Estas cuatro funciones juntas se encuentran en la relación . ^[9] También se pueden definir más funciones operando el juego en diferentes máquinas de computación, como máquinas de Turing de 3 símbolos, ^[10] máquinas de Turing no deterministas, ^[11] el cálculo lambda (secuencia A333479 en la OEIS ) o incluso lenguajes de programación arbitrarios. ^[10]${\displaystyle {\text{num}}(n)\leq \Sigma (n)\leq {\text{space}}(n)\leq S(n)}$

La función de puntuación cuantifica la puntuación máxima que puede obtener un castor ocupado en una medida dada. Se trata de una función no computable , porque crece asintóticamente más rápido que cualquier función computable. ^[12]

La función de puntuación, , se define de modo que Σ( n ) sea la puntuación máxima alcanzable (el número máximo de 1 que finalmente hay en la cinta) entre todas las máquinas de Turing de n estados y 2 símbolos del tipo descrito anteriormente, cuando se inician en una cinta en blanco.${\displaystyle \Sigma :\mathbb {N} \to \mathbb {N} }$

Está claro que Σ es una función bien definida: para cada n , hay como máximo un número finito de máquinas de Turing de n estados como las mencionadas anteriormente, hasta el isomorfismo, y por lo tanto, como máximo un número finito de tiempos de ejecución posibles.

Según la definición basada en puntaje, cualquier máquina de Turing de 2 símbolos y n estados M para la cual σ ( M ) = Σ( n ) (es decir, que alcanza el puntaje máximo) se llama castor ocupado. Para cada n , existen al menos 4( n − 1)! castores ocupados de n estados. (Dado cualquier castor ocupado de n estados, otro se obtiene simplemente cambiando la dirección de cambio en una transición de detención, un tercero invirtiendo todas las direcciones de cambio de manera uniforme y un cuarto invirtiendo la dirección de detención del castor ocupado con todos los intercambios. Además, una permutación de todos los estados excepto Inicio y Detención produce una máquina que alcanza el mismo puntaje. Teóricamente, podría haber más de un tipo de transición que conduzca al estado de detención, pero en la práctica sería un desperdicio, porque solo hay una secuencia de transiciones de estado que producen el resultado buscado).

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. ^[4]${\displaystyle f:\mathbb {N} \to \mathbb {N} }$

Además, esto implica que es indecidible mediante un algoritmo general si una máquina de Turing arbitraria es un castor ocupado. (Un algoritmo de este tipo no puede existir, porque su existencia permitiría calcular Σ, lo cual es una imposibilidad demostrada. En particular, un algoritmo de este tipo podría usarse para construir otro algoritmo que calcularía Σ de la siguiente manera: para cualquier n dado , cada una de las finitas máquinas de Turing de 2 símbolos de n estados se probaría hasta que se encuentre un castor ocupado de n estados; esta máquina de castor ocupado se simularía entonces para determinar su puntuación, que es por definición Σ( n ).)

Aunque Σ( n ) es una función incomputable, hay algunos n pequeños para los cuales es posible obtener sus valores y demostrar que son correctos. No es difícil demostrar que Σ(0) = 0, Σ(1) = 1, Σ(2) = 4, y con progresivamente más dificultad se puede demostrar que Σ(3) = 6, Σ(4) = 13 y Σ(5) = 4098 (secuencia A028444 en la OEIS ). Σ( n ) aún no ha sido determinada para ninguna instancia de n > 5, aunque se han establecido límites inferiores (ver la sección Valores conocidos a continuación).

Una variante de la complejidad de Kolmogorov se define de la siguiente manera: ^[13] 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 1 consecutivos en una cinta inicialmente en blanco. La variante correspondiente del teorema de incompletitud de Chaitin 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 demostrar que ningún número específico tenga una complejidad mayor que k , y por lo tanto que no se puede demostrar ningún límite superior específico para Σ( k ) (esto último se debe a que "la complejidad de n es mayor que k " se demostraría si se demostrara n > Σ( k ) ). Como se menciona en la referencia citada, para cualquier sistema axiomático de "matemáticas ordinarias", el valor mínimo k para el que esto es cierto es mucho menor que 10⇈10 ; En consecuencia, en el contexto de las matemáticas ordinarias, no se puede demostrar ni el valor ni ningún límite superior de Σ(10⇈10). ( El primer teorema de incompletitud de Gödel se ilustra con este resultado: en un sistema axiomático de matemáticas ordinarias, hay una oración verdadera pero indemostrable de la forma Σ(10⇈10) = n , y hay infinitas oraciones verdaderas pero indemostrables de la forma Σ(10⇈10) < n .)

Además de la función Σ, Radó [1962] introdujo otra función extrema para las máquinas de Turing, la función de desplazamiento máximo , S , definida de la siguiente manera: ^[4]

• s ( M ) = el número de cambios que M realiza antes de detenerse, para cualquier M ∈ E _n ,
• S ( n ) = max{ s ( M ) | M ∈ E _n } = el mayor número de cambios realizados por cualquier máquina de Turing de 2 símbolos y n estados en detención.

Dado que se requiere que las máquinas de Turing normales tengan un desplazamiento en todas y cada una de las transiciones o "pasos" (incluida cualquier transición a un estado de detención), la función de desplazamientos máximos es al mismo tiempo una función de pasos máximos.

Radó demostró que S no es computable por la misma razón que Σ no es computable: 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, los que no habían sido sobrescritos en el momento en que la máquina de Turing se detuvo; en consecuencia, S crece al menos tan rápido como Σ, que ya se había demostrado que crece más rápido que cualquier función computable. ^[4]

La siguiente conexión entre Σ y S fue utilizada por Lin y Radó [ Computer Studies of Turing Machine Problems , 1965] para demostrar que Σ(3) = 6: Para un n dado , si se conoce S ( n ), entonces todas las máquinas de Turing de n estados pueden (en principio) funcionar hasta S ( n ) pasos, en cuyo punto 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 1 en la cinta (es decir, los castores atareados), uno 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, luego simular todas las máquinas de 3 estados esencialmente diferentes durante hasta 21 pasos. Analizando el comportamiento de las máquinas que no se habían detenido en 21 pasos, lograron demostrar que ninguna de esas máquinas se detendría jamás, probando así la conjetura de que S (3) = 21, y determinando que Σ(3) = 6 mediante el procedimiento recién descrito. ^[14]

En 2016, Adam Yedidia y Scott Aaronson obtuvieron el primer límite superior (explícito) del mínimo n para el cual S( n ) es indemostrable en ZFC . Para ello, construyeron una máquina de Turing de 7910 estados ^[15] cuyo comportamiento no puede demostrarse basándose en los axiomas habituales de la teoría de conjuntos ( teoría de conjuntos de Zermelo-Fraenkel con el axioma de elección ), bajo hipótesis de consistencia razonable ( propiedad estacionaria de Ramsey ). ^{[16] [17]} Stefan O'Rear luego la redujo a 1919 estados, con la dependencia de la propiedad estacionaria de Ramsey eliminada, ^{[18] [19]} y más tarde a 748 estados. ^[6] En julio de 2023, Riebel la redujo a 745 estados. ^{[7] [8]}

This section does not cite any sources. Please help improve this section by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Busy beaver" – news · newspapers · books · scholar · JSTOR (July 2024) (Learn how and when to remove this message)

Supongamos que S ( n ) es una función computable y que EvalS denote una TM, que evalúa S ( n ). Dada una cinta con n 1s, producirá S ( n ) 1s en la cinta y luego se detendrá. Sea Clean una máquina de Turing que limpia la secuencia de 1s inicialmente escritos en la cinta. Sea Double una máquina de Turing que evalúa la función n + n . Dada una cinta con n 1s, producirá 2 n 1s en la cinta y luego se detendrá. Creemos la composición 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 ₀ 1s 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. Comenzando con una cinta inicialmente en blanco, primero crea una secuencia de n ₀ 1s y luego la duplica, produciendo una secuencia de N 1s. Luego BadS producirá S ( N ) 1s en la cinta, y por último borrará todos los 1s y luego 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 que contradice la definición de la función S ( n ).

La incomputabilidad de Σ( n ) se puede demostrar de una manera similar. En la prueba anterior, se debe intercambiar la máquina EvalS por EvalΣ y Clean por Increment (una máquina de traducción simple), que busca un primer 0 en la cinta y lo reemplaza por un 1.

La incomputabilidad de S ( n ) también se puede establecer con referencia al problema de detención de la cinta en blanco. El problema de detención de la cinta en blanco es el problema de decidir para cualquier máquina de Turing si se detendrá o no cuando se inicie en una cinta vacía. El problema de detención de la cinta en blanco es equivalente al problema de detención estándar y, por lo tanto, también es incomputable. Si S ( n ) fuera computable, entonces podríamos resolver el problema de detención de la cinta en blanco simplemente ejecutando cualquier máquina de Turing dada con n estados durante S ( n ) pasos; si todavía no se ha detenido, nunca lo hará. Entonces, dado que el problema de detención de la cinta en blanco no es computable, se deduce que S ( n ) también debe ser incomputable.

Ambas funciones y son incomputables. ^[9] Esto se puede demostrar notando que en cada cuadrado de cinta en el que una máquina de Turing escribe un uno, también debe visitar: en otras palabras, . ^[9] Se puede demostrar que la función es incomputable probando, por ejemplo, que : 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 lo use para escribir al menos unos contiguos en la cinta. ^[9]${\displaystyle {\text{space}}(n)}$${\displaystyle {\text{num}}(n)}$${\displaystyle {\text{space}}(n)}$${\displaystyle \Sigma (n)\leq {\text{space}}(n)}$${\displaystyle {\text{num}}(n)}$${\displaystyle {\text{space}}(n)<{\text{num}}(3n+3)}$${\displaystyle {\text{space}}(n)}$

Los análogos de la función de desplazamiento se pueden definir de forma sencilla 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. ^[10] Por ejemplo, el juego del castor atareado también se puede generalizar a dos dimensiones utilizando máquinas de Turing en cintas bidimensionales, o a máquinas de Turing a las que se les permite permanecer en el mismo lugar y moverse a la izquierda y a la derecha. ^[10] Alternativamente, se puede definir una "función del castor atareado" para diversos modelos de computación con la complejidad de Kolmogorov . ^[10] Esto se hace tomando como el entero más grande tal que , donde es la longitud del programa más corto en que genera : es por lo tanto el entero más grande que un programa con una longitud o menos puede generar en . ^[10]${\displaystyle {BB}(n)}$${\displaystyle m}$${\displaystyle K_{L}(m)\leq n}$${\displaystyle K_{L}(m)}$${\displaystyle L}$${\displaystyle m}$${\displaystyle {BB}(n)}$${\displaystyle n}$${\displaystyle L}$

La máquina de 6 estados y 2 símbolos de mayor funcionamiento, que tiene la propiedad adicional de invertir el valor de la cinta en cada paso, produce6147 1s después47 339 970 pasos. ^{[ cita requerida ]} Entonces, para la clase de máquina de Turing de inversión (RTM), ^[20] S _RTM (6) ≥47 339 970 y Σ _RTM (6) ≥6147. De la misma manera, podríamos definir un análogo de la función Σ para máquinas de registros como el número más grande que puede estar presente en cualquier registro al detenerse, para un número dado de instrucciones. ^{[ cita requerida ]}

Una generalización simple es la extensión a máquinas de Turing con m símbolos en lugar de solo 2 (0 y 1). ^[10] Por ejemplo, una máquina de Turing trinaria 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 de castor atareado generalizadas :

1. Σ( n , m ): el mayor número de números distintos de cero que puede imprimir una máquina de n estados y m símbolos que comenzó en una cinta inicialmente en blanco antes de detenerse, ^{[ cita requerida ]} y
2. S ( n , m ): el mayor número de pasos dados por una máquina de n estados y m símbolos que comenzó en una cinta inicialmente en blanco antes de detenerse. ^[10]

Por ejemplo, la máquina de 3 estados y 3 símbolos de más larga duración encontrada hasta ahora funciona119 112 334 170 342 540 pasos antes de detenerse. ^{[21] [ se necesita una mejor fuente ]}

El problema se puede extender a las máquinas de Turing no deterministas buscando el sistema con la mayor cantidad de estados en todas las ramas o la rama con el mayor número de pasos. ^[11] La cuestión de si una NDTM dada se detendrá sigue siendo computacionalmente irreducible, y el cálculo requerido para encontrar una NDTM inquieta es significativamente mayor que 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 a la derecha muestra el número máximo de pasos antes de detenerse y el número máximo de estados únicos creados por la NDTM.

Además de plantear un juego matemático bastante desafiante , las funciones de castor atareado Σ(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 de manera sistemática dado el valor de S ( n ) para un n suficientemente grande . ^{[5] [22]} Teóricamente hablando, el valor de S(n) codifica la respuesta a todas las conjeturas matemáticas que pueden verificarse en tiempo infinito por una máquina de Turing con estados menores o iguales a n . ^[6]

Considere cualquier conjetura : cualquier conjetura que pueda ser refutada mediante un contraejemplo entre un número contable de casos (por ejemplo, la conjetura de Goldbach ). Escriba un programa de computadora que pruebe secuencialmente esta conjetura para valores crecientes. En el caso de la conjetura de Goldbach, consideraríamos cada número par ≥ 4 secuencialmente y probaríamos si es o no la suma de dos números primos. Supongamos que este programa se simula en una máquina de Turing de n estados. Si encuentra un contraejemplo (un número par ≥ 4 que no es la suma de dos primos en nuestro ejemplo), se detiene e indica eso. Sin embargo, si la conjetura es verdadera, entonces nuestro programa nunca se detendrá. (Este programa se detiene solo si encuentra un contraejemplo). ^[6]${\displaystyle \Pi _{1}^{0}}$

Ahora bien, este programa se simula mediante una máquina de Turing de n estados, de modo que si conocemos S ( n ) podemos decidir (en un tiempo finito) si se detendrá o no simplemente haciendo funcionar la máquina esa cantidad de pasos. Y si, después de S ( n ) pasos, la máquina no se detiene, sabemos que nunca lo hará y, por lo tanto, no hay contraejemplos para 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. ^[6] Por lo tanto, los 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. ^[6]

Sin embargo, los resultados actuales sobre el problema del castor atareado sugieren que esto no será práctico por dos razones: ^{[ cita requerida ]}

• Resulta extremadamente difícil demostrar valores para la función del castor atareado (y la función de desplazamiento máximo). Todos los valores exactos conocidos de S ( n ) se demostraron enumerando cada máquina de Turing de n estados y demostrando si cada una de ellas se detiene o no. Habría que calcular S ( n ) mediante algún método menos directo para que fuera realmente útil. ^{[ cita requerida ]}
• Los valores de S(n) y de las demás funciones del castor atareado se hacen muy grandes, muy rápidamente. Mientras que el valor de S(5) es de sólo alrededor de 47 millones, el valor de S(6) es más de 10⇈15, lo que equivale a una pila de 15 decenas. ^{[10] [ se necesita una mejor fuente ]} Este número tiene 10⇈14 dígitos y no es razonable usarlo en un cálculo. El valor de S(27), que es el número de pasos que el programa actual para la conjetura de Goldbach necesitaría ejecutarse para dar una respuesta concluyente, es incomprensiblemente grande y no es remotamente posible escribirlo, y mucho menos hacer funcionar una máquina para ello, en el universo observable. ^[5]${\displaystyle 10^{(10^{(10^{(10^{(\ldots )})})})}}$

Otra propiedad de S(n) es que ninguna teoría aritméticamente sólida y computablemente axiomatizada puede probar todos los valores de la función. Específicamente, dada una teoría computable y aritméticamente sólida , existe un número tal que para todo , ningún enunciado de la forma puede probarse en . ^[6] Esto implica que para cada teoría existe un valor máximo específico de S(n) que puede probar. Esto es cierto porque para cada uno de esos , se puede diseñar una máquina de Turing con estados para enumerar todas las posibles pruebas en . ^[6] Si la teoría es inconsistente, entonces todos los enunciados falsos son demostrables, y se le puede dar a la máquina de Turing la condición de detenerse si y solo si encuentra una prueba de, por ejemplo, . ^[6] Cualquier teoría que pruebe el valor de prueba su propia consistencia, violando el segundo teorema de incompletitud de Gödel . ^[6] Esto se puede usar para colocar varias teorías en una escala, por ejemplo los diversos axiomas cardinales grandes en ZFC : si a cada teoría se le asigna su número , las teorías con valores mayores de prueban la consistencia de las que están debajo de ellas, colocando todas esas teorías en una escala infinita contable. ^[6]${\displaystyle T}$${\displaystyle n_{T}}$${\displaystyle n\geq n_{T}}$${\displaystyle S(n)=k}$${\displaystyle T}$${\displaystyle T}$${\displaystyle n_{T}}$${\displaystyle T}$${\displaystyle 0=1}$${\displaystyle S(n_{T})}$${\displaystyle T}$${\displaystyle n_{T}}$${\displaystyle n_{T}}$

• Se ha construido una máquina de Turing binaria de 745 estados que se detiene si y solo si ZFC es inconsistente. ^{[7] [8]}

• Se ha construido una máquina de Turing de 744 estados que se detiene si, y sólo si, la hipótesis de Riemann es falsa. ^{[18] [5]}

• Se ha construido una máquina de Turing de 43 estados que se detiene si, y sólo si, la conjetura de Goldbach es falsa, y se ha propuesto una máquina de 27 estados para esa conjetura, pero aún no se ha verificado. ^{[18] [5]}

• Se ha construido una máquina de Turing de 15 estados que se detiene si y sólo si la siguiente conjetura formulada por Paul Erdős en 1979 es falsa: para todo n > 8 hay al menos un dígito 2 en la representación en base 3 de 2 ⁿ . ^{[23] [24]}

Al explorar la relación entre la universalidad computacional y el comportamiento dinámico de las máquinas de Turing de Busy Beaver , en 2012 se propuso una conjetura ^[25] que sugería que las máquinas de Busy Beaver eran candidatas naturales para la universalidad de Turing, ya que muestran características complejas, conocidas por (1) su máxima complejidad computacional dentro de restricciones de tamaño, (2) su capacidad para realizar cálculos no triviales antes de detenerse, y (3) la dificultad para encontrar y probar estas máquinas; estas características sugieren que las máquinas de Busy Beaver poseen la complejidad necesaria para la universalidad.

En 1964, Milton Green desarrolló un límite inferior para la variante de conteo de 1s de la función Busy Beaver 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 lo describieron como "un límite inferior no trivial (no recursivo primitivo)". ^[26] Este límite inferior se puede calcular, pero es demasiado complejo para expresarlo como una única expresión en términos de n . ^[27] Esto se hizo con un conjunto de máquinas de Turing, cada una de las cuales demostró el límite inferior para un cierto n . ^[27] Cuando n = 8, el método da

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

Por el contrario, el mejor límite inferior actual (a partir de 2024) de es , donde cada es la notación de flecha hacia arriba de Knuth . ^[10] Esto representa , una cadena exponencial de 15 decenas igual a . El valor de es probablemente mucho mayor aún que eso.${\displaystyle \Sigma (6)}$${\displaystyle 10\uparrow \uparrow 15}$${\displaystyle \uparrow }$${\displaystyle 10^{(10^{(10^{(10^{(\ldots )})})})}}$${\displaystyle 10^{10\uparrow \uparrow 14}}$${\displaystyle \Sigma (8)}$

Específicamente, el límite inferior se mostró con una serie de máquinas de Turing recursivas, cada una de las cuales estaba formada 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. ^[27] Al definir el valor del competidor de castor ocupado de N estados en una cinta que contiene unos como (la salida final de cada máquina es su valor en , porque una cinta en blanco tiene 0 unos), las relaciones de recursión son las siguientes: ^[27] a${\displaystyle m}$${\displaystyle B_{N}(m)}$${\displaystyle m=0}$

${\displaystyle B_{N}(0)=1}$

${\displaystyle B_{1}(m)=m+1}$

${\displaystyle B_{N}(m)=1+B_{N-2}(1+B_{N}(m-1))}$

Esto conduce a dos fórmulas, para números pares e impares, para calcular el límite inferior dado por la máquina N :${\displaystyle G(N)}$

${\displaystyle G(N)=B_{N-2}(B_{N-2}(1))}$para N impar

${\displaystyle G(N)=1+B_{N-3}(1+B_{N-3}(1))}$para N par

El límite inferior BB(N) también se puede relacionar con la función de Ackermann . Se puede demostrar que: ^[28]

${\displaystyle A(n,n)>G(4N+3)>A(4,2N+1)}$

Trivialmente, S(n) ≥ Σ(n) porque una máquina que escribe Σ(n) unos debe realizar al menos Σ(n) pasos para hacerlo. ^[28] Es posible dar un número de límites superiores en el tiempo S(n) con el número de unos Σ(n):

• ${\displaystyle S(n)\leq (n+1)\times \Sigma (5n)\times 2^{\Sigma (5n)}}$   (Rado ^[28] )
• ${\displaystyle S(n)\leq \Sigma (9n)}$   (Oficina ^[28] )
• ${\displaystyle S(n)\leq (2n-1)\times \Sigma (3n+3)}$   (Julstrom y Zwick ^[28] )

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 número unario más grande que puede generar), es posible demostrar: ^[28]

${\displaystyle {\text{num}}(n)<\Sigma (n)}$

${\displaystyle S(n)<{\text{num}}(n+o(n))}$

${\displaystyle S(n)<{\text{num}}(3n+6)}$   (Ben-Amram, et al., 1996 ^[9] )

Ben-Amram y Petersen, 2002, también dan un límite asintóticamente mejorado en S(n). Existe una constante c , tal que para todo n ≥ 2 : ^[28]

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

La siguiente tabla enumera los valores exactos y algunos límites inferiores conocidos para S ( n ), Σ( n ) y varias otras funciones de castor atareado. En esta tabla, se utilizan máquinas de Turing de 2 símbolos. Las entradas enumeradas como "?" son al menos tan grandes como otras entradas a la izquierda (porque todas las máquinas de n estados también son máquinas de estados (n+1)), y no más grandes que las entradas por encima de ellas (porque S(n) ≥ espacio(n) ≥ Σ(n) ≥ num(n)). Por lo tanto, se sabe que espacio(6) es mayor que 10⇈15, ya que espacio(n) ≥ Σ(n) y Σ(6) > 10⇈15.47 176 870 es un límite superior para el espacio(5), porque S(5) =47 176 870 ( ^[3] ) y S(n) ≥ espacio(n). 4098 es un límite superior para num(5), porque Σ(5) = 4098 ( ^[28] ) y Σ(n) ≥ num(n). La última entrada que aparece como "?" es num(6), porque Σ(6) > 10⇈15, pero Σ(n) ≥ num(n).

El castor atareado de cinco estados fue descubierto por Heiner Marxen y Jürgen Buntrock en 1989, pero recién resultó ser el quinto castor atareado ganador —estilizado como BB(5)— en 2024, utilizando una prueba en Coq . ^{[30] [31]}

Éstas son tablas de reglas para las 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 el límite inferior más conocido para Σ(6) y S (6).

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

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

Clave de resultado: (comienza en la posición subrayada y finaliza en la posición subrayada )

Castor ocupado de 1 estado y 2 símbolos

	A
0	1R H
1	(no utilizado)

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

Castor ocupado de dos estados y dos símbolos ^{[ cita requerida ]}

	A	B
0	1RB​	1L A
1	1 litro B	1R H

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

Castor ocupado de 3 estados y 2 símbolos ^{[32] [14]}

	A	B	do
0	1RB​	0RC​	1 litro
1	1R H	1RB​	1L A

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

A diferencia de las máquinas anteriores, ésta trabaja muy duro sólo para Σ, pero no para S. ( S (3) = 21.)

Castor ocupado de 4 estados y 2 símbolos

	A	B	do	D
0	1RB​	1L A	1R H	1R D
1	1 litro B	0 litros	1 litro de agua	0R A

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	do	D	mi
0	1RB​	1R C	1R D	1L A	1R H
1	1 litro	1RB​	0L E	1 litro de agua	0L A

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

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

actual contendiente al mejor de 6 estados y 2 símbolos ^{[21] [29]}

	A	B	do	D	mi	F
0	1RB​	1R C	1 litro	0L E	1 litro	0RC​
1	0L D	0R F	1L A	1R H	0RB​	0R E

Resultado: 1 0 1 1 1 ... 1 1 1 ("10" seguido de más de 10↑↑15 "1" contiguos en más de 10↑↑15 pasos, donde 10↑↑15=10 ^{10 . . 10} , una torre exponencial de 15 decenas).

En la siguiente tabla, las reglas para cada castor activo (maximización de Σ) se representan visualmente, con cuadrados naranjas que corresponden a un "1" en la cinta y blancos que corresponden 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, y el tiempo avanza de arriba hacia abajo. El estado de detención se representa mediante una regla que asigna un estado a sí mismo (la cabeza no se mueve).

• El número del Rayo
• Turmita

Wikiversidad organiza un concurso sobre el castor incansable

• La página de Heiner Marxen, quien, junto con Jürgen Buntrock, encontró los registros mencionados anteriormente para una máquina de Turing de 5 y 6 estados.
• Estudio histórico de los resultados del castor ocupado de Pascal Michel que también contiene los mejores resultados y algunos análisis.
• Definición de la clase RTM – Máquinas de Turing Inversas, subclase simple y fuerte de las MT.
• "El problema del castor atareado: un ataque del nuevo milenio" (archivado) en el Laboratorio RAIR de Rensselaer. Este esfuerzo encontró varios récords nuevos y estableció varios valores para la formalización cuádruple.
• Archivo del sitio web y foro de Daniel Briggs para resolver el problema del castor ocupado de 5 estados y 2 símbolos, basado en la lista de máquinas no regulares de Skelet (Georgi Georgiev).
• Ligocki, Shawn (17 de julio de 2021). "Comportamiento de los castores ajetreados similar al de Collatz". sligocki . Consultado el 12 de julio de 2022 .
• Aaronson, Scott (1999), ¿Quién puede nombrar el número mayor?
• Weisstein, Eric W. "Castor inquieto". MathWorld .
• Máquinas de Turing de Busy Beaver - Computerphile, Youtube
• Pascal Michel. La competencia del castor atareado: un estudio histórico. 70 páginas. 2017. <hal-00396880v5>