Castor ocupado - Busy beaver

En la informática teórica , el atareado juego del castor tiene como objetivo encontrar un programa final de un tamaño determinado que produzca el mayor rendimiento posible. Dado que un programa en bucle sin fin que produce una salida infinita se concibe fácilmente, tales programas se excluyen del juego.

Más precisamente, el ajetreado juego del castor consiste en diseñar una máquina de Turing de alfabeto binario que se detiene y que escribe la mayor cantidad de 1 en la cinta, utilizando solo un conjunto determinado 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 detención, y
2. la cinta contiene inicialmente sólo ceros.

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

Un n º castor ocupado , BB- n o simplemente "castor ocupado" es una máquina de Turing que gana el n -state Busy Beaver juego. Es decir, alcanza la mayor cantidad de 1 entre todas las demás Máquinas de Turing posibles que compiten en n estados. La máquina BB-2 Turing , 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, "On Non-Computable Functions".

El juego

El n -state ocupada juego de castor (o BB- n juego ), introducido en Tibor Radó 1962 de papel 's, implica una clase de máquinas de Turing , cada miembro de que se requiere para 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 número entero positivo, y uno de los n estados se distingue como el estado inicial. (Normalmente, los estados se etiquetan con 1, 2, ..., n , con el estado 1 como estado inicial, o con A , B , C , ..., con el estado A como estado inicial).
• La máquina utiliza una única cinta bidireccional infinita (o ilimitada).
• El alfabeto de la cinta es {0, 1}, con 0 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 cinta actual,

y produce tres salidas:

1. un símbolo para escribir sobre el símbolo en la celda de cinta actual (puede ser el mismo símbolo que el símbolo sobreescrito),
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 celda actual), y
3. un estado al que pasar (que puede ser el estado de detención).

Por tanto, hay (4 n + 4) ^{2 n} máquinas de Turing de n estados 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 verse como una tabla finita de 5 tuplas, cada una de las cuales tiene la forma

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

"Ejecutar" la máquina consiste en comenzar en el estado inicial, con la celda de cinta actual siendo cualquier celda de una cinta en blanco (todo-0), y luego iterar la función de transición hasta que se ingrese al estado de detención (si alguna vez). Si, y solo si, la máquina finalmente se detiene, entonces el número de unos que quedan finalmente en la cinta se denomina puntuación de la máquina .

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

Radó requirió que cada máquina inscrita en el concurso vaya acompañada de una declaración del número exacto de pasos que se necesitan para alcanzar el estado de parada, lo que permite verificar la puntuación de cada entrada (en principio) haciendo funcionar la máquina para el número indicado. de pasos. (Si las entradas consistieran 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 de castor ocupado cuantifica la puntuación máxima que puede alcanzar un castor ocupado en una medida determinada. Esta es una función no computable . Además, se puede demostrar que una función de castor ocupada crece asintóticamente más rápido que cualquier función computable.

La función de castor ocupado, Σ: ℕ → ℕ, se define de manera que Σ ( n ) es la puntuación máxima alcanzable (el número máximo de 1 finalmente en la cinta) entre todas las máquinas de Turing de 2 símbolos n- estados que se detienen de las anteriores- tipo descrito, cuando se inicia en una cinta en blanco.

Está claro que Σ es una función bien definida: para cada n , hay como mucho un número finito de máquinas de Turing de estado n como antes, 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 M de Turing de 2 símbolos y estado n para la cual σ ( M ) = Σ ( n ) (es decir, que alcanza la puntuación máxima) se denomina castor ocupado . Tenga en cuenta que para cada n , existen al menos cuatro castores ocupados en n estados (porque, dado cualquier castor ocupado en n estados, se obtiene otro simplemente cambiando la dirección de cambio en una transición que se detiene, otro cambiando todos los cambios de dirección a su contrario , y la final cambiando la dirección de parada del atareado castor totalmente intercambiado).

No computabilidad

El artículo de Radó de 1962 demostró que si f : ℕ → ℕ es cualquier función computable , entonces Σ ( n )> f (n) para todos los n suficientemente grandes y, por lo tanto, Σ no es una función computable.

Además, esto implica que es indecidible por 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 probada. En particular, dicho algoritmo podría usarse para construir otro algoritmo que calcularía Σ de la siguiente manera: para cualquier n dado , cada uno de las finitas muchas máquinas de Turing de 2 símbolos de n estados se probarían hasta que se encontrara un castor ocupado de n estados; esta máquina de castor ocupada se simularía entonces para determinar su puntuación, que es por definición Σ ( n )).

Si bien Σ ( n ) es una función no calculable, existen algunas n pequeñas para las que 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 y Σ (4) = 13 (secuencia A028444 en la 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 mínimo n para el cual Σ ( n ) no se puede demostrar en ZFC . Para ello, construyeron una máquina de Turing de 7910 estados cuyo comportamiento no puede probarse 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 ). Esto se redujo más tarde a 1919 estados, con la dependencia de la propiedad estacionaria de Ramsey eliminada, y más tarde a 748 estados.

