Castor ocupado

En informática teórica, el juego del castor ocupado tiene como objetivo encontrar un programa de terminación de un tamaño determinado que produzca el mayor rendimiento posible. Dado que es fácil concebir un programa en bucle sin fin que produce una salida infinita, dichos programas se excluyen del juego.

Más precisamente, el juego del castor ocupado consiste en diseñar una máquina de Turing que se detiene con el alfabeto {0,1} que escribe la mayor cantidad de 1 en la cinta, usando solo un conjunto dado de estados. Las reglas para el juego de 2 estados son las siguientes:

1. la máquina debe tener dos estados además del estado de suspensión, y
2. la cinta inicialmente contiene sólo 0s.

Un jugador debe concebir una tabla de transición que apunte a la salida más larga de 1s en la cinta mientras se asegura de que la máquina se detenga eventualmente.

Un nésimo castor ocupado, BB-n o simplemente "castor ocupado" es una máquina de Turing que gana el juego Busy Beaver de estado n. Es decir, alcanza el mayor número de 1 entre todas las demás Máquinas de Turing competidoras de n-estado posibles. La máquina de Turing BB-2, por ejemplo, logra cuatro 1 en seis pasos.

Determinar si una máquina de Turing arbitraria es un castor ocupado es indecidible. Esto tiene implicaciones en la teoría de la computabilidad, el problema de la detención y la teoría de la complejidad. El concepto fue introducido por primera vez por Tibor Radó en su artículo de 1962, "Sobre funciones no computables".

El juego

El njuego del castor ocupado (o BB-n game), introducido en Tibor Radó& El documento de 1962 de #39 involucra una clase de máquinas de Turing, cada miembro de la cual debe cumplir con las siguientes especificaciones de diseño:

• La máquina tiene n estados "operacionales" más un estado Halt, donde n es un entero positivo, y uno de los n estados se distingue como el estado de partida. (Típicamente, los estados están etiquetados por 1, 2,..., n, con el estado 1 como estado inicial, o por A, B, C,... con estado A como estado de partida.)
• La máquina utiliza una sola cinta infinita de dos vías (o sin límites).
• El alfabeto de cinta es {0, 1}, con 0 sirviendo como el símbolo en blanco.
• La máquina función de transición toma dos entradas:

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

y produce tres productos:

1. un símbolo para escribir sobre el símbolo en la celda actual (puede ser el mismo símbolo que el símbolo sobrescrito),
2. una dirección para moverse (izquierda o derecha; es decir, cambiar a la celda de cinta un lugar a la izquierda o derecha de la célula actual), y
3. un estado para la transición hacia (que puede ser el estado de Halt).

Hay así (4)n + 4)²ⁿ n-state Turing máquinas que cumplen esta definición porque la forma general de la fórmula es (símbolos × direcciones ×estados + 1))^{()símbolos × estados)}.

La función de transición puede ser vista como una tabla finita de 5-tuples, cada una de las formas

(estado actual, símbolo actual, símbolo para escribir, dirección de cambio, siguiente estado).

"Correr" la máquina consiste en comenzar en el estado de inicio, siendo la celda de cinta actual cualquier celda de una cinta en blanco (todo 0), y luego iterar la función de transición hasta que se ingresa al estado Halt (si es que alguna vez ocurre). Si, y solo si, la máquina finalmente se detiene, entonces el número de 1 que quedan finalmente en la cinta se denomina puntuación de la máquina.

El juego del castor ocupado de estado n (BB-n) es un concurso para encontrar una máquina de Turing de estado n que tenga la mayor puntaje posible: el mayor número de 1 en su cinta después de detenerse. Una máquina que obtiene la puntuación más alta posible entre todas las máquinas de Turing de estado n se denomina castor ocupado de estado n, y una máquina cuya puntuación es simplemente la más alta obtenida hasta ahora (quizás no el más grande posible) se denomina máquina de estado campeón n.

Radó exigió que cada máquina que participara en el concurso fuera acompañada de una declaración del número exacto de pasos que se necesitan para alcanzar el estado Halt, lo que permite verificar (en principio) la puntuación de cada entrada haciendo funcionar la máquina durante el número indicado de pasos. (Si las entradas fueran a consistir solo en descripciones de máquinas, entonces el problema de verificar cada entrada potencial es indecidible, porque es equivalente al conocido problema de detención: no habría una forma efectiva de decidir si una máquina arbitraria finalmente se detiene).

