castor ocupado

Máquina de Turing de mayor duración de un tamaño determinado

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 resultado posible. ^[1] Dado que es fácil concebir un programa en bucle sin fin que produzca resultados infinitos o se ejecute durante un tiempo infinito, dichos programas están excluidos del juego. A veces esto también se formula como encontrar la máquina que funciona durante más tiempo, pero ambos juegos son igualmente difíciles. ^[2]

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

1. la máquina debe tener como máximo dos estados además del estado de parada, 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 unos en la cinta mientras se asegura de que la máquina se detenga eventualmente.

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

Decidir el número de unos, o el tiempo de ejecución, del enésimo Busy Beaver es incalculable . 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". ^[1]

El juego

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 parada, donde n es un número entero positivo y uno de los n estados se distingue como el estado inicial. (Normalmente, los estados están etiquetados por 1, 2, ..., n , con el estado 1 como estado inicial, o por 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}, siendo el 0 el símbolo en blanco.
• La función de transición de la máquina toma dos entradas:

1. el estado actual sin suspensió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 realizar la transición (que puede ser el estado Detener).

Por lo tanto, hay (4 n + 4) ^{2 n} n máquinas de Turing de estados que cumplen con 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 la forma

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

"Ejecutar" la máquina consiste en comenzar en el estado inicial, siendo la celda de la 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 Detener (si es que alguna vez se ingresa). Si, y sólo si , la máquina finalmente se detiene, entonces el número de unos que finalmente quedan 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 unos en su cinta después de detenerse. Una máquina que alcanza la mayor puntuación posible entre todas las máquinas de Turing de n estados se llama castor ocupado de n estados, y una máquina cuya puntuación es simplemente la más alta alcanzada hasta ahora (quizás no la mayor posible) se llama campeona de n estados. máquina.

Radó requirió que cada máquina inscrita en el concurso estuviera acompañada de una declaración del número exacto de pasos que se necesitan para alcanzar el estado Detener, permitiendo así verificar la puntuación de cada entrada (en principio) haciendo funcionar la máquina durante el número indicado. de pasos. (Si las entradas consistieran únicamente en descripciones de máquinas, entonces el problema de verificar cada entrada potencial sería indecidible, porque es equivalente al conocido problema de la 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 ocupado crece asintóticamente más rápido que cualquier función computable. ^[3]

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 unos finalmente en la cinta) entre todas las máquinas de Turing de estado n de 2 símbolos que se detienen 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 antes, hasta el isomorfismo, por lo tanto, como máximo, 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 M de 2 símbolos y n estados para la cual σ ( M ) = Σ( n ) (es decir, que alcanza la puntuación máxima) se llama castor ocupado . Tenga en cuenta que para cada n , existen al menos cuatro castores ocupados de n estados (porque, dado cualquier castor ocupado de n estados, otro se obtiene simplemente cambiando la dirección del cambio en una transición detenida, otro cambiando todos los cambios de dirección a su opuesto). , y el final cambiando la dirección de detención del castor ocupado completamente intercambiado. En teoría, 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. producir el resultado buscado).

No computabilidad

El artículo de Radó de 1962 demostró que si es cualquier función computable , entonces Σ( n ) > f ( n ) para todos los n suficientemente grandes y, por tanto, que Σ no es una función computable. ${\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. (Tal algoritmo no puede existir, porque su existencia permitiría calcular Σ, lo cual es una imposibilidad comprobada. 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 máquinas de Turing de n estados y 2 símbolos se probarían hasta que se encontrara un castor ocupado de n estados; luego esta máquina castor ocupada se simularía para determinar su puntuación, que por definición es Σ( n ).)

Aunque Σ( n ) es una función no computable, 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 cada vez con mayor dificultad se puede demostrar que Σ(3) = 6 y Σ(4) = 13 (secuencia A028444 en el OEIS ). Σ( n ) aún no se ha determinado para ningún caso 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) del mínimo n para el cual Σ( n ) no es demostrable en ZFC . Para ello construyeron una máquina de Turing de 7910 estados ^[4] 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). ^{[5] [6]} Stefan O'Rear luego lo redujo a 1919 estados, eliminando la dependencia de la propiedad estacionaria de Ramsey, ^{[7] [8]} y más tarde a 748 estados. ^[9] En julio de 2023, Riebel lo redujo a 745 estados. ^{[10] [11]}