Complejidad e imposibilidad de demostrar Σ

Una variante de la complejidad de Kolmogorov se define como sigue [cf. Boolos, Burgess & Jeffrey, 2007]: La complejidad de un número n es el número más pequeño de estados necesarios para una máquina de Turing 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 ningún límite superior específico se puede probar para Σ ( k ) (lo último se debe a que "la complejidad de n es mayor que k " se probaría si se probara " 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 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 un enunciado verdadero pero no demostrable de la forma "Σ (10 ↑↑ 10) = n ", y hay infinitos pero-frases no demostrables de la forma "Σ (10 ↑↑ 10) < n ".)

Función de cambios máximos S

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

• s ( M ) = el número de cambios que M hace antes de detenerse, para cualquier M en E _n ,
• S ( n ) = máximo { s ( M ) | M ∈ E _n } = el mayor número de cambios realizados por cualquier máquina de Turing de 2 símbolos de estado n que se detenga.

Debido a que se requiere que estas máquinas de Turing tengan un cambio en todas y cada una de las transiciones o "pasos" (incluida cualquier transición a un estado de detención), la función de cambios 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. Demostró esto simplemente señalando 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 se habían sobrescrito 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 ) es conocido, entonces todos los estados n Las máquinas de Turing pueden (en principio) funcionar hasta en S ( n ) pasos, momento en el que 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 más 1 en la cinta (es decir, los castores ocupados), se 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 habían detenido en 21 pasos, lograron mostrar 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 que se acaba de describir.

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

${\ Displaystyle {\ begin {alineado} S (n) & \ geq \ Sigma (n) \\ S (n) & \ leq (2n-1) \ Sigma (3n + 3) \\ S (n) & < \ Sigma (3n + 6); \ end {alineado}}}$

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

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

${\ Displaystyle S (n)}$tiende a estar cerca del cuadrado de y, de hecho, muchas máquinas dan menos de . ${\ Displaystyle \ Sigma (n)}$${\ Displaystyle S (n)}$${\ Displaystyle \ Sigma ^ {2} (n)}$

Valores conocidos para Σ y S

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

El actual (a partir de 2018) campeón de castores ocupados de 5 estados produce 4098 1s, usando47 176 870 pasos (descubierto por Heiner Marxen y Jürgen Buntrock en 1989), pero sigue habiendo 18 o 19 (posiblemente bajo 10, ver más abajo) máquinas con un comportamiento no habitual que se cree que nunca se detiene, pero que no han sido probados para corre infinitamente. Skelet enumera 42 o 43 máquinas no probadas, pero 24 ya están probadas. Las máquinas restantes se han simulado en 81,8 mil millones de pasos, pero ninguna se detuvo. Daniel Briggs también probó algunas máquinas. Otra fuente dice que 98 máquinas aún no han sido probadas. Hay un análisis de los holdouts. Por lo tanto, es probable que Σ (5) = 4098 y S (5) = 47176870, pero esto no se ha probado y se desconoce si quedan reservas (a partir de 2018). Por el momento, el campeón récord de 6 estados produce más de3,515 × 10 ^{18 267}  1s (exactamente (25 × 4 ³⁰³⁴¹ +23) / 9), usando más de7.412 × 10 ^{36 534}  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 ^{10 10 1018 705 353} 1 en la cinta, pero indudablemente 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 que demostraban que

${\ Displaystyle \ Sigma (2k)> 3 \ uparrow ^ {k-2} 3> A (k-2, k-2) \ qquad {\ mbox {para}} k \ geq 2,}$

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

Por lo tanto

${\ Displaystyle \ Sigma (10)> 3 \ uparrow \ uparrow \ uparrow 3 = 3 \ uparrow \ uparrow 3 ^ {3 ^ {3}} = 3 ^ {3 ^ {3 ^ {. ^ {. ^ {. ^ {3}}}}}}}$

(con 3 ^{3 3}  = 7 625 597 484 987 términos en la torre exponencial), y

${\ Displaystyle \ Sigma (12)> 3 \ uparrow \ uparrow \ uparrow \ uparrow 3 = g_ {1},}$

donde el número g ₁ 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 primitivo recursivo)". Este límite inferior se puede calcular pero es demasiado complejo para expresarlo 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)> 3 \ uparrow ^ {k-2} 31> A (k-2, k-2) \ qquad {\ mbox {para}} k \ geq 2,}$