Funciones relacionadas

La función del castor ocupado Σ

La función Castor ocupado cuantifica la puntuación máxima que puede obtener un Castor ocupado en una medida determinada. Esta es una función no computable. Además, se puede demostrar que una función castor ocupada crece asintóticamente más rápido que cualquier función computable.

La función de castor ocupada, ${displaystyle Sigma:mathbb {N} to mathbb {N}$, se define de modo que lan) es la puntuación máxima alcanzable (el número máximo de 1s finalmente en la cinta) entre todos detener 2-symbol n-state Turing machines del tipo descrito anteriormente, cuando comenzó en una cinta en blanco.

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 estado n como arriba, hasta el isomorfismo, por lo tanto, como mucho, un número finito de tiempos de ejecución posibles.

Esta secuencia infinita Σ es la función de castor ocupado, y cualquier máquina de Turing de 2 símbolos de estado n M para el cual σ(M) = Σ(n) (es decir, que alcanza la máxima puntuación) se denomina ocupado castor. Tenga en cuenta que para cada n, existen al menos cuatro castores ocupados en estado n (porque, dado cualquier castor ocupado en estado n, otro es obtenida simplemente cambiando la dirección de cambio en una transición de parada, otra cambiando todos los cambios de dirección a su opuesto, y la final cambiando la dirección de parada del castor ocupado que ha cambiado por completo).

No computabilidad

El periódico de Radó en 1962 demostró que si ${displaystyle f:mathbb {N} to mathbb {N}$ es cualquier función computable, entonces la (n) f()n) para todo lo suficientemente grande n, y por lo tanto, la CEP no es una función computable.

Además, esto implica que es indecidible mediante un algoritmo general si una máquina de Turing arbitraria es un castor ocupado. (Tal algoritmo no puede existir, porque su existencia permitiría calcular Σ, lo cual es una imposibilidad comprobada. En particular, tal algoritmo podría usarse para construir otro algoritmo que calcularía Σ de la siguiente manera: para cualquier n dado , cada una de las máquinas de Turing de 2 símbolos con estado n finito se probaría hasta que se encuentre un castor ocupado de estado n; esta máquina castor ocupada luego ser simulado para determinar su puntuación, que es por definición Σ(n).)

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

En 2016, Adam Yedidia y Scott Aaronson obtuvieron el primer límite superior (explícito) en el n mínimo para el cual Σ(n) no es demostrable en ZFC. Para ello construyeron una máquina de Turing de 7910 estados cuyo comportamiento no puede demostrarse en base a 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). Esto se redujo más tarde a 1919 estados, con la eliminación de la dependencia de la propiedad estacionaria de Ramsey, y luego a 748 estados.

Complejidad e indemostrabilidad de Σ

Una variante de la complejidad de Kolmogorov se define de la siguiente manera [cf. Boolos, Burgess &erio; Jeffrey, 2007]: La complejidad de un número n es el menor número 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 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 complejidad. mayor que k y, por lo tanto, no se puede demostrar un límite superior específico para Σ(k) (este último se debe a que "la complejidad de n< /i> es mayor que k" se probaría si "n > Σ(k)" fueron probados). Como se menciona en la referencia citada, para cualquier sistema axiomático de "matemáticas ordinarias" el valor mínimo k para el cual esto es cierto es mucho menor que 10↑↑10; en consecuencia, en el contexto de las matemáticas ordinarias, no se puede probar 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 no demostrable de la forma "Σ(10 ↑↑ 10) = n", y hay infinitas oraciones verdaderas pero no demostrables de la forma "Σ(10 ↑↑ 10) < n".)

Función de turnos máximos S

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

• s()M) = el número de turnos M hace antes de detener, para cualquier M ▪ E_n,
• S()n= max{s()MSilencio M ▪ E_n} = el mayor número de turnos realizados por cualquier suspensión n- estado 2-símbolo Máquina de Turing.