Complejidad e imposibilidad de demostrar Σ

Una variante de la complejidad de Kolmogorov se define de la siguiente manera: ^[12] 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 unos 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, no existe un límite superior específico. se puede probar para Σ( k ) (esto ú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 que 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 oraciones 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 las máquinas de Turing, la función de desplazamientos máximos , S , definida de la siguiente manera:

• s ( M ) = el número de cambios que M hace antes de detenerse, para cualquier M ∈ E _n ,
• S ( norte ) = máximo { 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 que se detiene.

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 parada), 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 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 había demostrado que crece más rápido que cualquier función computable.

Lin y Radó [ Estudios informáticos de problemas de la máquina de Turing , 1965] utilizaron la siguiente conexión entre Σ y S para demostrar que Σ(3) = 6: Para un n dado , si se conoce S ( n ), entonces todos los n -estados Las máquinas de Turing pueden (en principio) ejecutarse hasta S ( n ) pasos, momento en el cual cualquier máquina que aún no se haya detenido nunca se detendrá. En ese punto, al observar qué máquinas se han detenido con más unos en la cinta (es decir, los castores ocupados), se obtiene de sus cintas el valor de Σ( n ). El enfoque utilizado por Lin y Radó para el caso de n = 3 fue conjeturar que S (3) = 21, 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 demostrar que ninguna de esas máquinas se detendría jamás, demostrando 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{aligned}S(n)&\geq \Sigma (n)\\S(n)&\leq (2n-1)\Sigma (3n+3)\\S(n)&<\Sigma (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+\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 que . ${\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 . ^[6]

El actual (a partir de 2023) campeón de castores ocupados de 5 estados produce4098 1s, usando47 176 870 pasos (descubierto por Heiner Marxen y Jürgen Buntrock en 1989), pero aún quedan muchas máquinas con un comportamiento no regular que se cree que nunca se detienen, pero que no se ha demostrado que funcionen infinitamente. Varias fuentes enumeran diferentes números de estos reticentes. Skelet enumera 42 o 43 máquinas no probadas. ^[13]

Actualmente, el campeón récord de 6 estados produce más de 10⇈15 ^[14] (encontrado por Pavel Kropitz en 2022). Como se señaló anteriormente, se trata de máquinas de Turing de 2 símbolos.

Milton Green, en su artículo de 1964 "Un límite inferior en la función Sigma de Rado para máquinas binarias de Turing", 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 {\text{for }}k\geq 2,}$

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

De este modo

${\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 del 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 expresarlo como una expresión única 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 {\text{for }}k\geq 2,}$

Por el contrario, el mejor límite inferior actual (a partir de 2023) de Σ(6) es 10⇈15, 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 el primer límite inferior de Green para Σ(8), y también mucho mayor que el segundo límite inferior: 3×(7×3 ⁹² −1)/2.

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

Supongamos que S ( n ) es una función computable y dejemos 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 Clean una máquina de Turing que limpia la secuencia de unos escrita inicialmente en la cinta. Sea Double una función de evaluación de la máquina de Turing n + n . Dada una cinta con n 1, producirá 2 n 1 en la cinta y luego se detendrá. Creemos la composición Doble | Evaluaciones | Limpie y sea n ₀ 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 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 | Evaluaciones | Limpio . Observe que esta máquina tiene N estados. Comenzando con una cinta inicialmente en blanco, primero crea una secuencia de n ₀ 1 y luego la duplica, produciendo una secuencia de N 1. 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 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 ) puede demostrarse de manera similar. En la prueba anterior, se debe intercambiar la máquina EvalS con EvalΣ y Clean con Increment : 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 inicie 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, tampoco es computable. Si S ( n ) fuera computable, entonces podríamos resolver el problema de la 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á. Entonces, dado que el problema de detención de la cinta en blanco no es computable, se deduce que S ( n ) tampoco debe ser computable.

Generalizaciones

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

1. Σ( n , m ): el mayor número de ceros distintos de ceros imprimibles por una máquina de n estados y m símbolos que comenzó 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 estados y m símbolos comenzó en una cinta inicialmente en blanco antes de detenerse.

Por ejemplo, la máquina de 3 estados y 3 símbolos de mayor funcionamiento encontrada hasta ahora ejecuta119 112 334 170 342 540 pasos antes de detenerse. ^[15] La máquina de 2 símbolos y 6 estados de mayor duración que tiene la propiedad adicional de invertir el valor de la cinta en cada paso produce6147 1s después47 339 970 pasos. ^{[ cita necesaria ]} Entonces, para la clase de Máquina de Turing Inversa (RTM), ^[16] S _RTM (6) ≥47 339 970 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.

Asimismo, podríamos definir una función análoga a la función Σ para máquinas de registro como el mayor número que puede estar presente en cualquier registro al detenerse, para un número determinado 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 hacia la izquierda y arriba. Estas máquinas no han sido investigadas o fueron superadas posteriormente por una máquina más pequeña.

Máquinas de Turing no deterministas

El problema se puede extender a las máquinas de Turing no deterministas buscando el sistema con más estados en todas las ramas o la rama con el mayor número de pasos. ^[17] 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 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 de castor 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 forma sistemática dado el valor de S ( n ) para un n suficientemente grande . ^[18]

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 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 y lo indica. Sin embargo, si la conjetura es cierta, nuestro programa nunca se detendrá. (Este programa se detiene sólo 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 de tiempo finita) si alguna vez 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, 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). Solo se ha probado para máquinas extremadamente pequeñas con menos de cinco estados, mientras que presumiblemente se necesitarían al menos entre 20 y 50 estados ^{[ cita necesaria ]} para fabricar una máquina útil. Además, cada valor exacto conocido de S ( n ) se demostró enumerando cada máquina de Turing de n estados y demostrando si cada una se detiene o no. Habría que calcular S ( n ) mediante algún método menos directo para que fuera realmente útil.
• Pero incluso si se encontrara una mejor manera de calcular S ( n ), los valores de la función de castor ocupado (y la función de desplazamiento 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. Asimismo, sabemos quees un número gigantesco y S (17) > Σ(17) > G > g ₁ , donde G esel número de Graham, un número enorme. Por lo tanto, incluso si supiéramos, digamos,S(30), es completamente irrazonable hacer funcionar una máquina con ese número de pasos. No hay suficiente capacidad computacional en la parte conocida del universo para haber realizado inclusoS(6) directamente. ^[19] ${\displaystyle S(10)>\Sigma (10)>3\uparrow \uparrow \uparrow 3}$

Casos notables

Se ha construido una máquina binaria de Turing de 745 estados que se detiene si y sólo si ZFC es inconsistente. ^{[10] [11]} 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. ^{[7] [20]} 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. ^{[7] [20]}

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 ⁿ . ^{[21] [22]}

Ejemplos

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).

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 ceros. Por tanto, el símbolo inicial leído en la cinta es un 0.