Por el contrario, el mejor límite inferior actual (a partir de 2018) en Σ (6) es 10 ^{18 267} , que es mayor que el límite inferior dado por la fórmula de Green, 3 ³ = 27 (que es pequeño en comparación). De hecho, es mucho mayor que el límite inferior: 3 ↑↑ 3 = 3 ^{3 3} =7 625 597 484 987 , que es Verde de primera límite inferior para Σ (8), y también mucho mayor que el segundo límite inferior: 3 × (7 × 3 ⁹² -1) / 2.

Σ (7) es de la misma manera 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 deje que EvalS denote una TM, evaluando S ( n ). Dada una cinta con n 1s, producirá S ( n ) 1s en la cinta y luego se detendrá. Deje que Clean denote una máquina de Turing que limpia la secuencia de unos escritos 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á 2 n 1s en la cinta y luego se detendrá. Creemos la composición Doble | EvalS | Limpiar y dejar que n ₀ sea ​​el número de estados de esta máquina. Deje que Create_n ₀ denote 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 la cabeza hacia 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 | EvalS | Limpio . Tenga en cuenta 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. Entonces 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 demostrarse de manera similar. En la prueba anterior, se debe cambiar la máquina EvalS por EvalΣ y Limpiar con Incremento - una TM simple, buscando un primer 0 en la cinta y reemplazándolo con 1.

La incomputabilidad de S ( n ) también se puede establecer haciendo 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 encienda con 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 incuestionable. 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 para S ( n ) pasos; si todavía no se ha detenido, nunca lo hará. Por lo tanto, dado que el problema de detención de la cinta en blanco no es computable, se deduce que S ( n ) debe ser igualmente incomputable.

Generalizaciones

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

1. Σ ( n , m ): el mayor número de no ceros imprimibles por un estado n , máquina de símbolo m que se inició en una cinta inicialmente en blanco antes de detenerse, y
2. S ( n , m ): el mayor número de pasos dados por una máquina de n- estado, símbolo m , iniciada en una cinta inicialmente en blanco antes de detenerse.

Por ejemplo, la máquina de 3 símbolos de 3 estados más antigua encontrada hasta ahora ejecuta 119 112 334 170 342 540 pasos antes de detenerse. La máquina de 2 símbolos y 6 estados de funcionamiento más prolongado que tiene la propiedad adicional de invertir el valor de la cinta en cada paso produce6147 1 s después47 339 970 pasos. Entonces S _RTM (6) ≥47 339 970 y Σ _RTM (6) ≥6147 .

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

Asimismo, podríamos definir una función análoga a la Σ 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 de castores ocupados. Nota: 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 posteriormente superadas 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 . Cada uno de estos sitios web también contiene algún análisis de las máquinas de Turing y referencias a las pruebas de los valores exactos.

Valores de S ( n , m )
norte metro	2 estados	3 estados	4 estados	5 estados	6 estados	7 estados
2 símbolos	6	21	107	47 176 870  ?	> 7,4 × 10 36 534	> 10 10 10 1018 705 353
3-símbolo	38	≥ 119 112 334 170 342 540	> 1,0 × 10 14 072	?	?	?
4 símbolos	≥ 3 932 964	> 5,2 × 10 13 036	?	?	?	?
5-símbolo	> 1,9 × 10 704	?	?	?	?	?
6-símbolo	> 2,4 × 10 9866	?	?	?	?	?
Valores de Σ ( n , m )
norte metro	2 estados	3 estados	4 estados	5 estados	6 estados	7 estados
2 símbolos	4	6	13	4098  ?	> 3,5 × 10 18 267	> 10 10 10 1018 705 353
3-símbolo	9	≥ 374 676 383	> 1,3 × 10 7036	?	?	?
4 símbolos	≥ 2050	> 3,7 × 10 6518	?	?	?	?
5-símbolo	> 1,7 × 10 352	?	?	?	?	?
6-símbolo	> 1,9 × 10 4933	?	?	?	?	?

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 dado se detendrá sigue siendo computacionalmente irreducible, y el cálculo requerido para encontrar un castor ocupado con NDTM es significativamente mayor que en el caso determinista, ya que hay múltiples ramas que deben tenerse en cuenta. Para un sistema de 2 estados y 2 colores con p casos o reglas, 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 ocupadas funciones Beaver ofrecen un enfoque completamente nuevo para resolver problemas de matemáticas puras. Muchos problemas abiertos en matemáticas podrían resolverse en teoría, pero no en la práctica, de manera sistemática dado el valor de S ( n ) para una n suficientemente grande .

