Castor ocupado

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

Este "diagrama espacio-temporal" ^[1] muestra los primeros 100.000 pasos de tiempo del mejor castor atareado de 5 estados, de arriba a abajo. El naranja es "1", el blanco es "0" (imagen comprimida verticalmente).

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

Las máquinas de Turing consisten en una cinta infinita y un conjunto finito de estados que sirven como "código fuente" del programa. Producir la mayor cantidad de salida se define como escribir la mayor cantidad de 1 en la cinta, también conocido como lograr la puntuación más alta, y funcionar durante el mayor tiempo se define como dar la mayor cantidad de pasos para detenerse. ^[4] El juego del castor atareado de n estados consiste en encontrar la máquina de Turing que funcione durante más tiempo o con la puntuación más alta que tenga n estados y finalmente se detenga. ^[2] Se supone que estas máquinas comienzan en una cinta en blanco, y se supone que la cinta contiene solo ceros y unos (una máquina de Turing binaria). ^[2] El objetivo del juego es programar un conjunto de transiciones entre estados con el objetivo de obtener la puntuación más alta o el tiempo de funcionamiento más largo, asegurándose al mismo tiempo que la máquina se detendrá eventualmente.

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

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

Definición técnica

Movimientos de un Busy Beaver de 3 estados. Este es uno de los varios Busy Beaver que dan la cantidad máxima de 1 en el punto de detención (es decir, 6). Las flechas muestran los movimientos según el estado y si la máquina lee un 0 o un 1. "P" significa imprimir un 1 antes de moverse a la derecha o a la izquierda ("R" o "L").

El juego del castor ocupado de n estados (o juego BB -n ), introducido en el artículo de Tibor Radó de 1962, involucra una clase de máquinas de Turing , cada miembro de las cuales debe cumplir con las siguientes especificaciones de diseño:

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

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

y produce tres resultados:

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

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

Ejemplo

Las reglas para una máquina de Turing de 1 estado podrían ser:

• En el estado 1, si el símbolo actual es 0, escribe un 1, muévete un espacio hacia la derecha y pasa al estado 1
• En el estado 1, si el símbolo actual es 1, escriba un 0, muévase un espacio a la derecha y pase a HALT

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

Funciones

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

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

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

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

Función de puntuación Σ

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

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

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

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

No computabilidad

El artículo de Radó de 1962 demostró que si es cualquier función computable , entonces Σ( n ) > f ( n ) para todo n suficientemente grande , y por lo tanto que Σ no es una función computable. ^[4] ${\displaystyle f:\mathbb {N} \to \mathbb {N} }$

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

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

Complejidad e imposibilidad de demostrar Σ

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

Función de cambios máximosS

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

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

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

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

La siguiente conexión entre Σ y S fue utilizada por Lin y Radó [ Computer Studies of Turing Machine Problems , 1965] para demostrar que Σ(3) = 6 y que S(6)=21: Para un n dado , si S ( n ) es conocido, entonces todas las máquinas de Turing de n estados pueden (en principio) funcionar hasta S ( n ) pasos, en cuyo punto cualquier máquina que aún no se haya detenido nunca se detendrá. En ese punto, al observar qué máquinas se han detenido con la mayor cantidad de 1 en la cinta (es decir, los castores atareados), uno obtiene de sus cintas el valor de Σ( n ). El enfoque utilizado por Lin y Radó para el caso de n = 3 fue conjeturar que S (3) = 21 (después de conjeturar sin éxito 18), luego simular todas las máquinas de 3 estados esencialmente diferentes (82,944 máquinas, igual a 2 ^{· 10} 3 ⁴ ) durante hasta 21 pasos. Encontraron 26,073 máquinas que se detuvieron, incluida una que se detuvo solo después de 21 pasos. Al analizar el comportamiento de las máquinas que no se habían detenido dentro de los 21 pasos, lograron demostrar que ninguna de esas máquinas se detendría nunca, la mayoría de ellas siguiendo un cierto patrón. Esto demostró la conjetura de que S (3) = 21, y también determinó que Σ(3) = 6, que fue alcanzado por varias máquinas, todas deteniéndose después de 11 a 14 pasos. ^[14]

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

Prueba de la incomputabilidad deS(norte) y Σ(norte)