Tecla de resultado: (comienza en la posición subrayada , se detiene en la posición subrayada )

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

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

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 está ocupada sólo para Σ, pero no para S. ( S (3) = 21.)

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

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

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

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

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).

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 un "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 y el tiempo avanza 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).

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

Ver también

• El número del Rayo
• Turmita

Notas

1. Radó, Tibor (mayo de 1962). «Sobre funciones no computables» (PDF) . Revista técnica del sistema Bell . 41 (3): 877–884. doi :10.1002/j.1538-7305.1962.tb00480.x.
2. Weisstein, Eric W. "Castor ocupado". Wolfram MathWorld . Consultado el 21 de noviembre de 2023 .
3. Chaitín (1987)
4. Adam Yedidia y Scott Aaronson (mayo de 2016). Una máquina de Turing relativamente pequeña cuyo comportamiento es independiente de la teoría de conjuntos (informe técnico). MIT. arXiv : 1605.04343 . Código Bib : 2016arXiv160504343Y.
5. Arón, Jacob. "Esta máquina de Turing debería funcionar para siempre a menos que las matemáticas estén mal" . Consultado el 25 de septiembre de 2016 .
6. La versión del 3 de mayo contenía 7918 estados: "El número 8000 de Busy Beaver elude la teoría de conjuntos de ZF". Blog optimizado para Shtetl . 2016-05-03 . Consultado el 25 de septiembre de 2016 .
7. "Tres anuncios". Blog optimizado para Shtetl . 2016-05-03 . Consultado el 27 de abril de 2018 .
8. "GitHub - sorear/metamath-turing-machines: enumeradores a prueba de Metamath y otras cosas". GitHub . 2019-02-13.
9. "La ocupada frontera de los castores" (PDF) .
10. "La vida, los blogs y la función Busy Beaver continúan". 2023-07-05 . Consultado el 27 de agosto de 2023 .
11. "La indecidibilidad de BB (748)" (PDF) . Consultado el 27 de agosto de 2023 .
12. Boolos, Burgess & Jeffrey, 2007. "Computabilidad y lógica"
13. "Página de esqueleto para el problema de Busy Beaver". esqueleto.ludost.net .
14. BB(6, 2) > 10 ↑ ↑ 15 ​​artículo que demuestra este límite.
15. Página de competencias Busy Beaver de Pascal Michel que enumera a los mejores contendientes conocidos.
16. "Máquina de Turing inversa". esqueleto.ludost.net . Consultado el 10 de febrero de 2022 .
17. Wolfram, Stephen (4 de febrero de 2021). "Máquinas de Turing multidireccionales". www.wolframphysics.org .
18. Chaitín 1987
19. Lloyd 2001. Capacidad computacional del universo.
20. Pavlus, John (10 de diciembre de 2020). "Cómo los programas informáticos más lentos iluminan los límites fundamentales de las matemáticas". Revista Quanta . Consultado el 11 de diciembre de 2020 .
21. Tristan Stérin y Damien Woods (julio de 2021). Sobre la dureza de conocer los valores de castor ocupado BB(15) y BB(5,4) (Informe técnico). Universidad de Maynooth. arXiv : 2107.12475 .
22. Erdõs, Paul (1979). "Algunos problemas no convencionales en teoría de números". Matemáticas. revista 52 (2): 67–70. doi :10.1080/0025570X.1979.11976756. JSTOR  2689842.
23. Shen Lin (1963). Estudios informáticos de problemas de la máquina de Turing (tesis doctoral). Universidad del Estado de Ohio .
24. Lin, Shen; Rado, Tibor (abril de 1965). "Estudios informáticos de los problemas de la máquina de Turing". Revista de la ACM . 12 (2): 196–212. doi : 10.1145/321264.321270 . S2CID  17789208.