Debido a que se requiere que estas máquinas de Turing tengan un cambio en todas y cada una de las transiciones o "pasos" (incluyendo cualquier transición a un estado de Detención), la función max-shifts es al mismo tiempo una función max-steps.

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. Demostró esto simplemente observando que para cada n, S(n) ≥ Σ(n). Cada turno puede escribir un 0 o un 1 en la cinta, mientras que Σ cuenta un subconjunto de los turnos que escribieron un 1, es decir, los que no habían sido sobrescritos cuando la máquina de Turing se detuvo; en consecuencia, S crece al menos tan rápido como Σ, que ya se ha demostrado que crece más rápido que cualquier función computable.

La siguiente conexión entre Σ y S fue utilizada por Lin & Radó [Computer Studies of Turing Machine Problems, 1965] para demostrar que Σ(3) = 6: Para un n dado, si S(n), entonces todas las máquinas de Turing de estado n pueden funcionar (en principio) 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 ocupados), uno obtiene de sus cintas el valor de Σ(n). El enfoque utilizado por Lin & Radó para el caso de n = 3 fue conjeturar que S(3) = 21, luego simular todas las máquinas de 3 estados esencialmente diferentes para hasta 21 pasos. Al analizar el comportamiento de las máquinas que no se detuvieron en 21 pasos, lograron demostrar que ninguna de esas máquinas se detendría nunca, probando así la conjetura de que S(3) = 21 y determinando que Σ(3) = 6 por el procedimiento recién descrito.

Las desigualdades que relacionan Σ y S incluyen las siguientes (de [Ben-Amram, et al., 1996]), que son válidas para todos los n ≥ 1:

${displaystyle {begin{aligned}S(n) limitgeqSigma (n)S(n) limitleq (2n-1)Sigma (3n+3)S(n) correspondíaSigma (3n+6);end{aligned}}}}$

y un límite asintóticamente mejorado (de [Ben-Amram, Petersen, 2002]): existe una constante c, tal que para todo n ≥ 2,

${displaystyle S(n)leq Sigma left(n+leftlceil {frac {8n}{log _{2}n}rightrceil +cright). }$

${displaystyle S(n)}$ tiende a estar cerca de la plaza de ${displaystyle Sigma (n)}$, y de hecho muchas máquinas dan ${displaystyle S(n)}$ menos que ${displaystyle Sigma ^{2}(n)}$.

Valores conocidos para Σ y S

A partir de 2016, los valores de función para Σ(n) y S(n) solo se conocen exactamente para n< /i> < 5.

El actual (a partir de 2018) campeón del castor ocupado de 5 estados produce 4098 1s, usando 47176870 pasos (descubiertos por Heiner Marxen y Jürgen Buntrock en 1989), pero quedan 18 o 19 (posiblemente menos de 10, ver más abajo) máquinas con comportamiento que se cree que nunca se detiene, pero que no se ha demostrado que se ejecute infinitamente. Skelet enumera 42 o 43 máquinas no probadas, pero 24 ya están probadas. Las máquinas restantes han sido simuladas a 81.800 millones de pasos, pero ninguna se detuvo. Daniel Briggs también probó algunas máquinas. Otra fuente dice que 98 máquinas siguen sin probarse. Hay un análisis de los holdouts. Por lo tanto, es probable que Σ(5) = 4098 y S(5) = 47176870, pero esto sigue sin probarse y se desconoce si quedan reservas (a partir de 2018). En este momento, el campeón récord de 6 estados produce más de 3.5147495×10¹⁸²⁶⁷ 1s (exactamente (25×4³⁰³⁴¹+23)/9), utilizando más de 7.412×10³⁶⁵³⁴ pasos (encontrado por Pavel Kropitz en 2010). Como se señaló anteriormente, estas son máquinas de Turing de 2 símbolos.

Una simple extensión de la máquina de 6 estados conduce a una máquina de 7 estados que escribirá más de 10^{10101018705353} 1 en la cinta, pero sin duda hay máquinas de 7 estados mucho más ocupadas. Sin embargo, otros cazadores de castores ocupados tienen diferentes juegos de máquinas.

Milton Green, en su artículo de 1964 "A Lower Bound on Rado's Sigma Function for Binary Turing Machines", construyó un conjunto de máquinas de Turing demostrando que

${displaystyle Sigma (2k)]mbox{for }kgeq 2,}$