Supongamos que S ( n ) es una función computable y que EvalS denote una TM, que evalúa S ( n ). Dada una cinta con n 1s, producirá S ( n ) 1s en la cinta y luego se detendrá. Sea Clean una máquina de Turing que limpia la secuencia de 1s inicialmente escritos en la cinta. Sea Double una máquina de Turing que evalúa la función n + n . Dada una cinta con n 1s, producirá 2 n 1s en la cinta y luego se detendrá. Creemos la composición Double | EvalS | Clean y sea n ₀ el número de estados de esta máquina. Sea Create_n ₀ una máquina de Turing que crea n ₀ 1s en una cinta inicialmente en blanco. Esta máquina puede construirse de manera trivial para tener n ₀ estados (el estado i escribe 1, mueve el cabezal a la derecha y cambia al estado i + 1, excepto el estado n ₀ , que se detiene). Sea N la suma n ₀ + n ₀ .

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

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

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

Incomputabilidad de espacio(n) y num(n)

Ambas funciones y son incomputables. ^[9] Esto se puede demostrar notando que en cada cuadrado de cinta en el que una máquina de Turing escribe un uno, también debe visitar: en otras palabras, . ^[9] Se puede demostrar que la función es incomputable probando, por ejemplo, que : esto se puede hacer diseñando una máquina de Turing de (3n+3) estados que simule el campeón del espacio de n estados, y luego lo use para escribir al menos unos contiguos en la cinta. ^[9] ${\displaystyle {\text{space}}(n)}$ ${\displaystyle {\text{num}}(n)}$ ${\displaystyle {\text{space}}(n)}$ ${\displaystyle \Sigma (n)\leq {\text{space}}(n)}$ ${\displaystyle {\text{num}}(n)}$ ${\displaystyle {\text{space}}(n)<{\text{num}}(3n+3)}$ ${\displaystyle {\text{space}}(n)}$

Generalizaciones

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

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

Diferentes números de símbolos

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

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

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

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 el mayor número de pasos. ^[11] La cuestión de si una NDTM dada se detendrá sigue siendo computacionalmente irreducible, y el cálculo requerido para encontrar una NDTM inquieta es significativamente mayor que el caso determinista, ya que hay múltiples ramas que deben considerarse. Para un sistema de 2 estados y 2 colores con p casos o reglas, la tabla a la derecha muestra el número máximo de pasos antes de detenerse y el número máximo de estados únicos creados por la NDTM.

Aplicaciones

Problemas matemáticos abiertos

Además de plantear un juego matemático bastante desafiante , las funciones de castor atareado Σ(n) y S ( n ) ofrecen un enfoque completamente nuevo para resolver problemas de matemáticas puras. Muchos problemas abiertos en matemáticas podrían en teoría, pero no en la práctica, resolverse de manera sistemática dado el valor de S ( n ) para un n suficientemente grande . ^{[5] [22]} Teóricamente hablando, el valor de S(n) codifica la respuesta a todas las conjeturas matemáticas que pueden verificarse en tiempo infinito por una máquina de Turing con estados menores o iguales a n . ^[6]

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

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

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

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

Coherencia de las teorías

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

Ejemplos notables

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

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

• En 2016, se construyó una máquina de Turing de 43 estados que se detiene si, y solo si, la conjetura de Goldbach es falsa. Esta se redujo a una máquina de 27 estados ^{[18] [5]} y en 2024 esta construcción se demostró y verificó formalmente en el lenguaje de demostración de teoremas Lean 4. ^[23]

• 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 de base 3 de 2 ⁿ . ^{[24] [25]}

Máquinas universales de Turing

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

Resultados conocidos

Límites inferiores

Maquinas verdes

En 1964, Milton Green desarrolló un límite inferior para la variante de conteo de 1s de la función Busy Beaver que se publicó en las actas del simposio IEEE de 1964 sobre teoría de circuitos de conmutación y diseño lógico. Heiner Marxen y Jürgen Buntrock lo describieron como "un límite inferior no trivial (no recursivo primitivo)". ^[27] Este límite inferior se puede calcular, pero es demasiado complejo para expresarlo como una única expresión en términos de n . ^[28] Esto se hizo con un conjunto de máquinas de Turing, cada una de las cuales demostró el límite inferior para un cierto n . ^[28] Cuando n = 8, el método da

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

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