Referencias

• Radó, Tibor (mayo de 1962). «Sobre funciones no computables» (PDF) . Revista técnica del sistema Bell . 41 (3): 877–884. doi :10.1002/j.1538-7305.1962.tb00480.x.

  Aquí es donde Radó definió por primera vez el problema del castor ocupado y demostró que era incomputable y crecía más rápido que cualquier función computable.

• Lin, Shen; Radó, Tibor (abril de 1965). "Estudios informáticos de los problemas de la máquina de Turing". Revista de la ACM . 12 (2): 196–212. doi : 10.1145/321264.321270 . S2CID  17789208.

  Los resultados de este artículo ya habían aparecido en parte en la tesis doctoral de Lin de 1963, bajo la dirección de Radó. Lin y Radó demuestran que Σ(3) = 6 y S (3) = 21 demostrando que todas las máquinas de Turing de 3 estados y 2 símbolos que no se detienen en 21 pasos nunca se detendrán. (La mayoría se verifican automáticamente mediante un programa de computadora, pero 40 se verifican mediante inspección humana).

• Brady, Allen H. (abril de 1983). "La determinación del valor de la función no computable de Rado Σ (k) para máquinas de Turing de cuatro estados". Matemáticas de la Computación . 40 (162): 647–665. doi : 10.1090/S0025-5718-1983-0689479-6 . JSTOR  2007539.

  Brady demuestra que Σ(4) = 13 y S (4) = 107. Brady define dos nuevas categorías para máquinas de Turing de 3 estados y 2 símbolos que no se detienen: árboles de Navidad y mostradores. Utiliza un programa de computadora para demostrar que todas las máquinas, excepto 27, que funcionan en 107 pasos, son variantes de árboles de Navidad y mostradores que se puede demostrar que funcionan infinitamente. Las últimas 27 máquinas (denominadas resistencias) han demostrado, mediante inspección personal realizada por el propio Brady, que no se detienen.