donde ↑ es la notación de flecha hacia arriba de Knuth y A es la función de Ackermann.

Así

${displaystyle Sigma (10)}=3uparrow uparrow 3=3uparrow uparrow 3^{3^{3}}=3^{3^{3^{.^{.^{}}}}}}}}}}$

(con 3³³ = 7< span style="margen-izquierda:.25em;">625597484987 términos en la torre exponencial), y

${displaystyle Sigma (12) Confía3uparrow uparrow uparrow 3=g_{1},}$

donde el número g1 es el enorme valor inicial en la secuencia que define el número de Graham.

En 1964, Milton Green desarrolló un límite inferior para 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)". Este límite inferior se puede calcular, pero es demasiado complejo para establecerlo como una sola expresión en términos de n. Cuando n=8 el método da Σ(8) ≥ 3 × (7 × 3⁹² - 1) / 2 ≈ 8,248×10⁴⁴.

Se puede derivar de los límites inferiores actuales que:

${displaystyle Sigma (2k+1) confianza3uparrow ^{k-2}31 propiedadesA(k-2,k-2)qquad {mbox{for }kgeq 2,}$

Por el contrario, el mejor límite inferior actual (a partir de 2018) en Σ(6) es 10¹⁸²⁶⁷, que es mayor que el límite inferior dado por la fórmula de Green, 3 ³ = 27 (que es diminuto en comparación). De hecho, es mucho mayor que el límite inferior: 3 ↑↑ 3 = 3³³ = 7625597< span style="margin-left:.25em;">484987, que es el primero de Green límite inferior para Σ(8), y también mucho mayor que el segundo límite inferior: 3×(7×3⁹²−1)/2.

Σ(7) es mucho, mucho mayor que el límite inferior común actual 3³¹ (casi 618 billones), por lo que el segundo límite inferior también es muy, muy débil.

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

Suponga que S(n) es una función computable y permita que EvalS denote una TM, evaluando S (n). Dada una cinta con n 1, producirá S(n) 1 en la cinta y luego se detendrá. Sea Limpiar una máquina de Turing que limpia la secuencia de 1 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 1s, producirá 2n 1s en la cinta y luego se detendrá. Creamos la composición Doble | Evaluaciones | Limpie y deje que n₀ sea el número de estados de esta máquina. Sea Create_n₀ una máquina de Turing que crea n₀ 1 en una cinta inicialmente en blanco. Esta máquina puede construirse de manera trivial para tener n₀ estados (el estado i escribe 1, mueve la cabeza 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₀ | Doble | Evaluaciones | Limpiar. Observe que esta máquina tiene estados N. Comenzando con una cinta inicialmente en blanco, primero crea una secuencia de n₀ 1 y luego la duplica, produciendo una secuencia de N 1. Luego, BadS producirá S(N) 1 en la cinta y, por último, borrará todos los 1 y luego se detendrá. Pero la fase de limpieza continuará al menos S(N) pasos, por lo que el tiempo de trabajo de BadS es estrictamente mayor que S(N), lo que contradice la definición de la función S(n).

La incomputabilidad de Σ(n) puede probarse de manera similar. En la prueba anterior, uno debe intercambiar la máquina EvalS con EvalΣ y Clean con Increment — un simple TM, buscando un primer 0 en la cinta y reemplazándolo con 1.

La incomputabilidad de S(n) también se puede establecer por referencia al problema de detención de la cinta en blanco. El problema de la 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, tampoco es computable. Si S(n) fuera computable, entonces podríamos resolver el problema de detener la cinta en blanco simplemente ejecutando cualquier máquina de Turing dada con n estados para < i>S(n) pasos; si todavía no se ha detenido, nunca lo hará. Entonces, dado que el problema de detener la cinta en blanco no es computable, se deduce que S(n) tampoco debe ser computable.

Generalizaciones

Para cualquier modelo de computación existen análogos simples del castor ocupado. Por ejemplo, la generalización a las máquinas de Turing con estados n y símbolos m define las siguientes funciones generalizadas de castor ocupado:

1. .n, m): el mayor número de no zareros imprimibles por un n- Estado, m- la máquina del simbolo comenzó en una cinta inicialmente en blanco antes de detenerse, y
2. S()n, m): el mayor número de medidas adoptadas por un n- Estado, m- la máquina del simbolo comenzó en una cinta inicialmente en blanco antes de detenerse.