Específicamente, el límite inferior se mostró con una serie de máquinas de Turing recursivas, cada una de las cuales estaba formada por una más pequeña con dos estados adicionales que aplicaban repetidamente la máquina más pequeña a la cinta de entrada. ^[28] Al definir el valor del competidor de castor ocupado de N estados en una cinta que contiene unos como (la salida final de cada máquina es su valor en , porque una cinta en blanco tiene 0 unos), las relaciones de recursión son las siguientes: ^[28] a ${\displaystyle m}$ ${\displaystyle B_{N}(m)}$ ${\displaystyle m=0}$

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

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

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

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

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

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

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

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

Relaciones entre las funciones de Busy beaver

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

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

Al definir num(n) como el número máximo de unos que una máquina de Turing de n estados puede generar de forma contigua, en lugar de en cualquier posición (el número unario más grande que puede generar), es posible demostrar: ^[29]

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

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

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

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

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

Valores exactos y límites inferior y superior

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

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

Lista de castores ocupados

Diagrama espacio-temporal ampliado de la máquina de Turing de cinco estados (para S(n), luego Σ(n)). La máquina funciona durante 47.176.870 pasos, alcanzando un máximo de 12.288 ceros y dejando atrás 4.098 ceros al detenerse.
El diagrama está comprimido, de modo que solo se muestran los pasos que cambian la cinta. Los triángulos verdes y amarillos indican las regiones en las que la máquina de Turing se desplaza de un lado a otro; el tiempo que tarda es proporcional a las áreas de estos triángulos de colores. La fila inferior es un extracto de la cinta y del cabezal de lectura/escritura al detenerse.

Éstas son tablas de reglas para máquinas de Turing que generan Σ(1) y S (1), Σ(2) y S (2), Σ(3) (pero no S (3)), Σ(4) y S (4), Σ(5) y S (5), y el límite inferior más conocido para Σ(6) y S (6).

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

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

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

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

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

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

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

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)

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

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

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 activo (maximización de Σ) se representan visualmente, con cuadrados naranjas que corresponden a un "1" en la cinta y blancos que corresponden a un "0". La posición de la cabeza se indica mediante el ovoide negro, y la orientación de la cabeza representa el estado. Las cintas individuales se disponen horizontalmente, y el tiempo avanza de arriba hacia abajo. El estado de detención se representa mediante una regla que asigna un estado a sí mismo (la cabeza no se mueve).

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

Véase también

• El número del Rayo
• Turmita

Notas