• Machlin, Rona; Stout, Quentin F. (junio de 1990). "El comportamiento complejo de las máquinas simples". Physica D: Fenómenos no lineales . 42 (1–3): 85–98. Código bibliográfico : 1990PhyD...42...85M. doi :10.1016/0167-2789(90)90068-Z. hdl : 2027.42/28528 .

  Machlin y Stout describen el problema del castor ocupado y muchas técnicas utilizadas para encontrar castores ocupados (que aplican a las máquinas de Turing con 4 estados y 2 símbolos, verificando así la prueba de Brady). Sugieren cómo estimar una variante de la probabilidad de parada de Chaitin (Ω).

• Marxen, Heiner; Buntrock, Jürgen (febrero de 1990). "Atacando al Busy Beaver 5". Boletín de la EATCS . 40 : 247–251. Archivado desde el original el 9 de octubre de 2006 . Consultado el 19 de enero de 2020 .

  Marxen y Buntrock demuestran que Σ(5) ≥ 4098 y S (5) ≥ 47 176 870 y describir en detalle el método que utilizaron para encontrar estas máquinas y demostrar que muchas otras nunca se detendrán.

• Verde, Milton W. (1964). "Un límite inferior de la función Sigma de Rado para máquinas binarias de Turing ". 1964 Actas del Quinto Simposio Anual sobre Teoría de Circuitos de Conmutación y Diseño Lógico. págs. 91–94. doi :10.1109/SWCT.1964.3.

  Green construye recursivamente máquinas para cualquier número de estados y proporciona la función recursiva que calcula su puntuación (calcula σ), proporcionando así un límite inferior para Σ. El crecimiento de esta función es comparable al de la función de Ackermann .

• Dewdney, Alexander K. (1984). "Una trampa informática para el castor ocupado, la máquina de Turing que más trabaja". Científico americano . 251 (2): 10-17.

  Los programas de castores ocupados son descritos por Alexander Dewdney en Scientific American , agosto de 1984, páginas 19 a 23, también marzo de 1985, p. 23 y abril de 1985 p. 30.

• Chaitin, Gregory J. (1987). "Cálculo de la función Busy Beaver" (PDF) . En portada, TM; Gopinath, B. (eds.). Problemas abiertos en comunicación y computación . Saltador. págs. 108-112. ISBN 978-0-387-96621-2. Archivado desde el original (PDF) el 30 de diciembre de 2017 . Consultado el 7 de julio de 2022 .
• Brady, Allen H. (1995). "El juego del castor ocupado y el significado de la vida". En Herken, Rolf (ed.). La máquina universal de Turing: una encuesta de medio siglo (2ª ed.). Viena, Nueva York: Springer-Verlag. págs. 237–254. ISBN 978-3-211-82637-9.

  Donde Brady (famoso en 4 estados) describe algo de la historia de la bestia y llama a su búsqueda "El juego del castor ocupado". Describe otros juegos (por ejemplo, autómatas celulares y el Juego de la vida de Conway ). De particular interés es "El juego del castor ocupado en dos dimensiones" (p. 247). Con 19 referencias.