Considere cualquier conjetura que pueda refutarse mediante un contraejemplo entre un número contable de casos (por ejemplo, la conjetura de Goldbach ). Escriba un programa de computadora que compruebe secuencialmente esta conjetura en busca de 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. Suponga 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 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 n estados, por lo que si conocemos S ( n ) podemos decidir (en una cantidad finita de tiempo) si se detendrá o no simplemente ejecutando 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, 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 los valores para la función de castor ocupado (y la función de cambio máximo). Solo se ha probado para máquinas extremadamente pequeñas con menos de cinco estados, mientras que presumiblemente se necesitarían al menos 20-50 estados para hacer una máquina útil. Además, cada valor exacto conocido de S ( n ) fue probado enumerando cada máquina de Turing de n estados y probando si cada una se detiene o no. Habría que calcular S ( n ) por algún método menos directo para que sea realmente útil.
• Pero incluso si uno encontrara una mejor manera de calcular S ( n ), los valores de la función de castor ocupado (y la función de cambio máximo) se vuelven muy grandes, muy rápido. S (6)> 10^{36 534} ya requiere una aceleración especial basada en patrones para poder simular hasta su finalización. Del mismo modo, sabemos que S (10)> Σ (10)> 3 ↑↑↑ 3 es un número gigantesco y S (17)> Σ (17)> G, donde G es el número de Graham, un número enorme. Por lo tanto, incluso si supiéramos, digamos, S (30), es completamente irrazonable ejecutar cualquier máquina ese número de pasos. No hay suficiente capacidad computacional en la parte conocida del universo para haber realizado inclusooperaciones S (6) 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 se 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 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 de

Muestra los primeros 100,000 pasos de tiempo del mejor castor ocupado de 5 estados actual. El naranja es "1", el blanco es "0" (imagen comprimida 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 a 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 ceros. Por tanto, el símbolo inicial leído de la cinta es un 0.

Resultado clave: (comienza en la posición overlined , detenida en la posición subrayados )

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 2 estados y 2 símbolos

	A	B
0	1R B	1L A
1	1L B	1R H

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

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

Castor ocupado de 3 estados y 2 símbolos

	A	B	C
0	1R B	0R C	1L C
1	1R H	1R B	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, éste es un castor ocupado sólo por Σ, pero no para S . ( S (3) = 21.)

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

Castor ocupado de 4 estados y 2 símbolos

	A	B	C	D
0	1R B	1L A	1R H	1R D
1	1L B	0L C	1L D	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)

Mejor contendiente actual de 5 estados y 2 símbolos (posible castor ocupado)

	A	B	C	D	mi
0	1R B	1R C	1R D	1L A	1R H
1	1L C	1R B	0L E	1L D	0L A

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 .

Mejor contendiente actual de 6 estados y 2 símbolos

	A	B	C	D	mi	F
0	1R B	1R C	1L D	1R E	1L A	1L H
1	1L E	1R F	0R B	0L C	0R D	1R C

Resultado: ≈3,515 × 10 ¹⁸²⁶⁷ "1" s en ≈7,412 × 10 ³⁶⁵³⁴ pasos.

Visualizaciones

En la siguiente tabla, las reglas para cada castor ocupado (maximizando Σ) se representan visualmente, con cuadrados naranjas correspondientes a un "1" en la cinta, y blancos correspondientes 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 colocan horizontalmente, con el tiempo progresando verticalmente. El estado de detención está representado por una regla que asigna un estado a sí mismo (la cabeza no se mueve).

Evolución de los castores ocupados con 1-4 estados

Reglas para castor ocupado de 1 estado.

Reglas para castor ocupado de 2 estados.

Reglas para castor ocupado de 3 estados.

Reglas para castor ocupado de 4 estados.

Evolución del castor ocupado de un estado hasta que se detenga. El estado inicial desencadena un alto, con un solo "1" que se escribe antes de la terminación.

Evolución del castor ocupado de 2 estados hasta el alto.

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

Evolución del castor ocupado de 4 estados hasta el alto. La línea inferior de la imagen izquierda se ajusta a la línea superior de la imagen derecha.

Ver también

• Número de Rayo
• Turmita

Notas

Referencias

enlaces externos

• La página de Heiner Marxen , quien, con Jürgen Buntrock, encontró los registros antes mencionados para una máquina de Turing de 5 y 6 estados.
• Estudio histórico de Pascal Michel sobre los resultados de los castores ocupados, que también contiene los mejores resultados y algunos análisis.
• Definición de la clase RTM - Reversal Turing Machines, subclase simple y fuerte de las TM.
• El " Ataque del Milenio " en el Laboratorio RAIR de Rensselaer sobre el ajetreado problema de los castores. Este esfuerzo encontró varios registros nuevos y estableció varios valores para la formalización cuádruple.
• Archivo y foro del sitio web de Daniel Briggs para resolver el problema del castor ocupado de 5 estados y 2 símbolos, según la lista de máquinas no regulares de Skelet (Georgi Georgiev).
• Aaronson, Scott (1999), ¿Quién puede nombrar el número más grande?
• Weisstein, Eric W. "Busy Beaver" . MathWorld .
• Busy Beaver Turing Machines - Computerphile
• Pascal Michel. La competencia Busy Beaver: un estudio histórico . 70 páginas. 2017. <hal-00396880v5>