1. "El desafío del castor atareado: historia n.° 1: diagramas espacio-temporales". bbchallenge.org . Consultado el 9 de julio de 2024 .
2. Weisstein, Eric W. "Busy Beaver". Wolfram MathWorld . Consultado el 21 de noviembre de 2023 .
3. Brubaker, Ben (2 de julio de 2024). "Matemáticos aficionados encuentran la quinta máquina de Turing 'Busy Beaver'". Quanta Magazine . Consultado el 3 de julio de 2024 .
4. Radó, Tibor (mayo de 1962). "Sobre funciones no computables" (PDF) . Bell System Technical Journal . 41 (3): 877–884. doi :10.1002/j.1538-7305.1962.tb00480.x.
5. 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». Quanta Magazine . Consultado el 11 de diciembre de 2020 .
6. Aaronson, Scott (29 de septiembre de 2020). "La ajetreada frontera de los castores". Noticias SIGACT . 51 (3): 32–54. doi :10.1145/3427361.3427369. ISSN  0163-5700.PDF disponible del autor.
7. "La vida, los blogs y la función de castor atareado continúan". 2023-07-05 . Consultado el 2023-08-27 .
8. Riebel, Johannes (marzo de 2023). La indecidibilidad de BB(748): comprensión de los teoremas de incompletitud de Gödel (PDF) (tesis de licenciatura). Universidad de Augsburgo . Consultado el 24 de septiembre de 2024 .
9. Ben-Amram, AM; Julstrom, BA; Zwick, U. (1996-08-01). "Una nota sobre los castores ocupados y otras criaturas". Teoría de sistemas matemáticos . 29 (4): 375–386. doi :10.1007/BF01192693. ISSN  1433-0490.
10. Aaronson, Scott (2 de julio de 2024). "Ahora se sabe que BusyBeaver(5) es 47 176 870". Shtetl-Optimized . Consultado el 4 de julio de 2024 .
11. Wolfram, Stephen (4 de febrero de 2021). "Máquinas de Turing multidireccionales". www.wolframphysics.org .
12. Chaitín (1987)
13. Boolos, Burgess y Jeffrey, 2007. "Computabilidad y lógica"
14. Lin, Shen; Rado, Tibor (abril de 1965). "Estudios informáticos de problemas de máquinas de Turing". Revista de la ACM . 12 (2): 196–212. doi : 10.1145/321264.321270 . S2CID  17789208.
15. 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 Bibliográfico :2016arXiv160504343Y.
16. Aron, Jacob. "Esta máquina de Turing debería funcionar eternamente a menos que las matemáticas estén equivocadas". NewScientist . Consultado el 25 de septiembre de 2016 .
17. 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 Shtetl-Optimized . 2016-05-03 . Consultado el 2016-09-25 .
18. "Tres anuncios". Blog optimizado para Shtetl . 2016-05-03 . Consultado el 2018-04-27 .
19. "GitHub - sorear/metamath-turing-machines: Enumeradores de pruebas de Metamath y otras cosas". GitHub . 13 de febrero de 2019.
20. "Máquina de Turing inversa". skelet.ludost.net . Consultado el 10 de febrero de 2022 .
21. Página de competencias Busy Beaver de Pascal Michel que enumera a los mejores contendientes conocidos.
22. Chaitin, Gregory J. (1987). "Computing the Busy Beaver Function" (PDF) . En portada, TM; Gopinath, B. (eds.). Problemas abiertos en comunicación y computación . Springer. págs. 108-112. ISBN. 978-0-387-96621-2Archivado desde el original (PDF) el 30 de diciembre de 2017. Consultado el 7 de julio de 2022 .
23. Leng, Yijun. "Repositorio de GitHub" goldbach_tm27"". GitHub .
24. Tristan Stérin y Damien Woods (julio de 2021). Sobre la dificultad de conocer los valores BB(15) y BB(5,4) del castor atareado (informe técnico). Universidad de Maynooth. arXiv : 2107.12475 .
25. Erdõs, Paul (1979). "Algunos problemas no convencionales en la teoría de números". Math. Mag. 52 (2): 67–70. doi :10.1080/0025570X.1979.11976756. JSTOR  2689842.
26. Zenil, Hector (2012). "Sobre el comportamiento cualitativo dinámico de la computación universal". Sistemas complejos . 20 (3): 265–277. doi :10.25088/ComplexSystems.20.3.265. ISSN  0891-2513.PDF disponible en el editor.
27. Brady, Allen H. (marzo de 1998). "Heiner Marxen y Jürgen Buntrock. Atacando al castor atareado 5. Boletín de la Asociación Europea de Ciencias Informáticas Teóricas, n.º 40 (febrero de 1990), págs. 247-251. - Pascal Michel. Competencia del castor atareado y problemas similares a Collatz. Archivo de lógica matemática, vol. 32 (1993), págs. 351-367". Revista de lógica simbólica . 63 (1): 331-332. doi :10.2307/2586607. ISSN  0022-4812. JSTOR  2586607.Versión HTML gratuita del autor
28. Green, Milton W. (11 de noviembre de 1964). "Función sigma de RADO de límite inferior para máquinas de Turing binarias". Actas del quinto simposio anual sobre teoría de circuitos de conmutación y diseño lógico de 1964. SWCT '64. EE. UU.: IEEE Computer Society: 91–94. doi :10.1109/SWCT.1964.3.
29. Ben-Amram, AM; Petersen, H. (2002). "Límites mejorados para funciones relacionadas con castores ocupados". Teoría de sistemas informáticos . 35 (1): 1–11. doi :10.1007/s00224-001-1052-0. MR  1879169.
30. Ligocki, Shawn (21 de junio de 2022). "BB(6, 2) > 10↑↑15". sligocki . Consultado el 4 de julio de 2024 .
31. "[2 de julio de 2024] Hemos demostrado que "BB(5) = 47.176.870"". El desafío del castor atareado . 2024-07-02 . Consultado el 2024-07-02 .
32. "El desafío del castor atareado". bbchallenge.org . Consultado el 2 de julio de 2024 .
33. Shen Lin (1963). Estudios informáticos de problemas de máquinas de Turing (tesis doctoral). Universidad Estatal de Ohio .