• Stand, Taylor L. (1967). Máquinas Secuenciales y Teoría de Autómatas . Nueva York: Wiley. ISBN 978-0-471-08848-6.

  Cf. Capítulo 9, Máquinas de Turing. Un libro difícil, destinado a ingenieros eléctricos y especialistas técnicos. Analiza la recursividad, la recursividad parcial con referencia a las máquinas de Turing, y el problema de detención. Una referencia en Booth atribuye el castor ocupado a Rado. Booth también define el problema del castor ocupado de Rado en "problemas domésticos" 3, 4, 5, 6 del Capítulo 9, p. 396. El problema 3 consiste en "mostrar que el problema del castor ocupado no tiene solución... para todos los valores de n".

• Ben-Amram, AM; Julstrom, Licenciatura en Letras; Zwick, U. (1996). "Una nota sobre Busy Beavers y otras criaturas". Teoría de Sistemas Matemáticos . 29 (4): 375–386. CiteSeerX  10.1.1.75.1297 . doi :10.1007/BF01192693. S2CID  30937913. Archivado desde el original el 21 de julio de 2018 . Consultado el 7 de julio de 2022 .

  Límites entre funciones Σ y S .

• Ben-Amram, AM; Petersen, H. (2002). "Límites mejorados para funciones relacionadas con castores ocupados". Teoría de los Sistemas Computacionales . 35 : 1–11. CiteSeerX  10.1.1.136.5997 . doi :10.1007/s00224-001-1052-0. S2CID  10429773.

  Límites mejorados.

• Lafitte, G.; Papazian, C. (junio de 2007). "El tejido de las pequeñas máquinas de Turing". Computación y lógica en el mundo real, Actas de la Tercera Conferencia sobre Computabilidad en Europa . págs. 219-227. CiteSeerX  10.1.1.104.3021 .

  Este artículo contiene una clasificación completa de las máquinas de Turing de 2 estados y 3 símbolos y, por tanto, una prueba del castor ocupado (2, 3): Σ(2, 3) = 9 y S(2, 3) = 38.

• Boolos, George S.; Burgess, John P.; Jeffrey, Richard C. (2007). Computabilidad y Lógica (Quinta ed.). Prensa de la Universidad de Cambridge. ISBN 978-0-521-87752-7.
• Kropitz, Pavel (2010). Problém Busy Beaver (tesis de licenciatura) (en eslovaco). Universidad Carolina de Praga.

  Esta es la descripción de las ideas, de los algoritmos y su implementación, con la descripción de los experimentos que examinan máquinas de Turing de 5 y 6 estados ejecutadas en paralelo en 31 computadoras de 4 núcleos y, finalmente, los mejores resultados para la MT de 6 estados.

enlaces externos

• La página de Heiner Marxen, quien junto 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 - Máquinas de Turing inversas, subclase simple y fuerte de las TM.
• "El problema del castor ocupado: un nuevo ataque del milenio" (archivado) en el laboratorio Rensselaer RAIR. Este esfuerzo encontró varios registros nuevos y estableció varios valores para la cuádruple formalización.
• 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 similar al de Collatz de Busy Beavers". sligocki . Consultado el 12 de julio de 2022 .
• Aaronson, Scott (1999), ¿Quién puede nombrar el número mayor?
• Weisstein, Eric W. "Castor ocupado". MundoMatemático .
• Máquinas de Turing de Beaver ocupadas - Computerphile, Youtube
• Pascal Michel. La competencia Busy Beaver: un estudio histórico. 70 páginas. 2017. <hal-00396880v5>