Por ejemplo, la máquina de 3 símbolos y 3 estados de más larga duración encontrada hasta ahora ejecuta 119112334170 342540 pasos antes de detenerse. La máquina de 6 estados y 2 símbolos de más larga duración que tiene la propiedad adicional de invertir el valor de la cinta en cada paso produce 6147 1s después de 47339970 pasos. Entonces, para la clase Reversal Turing Machine (RTM), S_RTM(6) ≥ 47339970 y Σ_RTM(6) ≥ 6147.

Es posible generalizar aún más la función del castor ocupado extendiéndola a más de una dimensión.

Del mismo modo, podríamos definir un análogo a la función Σ para máquinas de registro como el número más grande que puede estar presente en cualquier registro al detenerse, para un número dado de instrucciones.

Valores exactos y límites inferiores

La siguiente tabla enumera los valores exactos y algunos límites inferiores conocidos para S(n, m) y Σ(n , m) para los problemas generalizados del castor ocupado. Nota: las entradas enumeradas como "?" están delimitados desde abajo por el máximo de todas las entradas a la izquierda y arriba. Estas máquinas no han sido investigadas o fueron superadas posteriormente por una máquina más pequeña.

Las máquinas de Turing que alcanzan estos valores están disponibles en la página web de Pascal Michel. Este sitio web también contiene algunos análisis de las máquinas de Turing y referencias a las pruebas de los valores exactos.

Valores de S(n, m)
n m	2-estado	3 estados	4-estado	5-state	6 estados
2-símbolo	6	21	107	47176870?	■ 10 ${displaystyle uparrow uparrow }$ 15
3-símbolo	38	≥ 119112334170342540	■ 1.0×1014072	?	?
4-símbolo	≥ 3932964	■ 5.2×1013036	?	?	?
5-symbol	■ 1.9×10704	?	?	?	?
6-symbol	■ 2.4×109866	?	?	?	?
Valores de lan, m)
n m	2-estado	3 estados	4-estado	5-state	6 estados
2-símbolo	4	6	13	4098?	■ 10 ${displaystyle uparrow uparrow }$ 15
3-símbolo	9	≥ 374676383	■ 1.3×107036	?	?
4-símbolo	≥ 2050	■ 3.7×106518	?	?	?
5-symbol	■ 1.7×10352	?	?	?	?
6-symbol	■ 1.9×104933	?	?	?	?

Máquinas de Turing no deterministas

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 la mayor cantidad de pasos. La cuestión de si un NDTM determinado se detendrá sigue siendo computacionalmente irreducible, y el cálculo requerido para encontrar un castor ocupado de NDTM 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 casos o reglas p, la tabla de la derecha proporciona el número máximo de pasos antes de detenerse y el número máximo de estados únicos creados por el NDTM.

Aplicaciones

Además de plantear un juego matemático bastante desafiante, las funciones del castor ocupado 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 .

Considere cualquier conjetura que pueda ser refutada a través de 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 secuencialmente todo número par ≥ 4 y probaríamos si es o no la suma de dos números primos. Suponga que este programa se simula en una máquina de Turing de estado n. Si encuentra un contraejemplo (un número par ≥ 4 que no es la suma de dos números primos en nuestro ejemplo), se detiene y lo indica. Sin embargo, si la conjetura es cierta, nuestro programa nunca se detendrá. (Este programa se detiene solo si encuentra un contraejemplo).

Ahora, este programa es simulado por una máquina de Turing de estado n, así que si conocemos S(n) podemos decidir (en una cantidad finita de tiempo) si alguna vez se detendrá o no simplemente haciendo funcionar la máquina tantos pasos. Y si, después de S(n) pasos, la máquina no se detiene, sabemos que nunca lo hará y, por lo tanto, que 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 cierta.