Referencias

• Radó, Tibor (mayo de 1962). "Sobre funciones no computables" (PDF) . Bell System Technical Journal . 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 no era computable y crecía más rápido que cualquier función computable.

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

  Los resultados de este trabajo ya habían aparecido en parte en la tesis doctoral de Lin de 1963, bajo la dirección de Radó. Lin y Radó prueban que Σ(3) = 6 y S (3) = 21 al demostrar 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 prueban automáticamente mediante un programa informático, sin embargo, 40 se prueban 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 las máquinas de Turing de 2 símbolos y 3 estados que no se detienen: árboles de Navidad y contadores. Utiliza un programa informático para demostrar que todas las máquinas, excepto 27 que funcionan durante 107 pasos, son variantes de árboles de Navidad y contadores que pueden funcionar infinitamente. Las últimas 27 máquinas (denominadas máquinas resistentes) no se detienen mediante una inspección personal realizada por el propio Brady.

• Machlin, Rona; Stout, Quentin F. (junio de 1990). "El comportamiento complejo de máquinas simples". Physica D: Nonlinear Phenomena . 42 (1–3): 85–98. Bibcode :1990PhyD...42...85M. doi :10.1016/0167-2789(90)90068-Z. hdl : 2027.42/28528 .

  Machlin y Stout describen el problema del castor atareado y muchas técnicas utilizadas para encontrarlos (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 detención de Chaitin (Ω).

• Marxen, Heiner; Buntrock, Jürgen (febrero de 1990). "Ataque al castor atareado 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 describen en detalle el método que utilizaron para encontrar estas máquinas y demostrar que muchas otras nunca se detendrán.

• Green, Milton W. (1964). Un límite inferior en la función sigma de Rado para máquinas de Turing binarias . Actas del quinto simposio anual sobre teoría de circuitos de conmutación y diseño lógico. 1964. págs. 91–94. doi :10.1109/SWCT.1964.3.

  Green construye de forma recursiva 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". Scientific American . 251 (2): 10–17.

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

• Chaitin, Gregory J. (1987). "Computing the Busy Beaver Function" (PDF) . En portada, TM; Gopinath, B. (eds.). Problemas abiertos en comunicación y computación . Springer. págs. 108–112. ISBN. 978-0-387-96621-2Archivado 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 atareado y el sentido de la vida". En Herken, Rolf (ed.). La máquina universal de Turing: un estudio de medio siglo (2.ª ed.). Viena, Nueva York: Springer-Verlag. pp. 237–254. ISBN 978-3-211-82637-9.

  En este libro, Brady (famoso en cuatro estados) describe parte de la historia de la bestia y llama a su persecución "El juego del castor atareado". Describe otros juegos (por ejemplo, los autómatas celulares y el Juego de la vida de Conway ). De particular interés es "El juego del castor atareado en dos dimensiones" (p. 247). Con 19 referencias.

• Booth, Taylor L. (1967). Máquinas secuenciales y teoría de autómatas . Nueva York: Wiley. ISBN 978-0-471-08848-6.

  Véase el capítulo 9, Máquinas de Turing. Un libro difícil, destinado a ingenieros eléctricos y especialistas técnicos. Analiza la recursión, la recursión parcial con referencia a las máquinas de Turing y el problema de la detención. Una referencia en Booth atribuye el problema del castor atareado a Rado. Booth también define el problema del castor atareado de Rado en "problemas caseros" 3, 4, 5, 6 del capítulo 9, p. 396. El problema 3 es "mostrar que el problema del castor atareado es irresoluble... para todos los valores de n".

• Ben-Amram, AM; Julstrom, BA; Zwick, U. (1996). "Una nota sobre los castores ajetreados 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 2018-07-21 . Consultado el 2022-07-07 .

  Límites entre las funciones Σ y S .

• Ben-Amram, AM; Petersen, H. (2002). "Límites mejorados para funciones relacionadas con castores ajetreados". Teoría de sistemas informáticos . 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). "La estructura 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 atareado (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 edición). Cambridge University Press. ISBN 978-0-521-87752-7.
• Kropitz, Pavel (2010). Problema del castor atareado (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 las 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 TM de 6 estados.

Enlaces externos

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