Por lo tanto, los valores específicos (o límites superiores) para S(n) podrían usarse para resolver sistemáticamente muchos problemas abiertos en matemáticas (en teoría). 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 probar valores para la función de castor ocupado (y la función de cambio máximo). Sólo se ha probado para máquinas extremadamente pequeñas con menos de cinco estados, mientras que uno presumiblemente necesita al menos 20-50 estados para hacer una máquina útil. Además, todo valor exacto conocido S()n) fue probado por enumerar cada n-state Turing machine y probar si cada parada o no. Uno tendría que calcular S()n) por un método menos directo para que realmente sea útil.
• Pero incluso si uno encontró una mejor manera de calcular S()n), los valores de la función de castor ocupado (y la función de cambio máx) se hacen muy grandes, muy rápido. S(6) 10³⁶⁵³⁴ ya requiere una aceleración especial basada en patrones para poder simular hasta la terminación. Asimismo, sabemos que S(10) не нна(10) не 3 ↑↑↑ 3 es un número gigantesco y S(17) √≠ Èn(17) G G, donde G es el número de Graham - un número enorme. Así, aunque supiéramos, digamos: S(30), es completamente irrazonable ejecutar cualquier máquina que número de pasos. No hay suficiente capacidad computacional en la parte conocida del universo para haber realizado incluso S(6) operaciones directamente.

Instancias notables

Se ha construido una máquina de Turing binaria de 748 estados que se detiene si ZFC es inconsistente. Se ha construido una máquina de Turing de 744 estados que se detiene si la hipótesis de Riemann es falsa. Se ha construido una máquina de Turing de 43 estados que detiene 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.

Se ha construido una máquina de Turing de 15 estados que se detiene si y solo 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 de base 3 de 2ⁿ.

Ejemplos

Muestra los primeros 100.000 pasos de la actual mejor castor ocupado de 5 estados. Orange es "1", blanco es "0" (imagen comprimido verticalmente).

Estas 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), y el límite inferior más conocido para Σ(5) y S(5), y Σ(6) y S(6). Para otras visualizaciones,

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 para escribir en la cinta, la dirección para moverse 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 0. Por lo tanto, el símbolo inicial que se lee de la cinta es un 0.

Clave de resultado: (comienza en la posición overlined, se detiene en la posición subrayado)

1-estado, 2-símbolo ocupado beaver

	A
0	1RH
1	(no utilizado)

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

2-estado, 2-símbolo ocupado beaver

	A	B
0	1RB	1LA
1	1LB	1RH

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

Animación de un castor ocupado de 3 estados, 2 símbolos

3-estado, 2-símbolo ocupado beaver

	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"s en total).

A diferencia de las máquinas anteriores, esta es un castor ocupado solo para Σ, pero no para S. (S(3) = 21.)

Animación de un castor ocupado de 4 estados, 2 símbolos

4-estado, 2-símbolo ocupado beaver

	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"s en total)

actual 5-estado, 2-symbol mejor contender (posible beaver ocupado)

	A	B	C	D	E
0	1RB	1RC	1RD	1LA	1RH
1	1LC	1RB	0LE	1LD	0LA

Resultado: 4098 "1"s con 8191 "0"s intercalados en 47 176 870 pasos.

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

actual 6-estado, 2-symbol mejor contender

	A	B	C	D	E	F
0	1RB	1RC	1LC	0LE	1LF	0RC
1	0LD	0RF	1LA	1RH	0RB	0RE

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

Visualizaciones

En la siguiente tabla, las reglas para cada castor ocupado (maximizando Σ) se representan visualmente, con cuadrados naranjas que corresponden a un "1" en la cinta, y el blanco correspondiente a "0". La posición de la cabeza está indicada por el ovoide negro, y la orientación de la cabeza representa el estado. Las cintas individuales se disponen horizontalmente, con el tiempo progresando de arriba a abajo. El estado de parada está representado por una regla que asigna un estado a sí mismo (la cabeza no se mueve).

Evolution of Busy Beavers with 1-4 States

Reglas para un castor ocupado.

Reglas para castor ocupado de 2 estados.

Reglas para castor ocupado de 3 estados.

Reglas para castor ocupado de 4 estados.

Evolución de un castor ocupado hasta que se detenga. El estado inicial detiene, con un solo "1" escrito antes de la terminación.

Evolución de castor ocupado de 2 estados hasta detenerse.

Evolución de castor ocupado de 3 estados hasta que se detenga.

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