Hispanopedia Wiki
Articulo de referencia

castor ocupado

Este "diagrama espacio-temporal" [ 1 ] muestra el estado de la cinta de memoria en una fila para los primeros 100 000 pasos de tiempo del castor ocupado de 5 estados, de arriba ...

Hispanopedia WikiContenido en espanolLectura gratuita

Este "diagrama espacio-temporal" [ 1 ] muestra el estado de la cinta de memoria en una fila para los primeros 100 000 pasos de tiempo del castor ocupado de 5 estados, de arriba a abajo. El naranja es "1", el blanco es "0" (imagen comprimida verticalmente).

En la informática teórica , el juego del castor ocupado busca encontrar un programa que termine , de un tamaño dado, que (según la definición) produzca la mayor cantidad de salida posible o se ejecute durante el mayor número de pasos. [ 2 ] Dado que es fácil concebir un programa en bucle infinito que produzca una salida infinita o se ejecute durante un tiempo infinito, dichos programas se excluyen del juego. [ 2 ] En lugar de 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 constan de una cinta infinita y un conjunto finito de estados que sirven como el "código fuente" del programa. Producir la mayor cantidad de salida se define como escribir la mayor cantidad de 1s en la cinta, también conocido como lograr la puntuación más alta, y ejecutarse durante el tiempo más largo se define como tomar la mayor cantidad de pasos para detenerse. [ 4 ] El juego del castor ocupado de n estados consiste en encontrar la máquina de Turing de mayor duración o mayor puntuación que tenga n estados y que finalmente se detenga. [ 2 ] Se supone que dichas 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 que apunten a la puntuación más alta o al tiempo de ejecución más largo, asegurándose al mismo tiempo de que la máquina se detenga eventualmente.

Decidir el tiempo de ejecución o la puntuación del n -ésimo castor ocupado no es computable . [ 4 ] De hecho, tanto las funciones Σ(n) como S(n) eventualmente se vuelven mayores que cualquier función computable . [ 4 ] Esto tiene implicaciones en la teoría de la computabilidad , el problema de la parada y la teoría de la complejidad . [ 5 ] El concepto de castor ocupado fue introducido por primera vez por Tibor Radó en su artículo de 1962, "Sobre funciones no computables". [ 4 ]

Una implicación del juego del castor ocupado es que, si fuera posible calcular las funciones Σ(n) y S(n) para todo n , esto resolvería todas las conjeturas matemáticas que pueden reducirse a un problema de parada, por ejemplo, a una forma de "¿se detiene ⟨esta máquina de Turing⟩ ? ". [ 6 ] Por ejemplo, hay una máquina de Turing de 27 estados que comprueba la conjetura de Goldbach para cada número y se detiene ante un contraejemplo; si esta máquina no se detuviera después de ejecutarse durante S(27) pasos, entonces debe ejecutarse indefinidamente, resolviendo la conjetura. [ 6 ] [ 7 ] Muchos otros problemas, incluyendo la hipótesis de Riemann (744 estados) y la consistencia de la teoría de conjuntos ZF (745 estados [ 8 ] [ 9 ] ), pueden expresarse de forma similar, donde como máximo se necesita comprobar un número infinito numerable de casos. [ 6 ]

Definición técnica

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 una 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 se etiquetan con 1, 2, ..., n , siendo el estado 1 el estado inicial, o con A , B , C , ..., siendo el estado A el estado inicial).
  • La máquina utiliza una única cinta bidireccional infinita (o ilimitada).
  • El alfabeto de la cinta es {0, 1}, donde 0 representa el símbolo en blanco.
  • La función de transición de la máquina toma dos entradas:
    • el estado actual sin parada,
    • el símbolo en la celda de cinta actual,
    y produce tres resultados:
    • 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 sobrescrito),
    • una dirección para moverse (izquierda o derecha; es decir, desplazarse a la celda de la cinta un lugar a la izquierda o a la derecha de la celda actual), y
    • un estado al que transitar (que puede ser el estado de parada).

"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 ceros), y luego iterar la función de transición hasta que se entra en el estado de parada (si es que se llega a hacerlo). Si y solo si la máquina finalmente se detiene, entonces el número de 1s que finalmente quedan en la cinta se llama puntuación de la máquina . Un castor ocupado n -ésimo , BB -n o simplemente "castor ocupado" es una máquina de Turing que gana el juego del castor ocupado de n estados. [ 6 ] Dependiendo de la definición, o bien alcanza la puntuación más alta (denotada por Σ(n) [ 4 ] ), o se ejecuta durante el tiempo más largo ( S(n) ), entre todas las demás posibles máquinas de Turing competidoras de n estados.

Ejemplo

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

  • En el estado 1, si el símbolo actual es 0, escribe un 1, muévete un espacio a la derecha y pasa al estado 1.
  • En el estado 1, si el símbolo actual es 1, escribe un 0, muévete un espacio a la derecha y pasa a la señal de ALTO.

Esta máquina de Turing se desplazaría hacia la derecha, intercambiando el valor de todos los bits que encuentra. Dado que la cinta inicial está compuesta enteramente por ceros, generaría una cadena infinita de unos. Esta máquina no sería una candidata al éxito de la máquina de Turing, ya que funciona indefinidamente en una cinta en blanco.

Funciones

En su artículo original de 1962, Radó definió dos funciones relacionadas con el juego del castor ocupado: la función de puntuación Σ(n) y la función de desplazamientos S(n). [ 4 ] Ambas toman una serie de estados de la máquina de Turing.norte{\displaystyle n}y produce la puntuación máxima alcanzable por una máquina de Turing de ese número de estados según alguna medida. La función de puntuación Σ(n) da el número máximo de 1s ynorte{\displaystyle n}Una máquina de Turing de -estados puede generar una salida 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 unanorte{\displaystyle n}La máquina de Turing de -estados puede experimentar antes de detenerse. [ 4 ] Demostró que ambas funciones eran no 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, por lo que esa notación no se utiliza en este artículo.

También se pueden definir otras funciones incomputables basándose en la medición del rendimiento de las máquinas de Turing de formas distintas al tiempo o al número máximo de unos. [ 10 ] Por ejemplo: [ 10 ]

  • La funciónnum(norte){\displaystyle {\text{num}}(n)}Se define como el número máximo de unos contiguos que una máquina de Turing que se detiene puede escribir en una cinta en blanco. En otras palabras, es el mayor número unario que una máquina de Turing de n estados puede escribir en una cinta.
  • La funciónespacio(norte){\displaystyle {\text{espacio}}(n)}Se define como el número máximo de casillas de cinta que una máquina de Turing puede leer (es decir, visitar) antes de detenerse. Esto incluye la casilla inicial, pero no una casilla a la que la máquina solo llega después de la transición de parada (si la transición de parada está anotada con una dirección de movimiento), ya que esa casilla 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.

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

Función de puntuación Σ

La función de puntuación cuantifica la puntuación máxima alcanzable por un castor trabajador en una medida dada. Esta es una función no computable , porque crece asintóticamente más rápido que cualquier función computable. [ 13 ]

La función de puntuación,Σ:norte→norte{\displaystyle \Sigma :\mathbb {N} \to \mathbb {N} } , se define de modo queΣ(norte){\displaystyle \Sigma (n)}es la puntuación máxima alcanzable (el número máximo de 1s finalmente en la cinta) entre todos los símbolos de parada de 2norte{\displaystyle n}-máquinas de Turing de estado del tipo descrito anteriormente, cuando se inician en una cinta virgen.

Está claro queΣ{\displaystyle \Sigma }es una función bien definida: para cada n , existen como máximo un número finito de máquinas de Turing de n estados como las anteriores, salvo isomorfismo, por lo tanto, como máximo un número finito de posibles tiempos de ejecución. [ 4 ] pág.  880

Según la definición basada en la puntuación, cualquier máquina de Turing M de n estados y 2 símbolos para la cual σ ( M ) = Σ( n ) (es decir, que alcanza la puntuación máxima) se denomina castor ocupado. Para cada n , existen al menos 4( n - 1)! castores ocupados de n estados. (Dado cualquier castor ocupado de n estados, se obtiene otro simplemente cambiando la dirección de desplazamiento en una transición de parada, un tercero invirtiendo uniformemente todas las direcciones de desplazamiento y un cuarto invirtiendo la dirección de parada del castor ocupado con todos los desplazamientos intercambiados. Además, una permutación de todos los estados excepto Inicio y Parada produce una máquina que alcanza la misma puntuación. Teóricamente, podría haber más de un tipo de transición que conduzca al estado de parada, pero en la práctica sería un desperdicio, ya que solo hay una secuencia de transiciones de estado que produce el resultado deseado).

No computabilidad

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

Además, esto implica que un algoritmo general no puede determinar 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 demostrada. En particular, dicho algoritmo podría usarse para construir otro algoritmo que calcularía Σ de la siguiente manera: para cualquier n dado , se probarían todas las máquinas de Turing de 2 símbolos y n estados (un número finito) hasta encontrar un castor ocupado de n estados; 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 incomputable, existen algunos valores pequeños de n para los que es posible obtener sus valores y demostrar su exactitud. No es difícil demostrar que Σ(0) = 0, Σ(1) = 1, Σ(2) = 4, y con creciente dificultad se puede demostrar que Σ(3) = 6, Σ(4) = 13 y Σ(5) = 4098 (secuencia A028444 en la OEIS ) . Σ( n ) aún no se ha determinado para ningún caso de n > 5, aunque se han establecido límites inferiores (véase la sección Valores conocidos más adelante).

Complejidad e imposibilidad de demostrar Σ

Una variante de la complejidad de Kolmogorov se define de la siguiente manera: [ 14 ] La complejidad de un número n es el número mínimo de estados necesarios para una máquina de Turing de clase BB que se detiene con un solo bloque de n 1s consecutivos en una cinta inicialmente en blanco. La variante correspondiente del teorema de incompletitud de Chaitin establece que, en el contexto de un sistema axiomático dado para los números naturales , existe un número k tal que no se puede demostrar que ningún número específico tenga una complejidad mayor que k , y por lo tanto que no se puede demostrar una cota superior específica 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 cual 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 ninguna cota 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, existe una proposición verdadera pero indemostrable de la forma Σ(10⇈10) = n , y existen infinitas proposiciones verdaderas pero indemostrables de la forma Σ(10⇈10) < n .)

Función de desplazamiento máximo 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: [ 4 ]

  • s ( M ) = el número de desplazamientos que M realiza antes de detenerse, para cualquier M ∈ E n ,
  • S ( n ) = max{ s ( M ) | M ∈ E n } = el mayor número de desplazamientos realizados por cualquiermáquina de Turing de 2 símbolos y n estados que se detiene.

Debido a que las máquinas de Turing normales requieren un cambio en cada transición o "paso" (incluida cualquier transición a un estado de parada), la función max-shifts es al mismo tiempo una función max-steps.

Radó demostró que S no es computable por la misma razón que Σ no lo es: 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, aquellos 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 crecía 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(3)=21: Para un n dado , si se conoce S ( n ), entonces todas las máquinas de Turing de n estados pueden (en principio) ejecutarse hasta S ( n ) pasos, en cuyo punto cualquier máquina que aún no se haya detenido nunca se detendrá. En ese punto, al observar qué máquinas se han detenido con la mayor cantidad de 1 en la cinta (es decir, los castores ocupados), 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 (tras conjeturar sin éxito 18), y luego simular todas las máquinas de 3 estados esencialmente diferentes (82.944 máquinas, igual a 2 10 3 4 ) durante hasta 21 pasos. Encontraron 26.073 máquinas que se detuvieron, incluyendo una que se detuvo solo después de 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, la mayoría siguiendo un patrón determinado. Esto demostró la conjetura de que S (3) = 21, y también determinó que Σ(3) = 6, valor alcanzado por varias máquinas, todas deteniéndose después de 11 a 14 pasos. [ 15 ]

En 2016, Adam Yedidia y Scott Aaronson obtuvieron la primera cota superior (explícita) sobre el mínimo n para el cual S( n ) es indemostrable en ZFC . Para ello, construyeron una máquina de Turing de 7910 estados [ 16 ] 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 razonables (propiedad de Ramsey estacionaria, equivalente a la existencia de cardinales sutiles arbitrariamente grandes ). [ 17 ] [ 18 ] [ 19 ] Stefan O'Rear la redujo entonces a 1919 estados, eliminando la dependencia de la propiedad de Ramsey estacionaria, [ 20 ] [ 21 ] y posteriormente a 748 estados. [ 5 ] En julio de 2023, Riebel la redujo a 745 estados. [ 8 ] [ 9 ] Se informan mejoras adicionales en el sitio web de BB Challenge .

Demostración de la imposibilidad de computar S ( n ) y Σ( n )

Supongamos que S ( n ) es una función computable y sea EvalS una máquina de Turing que evalúa S ( n ). Dada una cinta con n unos, producirá S ( n ) unos en la cinta y luego se detendrá. Sea Clean una máquina de Turing que limpia la secuencia de unos 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 unos , producirá 2n unos 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₀ unos 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 0 + n 0 .

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

La incomputabilidad de Σ( n ) puede demostrarse de forma similar. En la demostración anterior, hay que intercambiar la máquina EvalS por EvalΣ y Clean por Increment , una máquina de Turing simple que busca el primer 0 en la cinta y lo reemplaza por 1.

La incomputabilidad de S ( n ) también puede establecerse haciendo referencia al problema de la parada con cinta vacía. Este problema consiste en decidir, para cualquier máquina de Turing, si se detendrá o no al comenzar con una cinta vacía. El problema de la parada con cinta vacía es equivalente al problema de parada estándar y, por lo tanto, también es incomputable. Si S ( n ) fuera computable, podríamos resolver el problema de la parada con cinta vacía simplemente ejecutando cualquier máquina de Turing con n estados durante S ( n ) pasos; si aún no se ha detenido, nunca lo hará. Por lo tanto, dado que el problema de la parada con cinta vacía no es computable, se deduce que S ( n ) también debe ser incomputable.

Imposibilidad de computar space(n) y num(n)

Ambosespacio(norte){\displaystyle {\text{espacio}}(n)}ynum(norte){\displaystyle {\text{num}}(n)}Las funciones son incomputables. [ 10 ] Esto se puede demostrar paraespacio(norte){\displaystyle {\text{espacio}}(n)}al observar que en cada casilla de cinta una máquina de Turing escribe un uno, también debe visitar: en otras palabras,Σ(norte)≤espacio(norte){\displaystyle \Sigma (n)\leq {\text{espacio}}(n)}. [ 10 ] Elnum(norte){\displaystyle {\text{num}}(n)}Se puede demostrar que una función es incomputable probando, por ejemplo, queespacio(norte)<num(3norte+3){\displaystyle {\text{espacio}}(n)<{\text{num}}(3n+3)}: 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 la use para escribir al menosespacio(norte){\displaystyle {\text{espacio}}(n)}contiguas a la cinta. [ 10 ]

Generalizaciones

Se pueden definir análogos de la función de desplazamiento 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. [ 11 ] Por ejemplo, el juego del castor ocupado 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 hacia la izquierda y hacia la derecha. [ 11 ] Alternativamente, se puede definir una "función del castor ocupado" para diversos modelos de computación con complejidad de Kolmogorov . [ 11 ] Esto se hace tomandoBB(norte){\displaystyle {BB}(n)}ser el entero más grandemetro{\displaystyle m}de tal manera queKL(metro)≤norte{\displaystyle K_{L}(m)\leq n}, dóndeKL(metro){\displaystyle K_{L}(m)}es la duración del programa más corto enL{\displaystyle L}que producemetro{\displaystyle m}:BB(norte){\displaystyle {BB}(n)}es por tanto el entero más grande un programa con longitudnorte{\displaystyle n}o menos puede generar enL{\displaystyle L}. [ 11 ]

La máquina de 6 estados y 2 símbolos 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. Por lo tanto, para la clase de Máquina de Turing de Inversión (RTM), [ 22 ] S RTM (6) ≥47 339 970 y Σ RTM (6) ≥6147 . Asimismo, podríamos definir un análogo de la función Σ para máquinas de registro como el número más grande que puede estar presente en cualquier registro al detenerse, para un número dado de instrucciones. [ 23 ]

Diferentes cantidades de símbolos

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

  1. Σ( n , m ): el mayor número de valores distintos de cero que puede imprimir una máquina de n estados y m símbolos que se inicia 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 iniciada en una cinta inicialmente en blanco antes de detenerse. [ 11 ]

Por ejemplo, la máquina de 3 estados y 3 símbolos que más tiempo ha funcionado encontrada hasta ahora funciona119 112 334 170 342 540 pasos antes de detenerse . [ 24 ] [ 25 ]

Máquinas de Turing no deterministas

El problema puede extenderse a 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. [ 12 ] La cuestión de si una NDTM dada se detendrá sigue siendo computacionalmente irreducible, y el cálculo requerido para encontrar un castor ocupado de NDTM es significativamente mayor que en 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 da 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 Σ(n) y S ( n ) del castor ocupado ofrecen un enfoque completamente nuevo para resolver problemas de matemáticas puras. Muchos problemas abiertos en matemáticas podrían, en teoría, pero no en la práctica, resolverse de manera sistemática dado el valor de S ( n ) para un n suficientemente grande . [ 6 ] [ 26 ] Teóricamente hablando, el valor de S(n) codifica la respuesta a todas las conjeturas matemáticas que pueden ser verificadas en tiempo infinito por una máquina de Turing con menos o igual a n estados. [ 5 ]

Considere cualquierΠ10{\displaystyle \Pi _{1}^{0}}Conjetura : cualquier conjetura que pueda refutarse mediante un contraejemplo entre un número contable de casos (por ejemplo, la conjetura de Goldbach ). Escriba un programa informático 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 comprobarí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 que es cierto. Sin embargo, si la conjetura es verdadera, nuestro programa nunca se detendrá. (Este programa se detiene solo si encuentra un contraejemplo). [ 5 ]

Ahora bien, este programa se simula mediante una máquina de Turing de n estados, por lo que si conocemos S ( n ) podemos decidir (en un tiempo finito) si se detendrá o no simplemente ejecutando 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, que no hay contraejemplos a la conjetura dada (es decir, no hay números pares que no sean la suma de dos primos). Esto demostraría que la conjetura es verdadera. [ 5 ] Así, valores específicos (o cotas superiores) para S ( n ) podrían, en teoría, usarse para resolver sistemáticamente muchos problemas abiertos en matemáticas. [ 5 ]

Sin embargo, los resultados actuales sobre el problema del castor ocupado sugieren que esto no será práctico por dos razones:

  • Resulta extremadamente difícil demostrar los valores de la función del castor ocupado (y de la función de desplazamiento máximo). Cada valor exacto conocido de S ( n ) se demostró enumerando todas las máquinas de Turing de n estados y comprobando si cada una se detiene o no. Para que S ( n ) sea realmente útil, habría que calcularlo mediante un método menos directo.
  • Los valores de S(n) y otras funciones de castor ocupado se vuelven muy grandes, muy rápidamente. Mientras que el valor de S(5) es solo 47.176.870, [ 27 ] el valor de S(6) es más que 9222{\displaystyle ^{^{^{^{9}2}2}}2}, es decir, 2 tetrado al 2 tetrado al 2 tetrado al 9 que es al menos 2 pentado al 5. [ 28 ] El valor de S(25), 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 enorme, y no remotamente posible escribirlo, y mucho menos ejecutar una máquina para ello, en el universo observable. [ 6 ] [ 7 ]

Coherencia de las teorías

Otra propiedad de S(n) es que ninguna teoría aritméticamente sólida y computacionalmente axiomatizada puede probar todos los valores de la función. Específicamente, dada una teoría computable y aritméticamente sólidaT{\displaystyle T}, hay un númeronorteT{\displaystyle n_{T}}de tal manera que para todosnorte≥norteT{\displaystyle n\geq n_{T}}, ninguna declaración de la formaS(norte)=k{\displaystyle S(n)=k}se puede probar enT{\displaystyle T}. [ 5 ] Esto implica que para cada teoría hay un valor máximo específico de S(n) que puede probar. Esto es cierto porque para cada uno de estosT{\displaystyle T}, una máquina de Turing connorteT{\displaystyle n_{T}}Los estados pueden diseñarse para enumerar todas las pruebas posibles enT{\displaystyle T}. [ 5 ] Si la teoría es inconsistente, entonces todas las afirmaciones falsas son demostrables, y a la máquina de Turing se le puede dar la condición de detenerse si, y solo si, encuentra una prueba de, por ejemplo,0=1{\displaystyle 0=1}. [ 5 ] Cualquier teoría que demuestre el valor deS(norteT){\displaystyle S(n_{T})}demuestra su propia consistencia, violando el segundo teorema de incompletitud de Gödel . [ 5 ] Esto puede usarse para colocar varias teorías en una escala, por ejemplo los diversos axiomas cardinales grandes en ZFC : si cada teoríaT{\displaystyle T}se le asigna como su númeronorteT{\displaystyle n_{T}}, teorías con valores más grandes denorteT{\displaystyle n_{T}}demostrar la consistencia de las que están por debajo de ellas, colocando todas esas teorías en una escala infinita numerable. [ 5 ]

Ejemplos notables

  • Se ha construido una máquina de Turing binaria de 745 estados que se detiene si y solo si ZFC es inconsistente. [ 8 ] [ 9 ]
  • Se ha construido una máquina de Turing de 744 estados que se detiene si y solo si la hipótesis de Riemann es falsa. [ 20 ] [ 6 ]
  • 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 posteriormente a una máquina de 27 estados, [ 20 ] [ 6 ] luego a una de 25 estados, y más tarde se demostró y verificó formalmente en el lenguaje de demostración de teoremas Lean 4. [ 7 ]
  • Se ha construido una máquina de Turing de 15 estados que se detiene si y solo si la siguiente conjetura formulada por Paul Erdős en 1979 es falsa: para todo n > 8 hay al menos un dígito 2 en la representación en base 3 de 2 n . [ 29 ] [ 30 ]
  • Se ha descubierto una máquina de Turing de 6 estados que se detiene si y solo si se aplican repetidamenteincógnitanorte+1=⌊3incógnitanorte2⌋+2{\textstyle x_{n+1}=\left\lfloor {\frac {3x_{n}}{2}}\right\rfloor +2}Comenzando desde 4, siempre produce el doble de valores impares que de valores pares. Más tarde se le denominó "Antihydra". [ 31 ]

La Iglesia física: tesis de Turing

Las propiedades de crecimiento de la función Busy Beaver tienen implicaciones para el comportamiento de los sistemas físicos, asumiendo la veracidad de la tesis física de Church-Turing . Si la tesis física de Church-Turing es válida, y todas las funciones físicamente computables son Turing-computables, entonces ninguna magnitud física directamente medible puede crecer más rápido que la función Busy Beaver, ya que ninguna función Turing-computable puede crecer más rápido que ella. [ 32 ] Funciones simples deBB(norte){\displaystyle BB(n)}También impondría un límite inferior a las tasas de crecimiento, así como límites superiores e inferiores a las tasas de convergencia. [ 33 ] [ 32 ]

Resultados conocidos

límites inferiores

Máquinas verdes

En 1964, Milton Green desarrolló una cota inferior para la variante de conteo de 1s de la función del castor ocupado, 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 la describieron como "una cota inferior no trivial (no recursiva primitiva)". [ 34 ] Esta cota inferior se puede calcular, pero es demasiado compleja para expresarla como una sola expresión en términos de n . [ 35 ] Esto se hizo con un conjunto de máquinas de Turing, cada una de las cuales demostró la cota inferior para un cierto n . [ 35 ] Cuando n = 8 , el método da

Σ(8)≥3×(7×392−1)/2≈8.248×1044.{\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 2026) sobreΣ(6){\displaystyle \Sigma (6)}es2↑ ↑ ↑5{\displaystyle 2\uparrow \uparrow \uparrow 5}, donde el↑{\displaystyle \uparrow }'s representan la notación de flecha hacia arriba de Knuth . [ 36 ] Esto representa2↑ ↑2↑ ↑2↑ ↑4{\displaystyle 2\uparrow \uparrow 2\uparrow \uparrow 2\uparrow \uparrow 4}. El valor deΣ(8){\displaystyle \Sigma (8)}Es probable que sea mucho más grande que eso.

El límite inferior de Green se demostró mediante una construcción recursiva de una serie de máquinas de Turing, cada una de las cuales estaba compuesta 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. [ 35 ] Definiendo el valor de lanorte{\displaystyle N}-estado competidor ocupado-castaño en una cinta que contienemetro{\displaystyle m}los que seránBnorte(metro){\displaystyle B_{N}(m)}(el resultado final de cada máquina es su valor enmetro=0{\displaystyle m=0}, porque una cinta en blanco tiene 0 unos), las relaciones de recursión son las siguientes: [ 35 ]Bnorte(0)=1,B1(metro)=metro+1,Bnorte(metro)=1+Bnorte−2(1+Bnorte(metro−1)).{\displaystyle {\begin{aligned}B_{N}(0)&=1,\\B_{1}(m)&=m+1,\\B_{N}(m)&=1+B_{N-2}(1+B_{N}(m-1)).\end{aligned}}} Esto da lugar a dos fórmulas para calcular el límite inferior.GRAMO(norte){\displaystyle G(N)}dado por el ⁠norte{\displaystyle N}máquina : GRAMO(norte)=Bnorte−2(Bnorte−2(1)) para impar norte, yGRAMO(norte)=1+Bnorte−3(1+Bnorte−3(1)) incluso norte.{\displaystyle {\begin{aligned}G(N)&=B_{N-2}(B_{N-2}(1)){\text{ for odd }}N,{\text{ and}}\\G(N)&=1+B_{N-3}(1+B_{N-3}(1)){\text{ for even }}N.\end{aligned}}}

Límite inferior de GreenGRAMO(norte){\displaystyle G(N)}También puede estar relacionado con la función de Ackermann . En particular, A(norte,norte)<GRAMO(4norte+3)<A(2norte+1,4){\displaystyle A(N,N)<G(4N+3)<A(2N+1,4)} para todos los enteros positivosnorte{\displaystyle N}⁠ . [ 37 ]

Relaciones entre las funciones del castor ocupado

Trivialmente, S ( n ) ≥ Σ( n ) porque una máquina que escribe Σ( n ) unos debe tomar al menos Σ( n ) pasos para hacerlo. [ 37 ] Es posible dar una serie de cotas superiores para el tiempo S ( n ) con el número de unos Σ( n ) :

  • S(norte)≤(norte+1)×Σ(5norte)×2Σ(5norte){\displaystyle S(n)\leq (n+1)\times \Sigma (5n)\times 2^{\Sigma (5n)}} (Rado [ 37 ] )
  • S(norte)≤Σ(9norte){\displaystyle S(n)\leq \Sigma (9n)} (Buro [ 37 ] )
  • S(norte)≤(2norte−1)×Σ(3norte+3){\displaystyle S(n)\leq (2n-1)\times \Sigma (3n+3)} (Ben-Amram, Julstrom y Zwick [ 37 ] )

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 mayor número unario que puede generar), es posible demostrar que [ 37 ] [ 10 ]

num⁡(norte)<Σ(norte)S(norte)<num⁡(norte+o(norte))S(norte)<num⁡(3norte+6){\displaystyle {\begin{aligned}\operatorname {num} (n)&<\Sigma (n)\\S(n)&<\operatorname {num} (n+o(n))\\S(n)&<\operatorname {num} (3n+6)\end{aligned}}}

Ben-Amram y Petersen, 2002, también dan una cota asintóticamente mejorada en S ( n ) . Existe una constante c tal que para todo n ≥ 2 , [ 37 ]

S(norte)≤Σ(norte+⌈8norteregistro2⁡norte⌉+do).{\displaystyle S(n)\leq \Sigma \left(n+\left\lceil {\frac {8n}{\log _{2}n}}\right\rceil +c\right).}

Valores exactos y límites inferiores y superiores

La siguiente tabla enumera los valores exactos y algunos límites inferiores conocidos para S ( n ), Σ( n ) y varias otras funciones de castor ocupado. En esta tabla, se utilizan máquinas de Turing de 2 símbolos. Las entradas marcadas con "?" son al menos tan grandes como las demás entradas a la izquierda (porque todas las máquinas de n estados son también máquinas de (n+1) estados), y no mayores que las entradas que están encima de ellas (porque S(n) ≥ espacio(n) ≥ Σ(n) ≥ num(n)). Por lo tanto, se sabe que espacio(6) es mayor que 2↑ ↑ ↑{\displaystyle \uparrow \uparrow \uparrow }5, como espacio(n) ≥ Σ(n) y Σ(6) > 2↑ ↑ ↑{\displaystyle \uparrow \uparrow \uparrow }5.47 176 870 es un límite superior para 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 y Σ(n) ≥ num(n). La última entrada listada como "?" es num(6), porque Σ(6) > 2↑ ↑ ↑{\displaystyle \uparrow \uparrow \uparrow }5, pero Σ(n) ≥ num(n), lo mismo para num(7).

El problema del castor ocupado de 5 estados fue descubierto por Heiner Marxen y Jürgen Buntrock en 1989, pero no fue hasta 2024 que un colectivo matemático aficionado en línea lo reconoció como el quinto castor ocupado ganador, utilizando una prueba formalizada en Rocq . [ 40 ] [ 41 ]

Lista de castores ocupados

Diagrama espacio-temporal a escala reducida de la máquina de Turing de cinco estados. El diagrama se ha modificado para mostrar únicamente los pasos que modifican la cinta, lo que da lugar a la aparición de formas triangulares. Los triángulos verdes y amarillos indican las regiones donde la máquina de Turing se desplaza de un lado a otro; el tiempo empleado es proporcional a las áreas de estos triángulos de color. La fila inferior muestra un fragmento de la cinta y el cabezal de lectura/escritura al detenerse.

Estas 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 la mejor cota inferior conocida 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 debe escribir en la cinta, la dirección en la que se debe mover y el nuevo estado (en ese orden). El estado de parada se muestra como H.

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

Clave del resultado: (comienza en la posición resaltada , termina 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).

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

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 0 0 (107 pasos, trece "1" en total)

Este "diagrama espacio-temporal" [ 1 ] muestra el estado de la cinta de memoria en una fila para los primeros 100 000 pasos de tiempo del castor ocupado de 5 estados, de arriba a abajo. El naranja es "1", el blanco es "0" (imagen comprimida verticalmente).

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 cualitativamente similar a la evolución de algunos autómatas celulares .

Resultado: más de 2↑↑↑5 "1" en más de 2↑↑↑5 pasos, donde 2↑↑↑5 = 2↑↑2↑↑2↑↑2↑↑2 y ↑↑ representa tetración .

Visualizaciones

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

Evolución de castores ocupados con 1 a 4 estados
Reglas para el castor ocupado de un solo estado
Reglas para el castor ocupado de dos estados
Reglas para el castor ocupado de 3 estados
Reglas para el castor ocupado de 4 estados
Evolución del castor ocupado de un estado hasta detenerse. El estado inicial desencadena una parada, en la que se escribe un único "1" antes de la terminación.
Evolución del castor ocupado de 2 estados hasta detenerse
Evolución del castor ocupado de 3 estados hasta detenerse
Evolución del castor ocupado de 4 estados hasta detenerse. La línea inferior de la imagen izquierda se ajusta a la línea superior de la imagen derecha. El último paso escribe "1" antes de detenerse (no se muestra).

Véase también

Notas

  1. 1 2 "Historia # diagramas espacio-temporales" . El desafío del castor ocupado . Recuperado el 9 de julio de 2024 .
  2. 1 2 3 4 5 Weisstein, Eric W. "Busy Beaver" . Wolfram MathWorld . Archivado del original el 7 de diciembre de 2023. Recuperado el 21 de noviembre de 2023 .
  3. 1 2 3 Brubaker, Ben (2 de julio de 2024). "Matemáticos aficionados encuentran la quinta máquina de Turing 'Busy Beaver'" . Quanta Magazine . Recuperado el 3 de julio de 2024 .
  4. 1 2 3 4 5 6 7 8 9 10 11 12 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 . Archivado (PDF) del original el 12 de octubre de 2021. Recuperado el 7 de julio de 2022 .
  5. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Aaronson, Scott (29 de septiembre de 2020). " The Busy Beaver Frontier" (PDF) . SIGACT News . 51 (3): 32– 54. doi : 10.1145/3427361.3427369 . ISSN 0163-5700 . Archivado del original (PDF) el 5 de julio de 2022. 
  6. 1 2 3 4 5 6 7 8 Pavlus, John (10 de diciembre de 2020). "Cómo los programas informáticos más lentos revelan los límites fundamentales de las matemáticas" . Quanta Magazine . Archivado del original el 10 de diciembre de 2020. Recuperado el 11 de diciembre de 2020 .
  7. 1 2 3 Leng, Yijun. "Repositorio de GitHub 'goldbach_tm27'" . GitHub .
  8. 1 2 3 Aaronson, Scott (5 de julio de 2023). "La vida, los blogs y la función Busy Beaver continúan" . Shtetl-Optimized . Archivado del original el 28 de agosto de 2023. Recuperado el 27 de agosto de 2023 .
  9. 1 2 3 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 . Archivado (PDF) del original el 17 de septiembre de 2024. Recuperado el 24 de septiembre de 2024 .
  10. 1 2 3 4 5 6 7 Ben-Amram, AM; Julstrom, BA; Zwick, U. (1 de agosto de 1996). "Una nota sobre castores ocupados y otras criaturas" . Teoría de sistemas matemáticos . 29 (4): 375– 386. doi : 10.1007/BF01192693 . ISSN 1433-0490 . 
  11. 1 2 3 4 5 6 7 8 Aaronson, Scott (2 de julio de 2024). "BusyBeaver(5) ahora se sabe que es 47,176,870" . Shtetl-Optimized . Recuperado el 4 de julio de 2024 .
  12. 1 2 3 Wolfram, Stephen (4 de febrero de 2021). "Máquinas de Turing multidireccionales" . www.wolframphysics.org . Archivado del original el 7 de julio de 2022. Recuperado el 7 de julio de 2022 .
  13. ↑ Chaitin 1987 , pág. 2.
  14. ↑ Boolos, Burgess y Jeffrey, 2007. "Computabilidad y lógica"
  15. 1 2 3 Lin, Shen; Rado, Tibor (abril de 1965). "Estudios computacionales de problemas de máquinas de Turing" . Journal of the ACM . 12 (2): 196– 212. doi : 10.1145/321264.321270 . S2CID 17789208 . 
  16. ↑ Yedidia, Adam; Aaronson, Scott (mayo de 2016). "Una máquina de Turing relativamente pequeña cuyo comportamiento es independiente de la teoría de conjuntos". arXiv : 1605.04343 [ cs.FL ].
  17. ↑ Aron, Jacob (11 de mayo de 2016). "Esta máquina de Turing debería funcionar indefinidamente a menos que las matemáticas estén equivocadas" . New Scientist . Archivado del original el 20 de octubre de 2016. Consultado el 25 de septiembre de 2016 .
  18. ↑ La versión del 3 de mayo contenía 7918 estados: Aaronson, Scott (3 de mayo de 2016). "El número 8000 de Busy Beaver elude la teoría de conjuntos ZF" . Shtetl-Optimized . Archivado del original el 27 de septiembre de 2016. Recuperado el 25 de septiembre de 2016 .
  19. ↑ Friedman, Harvey M. (15 de enero de 2001). "Cardinales sutiles y ordenamientos lineales" . Annals of Pure and Applied Logic . 107 (1): 1– 34. doi : 10.1016/S0168-0072(00)00019-1 . ISSN 0168-0072 . 
  20. 1 2 3 Aaronson, Scott (3 de mayo de 2016). "Tres anuncios" . Shtetl-Optimized . Recuperado el 27 de abril de 2018 .
  21. ↑ "sorear/metamath-turing-machines: Enumeradores de pruebas metamatemáticas y otras cosas" . GitHub . 13 de febrero de 2019. Archivado del original el 17 de abril de 2021. Recuperado el 19 de mayo de 2018 .
  22. ↑ "Máquina de Turing inversa" . skelet.ludost.net . Consultado el 10 de febrero de 2022 .
  23. ↑ "A060843 - OEIS" . oeis.org . Consultado el 19 de febrero de 2026 .
  24. ↑ Las competiciones Busy Beaver de Pascal Michel se archivaron el 6 de octubre de 2023 en la página de Wayback Machine que enumera a los mejores contendientes conocidos.
  25. ↑ Michel, Pascal (14 de diciembre de 2015). "Problemas en teoría de números a partir de la competencia del castor ocupado". Métodos lógicos en informática . 11 (4): 10.
  26. ↑ Chaitin 1987 , pág. 3.
  27. ↑ Bischoff, Manon (25 de julio de 2024). "Los matemáticos finalmente han encontrado al quinto 'castor más ocupado'"." . Scientific American . Consultado el 10 de septiembre de 2025 .
  28. ↑ Aaronson, Scott (28 de junio de 2025). "BusyBeaver(6) es realmente bastante grande" . Shtetl-Optimized . Recuperado el 16 de julio de 2025 .
  29. ↑ Stérin, Tristan; Woods, Damien (2021). "Dureza del castor ocupado valor BB(15)". arXiv : 2107.12475 [ cs.LO ].
  30. ↑ Erdös, Paul (1979). « Algunos problemas poco convencionales en teoría de números» . Mathematics Magazine . 52 (2): 67– 70. doi : 10.1080/0025570X.1979.11976756 . JSTOR 2689842. Archivado del original el 13 de junio de 2022. Recuperado el 7 de julio de 2022 . 
  31. ↑ "Antihydra" . BusyBeaverWiki . Consultado el 18 de junio de 2025 .
  32. 1 2 Ord, Toby (2024). "Límites en las tasas de crecimiento y convergencia de todos los procesos físicos". arXiv : 2410.10928 [ physics.hist-ph ].
  33. ↑ Karmela Padavic-Callaghan (1 de noviembre de 2024). "Puede que exista un límite de velocidad cósmico sobre la rapidez con la que algo puede crecer" . New Scientist .
  34. ↑ Brady, Allen H. (marzo de 1998). "Heiner Marxen y Jürgen Buntrock. Atacando al castor ocupado 5. Boletín de la Asociación Europea de Ciencias de la Computación Teórica, n.º 40 (febrero de 1990), págs. 247–251. – Pascal Michel. Competencia del castor ocupado y problemas tipo Collatz. Archivo de lógica matemática, vol. 32 (1993), págs. 351–367" . The Journal of Symbolic Logic (reseña de libro). 63 (1): 331–332 . doi : 10.2307/2586607 . ISSN 0022-4812 . JSTOR 2586607. Archivado del original el 5 de julio de 2024. Recuperado el 5 de julio de 2024 .  Versión HTML gratuita del autor. Archivada el 9 de octubre de 2006 en Wayback Machine.
  35. 1 2 3 4 Green, Milton W. (11 de noviembre de 1964). "Una cota inferior de la función sigma de RADO para máquinas de Turing binarias". Actas de 1964 del Quinto Simposio Anual sobre Teoría de Circuitos de Conmutación y Diseño Lógico . IEEE Computer Society. págs. 91–94 . doi : 10.1109/SWCT.1964.3 . 
  36. 1 2 3 4 5 6 7 8 Michel, Pascal. "Estudio histórico de Busy Beavers" . Recuperado el 24 de enero de 2026 .
  37. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Ben-Amram, AM; Petersen, H. (2002). "Límites mejorados para funciones relacionadas con castores ocupados". Theory of Computing Systems . 35 (1): 1– 11. doi : 10.1007/s00224-001-1052-0 . MR 1879169 . 
  38. 1 2 3 Blanchard, Justin; Briggs, Daniel; Deka, Konrad; Fenner, Nathan; Forster, Yannick; Georgiev, Georgi; Casa, Mateo L.; Cazador, Raquel; Iijil; Kądziołka, Maja; Kropitz, Pavel; Ligocki, Shawn; mxdis; Naściszewski, Mateusz; savask; Stérin, Tristán; Xu, Chris; Yuen, Jason; Zimmermann, Théo (15 de septiembre de 2025). "Determinación del quinto valor de Busy Beaver". arXiv : 2509.12337 [ cs.LO ].
  39. ↑ "0RB1LD_1LC1RB_1LD1RE_1LA1LE_1LZ0RC - BusyBeaverWiki" . wiki.bbchallenge.org . Consultado el 17 de julio de 2026 .
  40. ↑ " [ 2 de julio de 2024 ] Hemos demostrado que 'BB(5) = 47.176.870'" . El desafío del castor ocupado . 2 de julio de 2024. Archivado del original el 2 de julio de 2024 . Recuperado el 2 de julio de 2024 .
  41. ↑ Brubaker, Ben (2 de julio de 2024). "Matemáticos aficionados encuentran la quinta máquina de Turing 'Busy Beaver'" . Quanta Magazine . Recuperado el 4 de febrero de 2026 .
  42. ↑ Shen Lin (1963). Estudios computacionales 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 . Archivado (PDF) del original el 12 de octubre de 2021. Recuperado el 7 de julio de 2022 .
    Fue aquí donde Radó definió por primera vez el problema del castor ocupado y demostró que era incomputable y que crecía más rápido que cualquier función computable.
  • Lin, Shen; Radó, Tibor (abril de 1965). "Estudios computacionales de problemas de máquinas de Turing" . Journal of the ACM . 12 (2): 196– 212. doi : 10.1145/321264.321270 . S2CID 17789208 . 
    Los resultados de este trabajo ya habían aparecido parcialmente 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 probando 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 demuestran automáticamente mediante un programa informático; sin embargo, 40 se demuestran 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" . Mathematics of Computation . 40 (162): 647–665 . doi : 10.1090/S0025-5718-1983-0689479-6 . JSTOR 2007539 . 
    Brady demuestra que Σ(4) = 13 y S (4) = 107. 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 contadores. Utiliza un programa informático para demostrar que todas las máquinas, excepto 27 que se ejecutan durante más de 107 pasos, son variantes de árboles de Navidad y contadores que pueden ejecutarse infinitamente. Las últimas 27 máquinas (conocidas como "resistencias"), según la propia inspección de Brady, no se detienen.
  • Machlin, Rona; Stout, Quentin F. (junio de 1990). "El comportamiento complejo de las 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 . Archivado del original el 30 de enero de 2012. Recuperado el 7 de julio de 2022 .
    Machlin y Stout describen el problema del castor ocupado y diversas técnicas para encontrar castores ocupados (que aplican a 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). "Attacking the Busy Beaver 5" . Boletín de la EATCS . ​​40 : 247–251 . Archivado del original el 9 de octubre de 2006. Recuperado 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.
  • Green, Milton W. (1964). "Una cota inferior para la función sigma de RADO en 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 . Archivado del original el 3 de febrero de 2019. Consultado el 7 de julio de 2022 . 
    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í una cota 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 más trabajadora". Scientific American . 251 (2): 10– 17.
    Alexander Dewdney describe los programas de castores trabajadores 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). "Cálculo de la función Busy Beaver" (PDF) . En Cover, TM; Gopinath, B. (eds.). Problemas abiertos en comunicación y computación . Springer. pp. 108–112 . ISBN  978-0-387-96621-2Archivado del original (PDF) el 30 de diciembre de 2017. Consultado el 7 de julio de 2022 .
  • Brady, Allen H. (1995). «El juego del castor trabajador y el significado de la vida». En Herken, Rolf (ed.). La máquina de Turing universal: un estudio de medio siglo (2.ª  ed.). Viena, Nueva York: Springer-Verlag. pp. 237–254 . ISBN  978-3-211-82637-9.
    En esta obra, Brady (conocido por su trayectoria en cuatro estados) describe parte de la historia de la bestia y denomina 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.
  • 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 complejo, dirigido a ingenieros eléctricos y técnicos especializados. Trata sobre recursión, recursión parcial con referencia a las máquinas de Turing y el problema de la parada. Una referencia en Booth atribuye el problema del castor ocupado a Rado. Booth también define el problema del castor ocupado de Rado en los "problemas de casa" 3, 4, 5 y 6 del capítulo 9, pág.  396. El problema 3 consiste en "demostrar que el problema del castor ocupado es irresoluble... para todos los valores de n".
  • Ben-Amram, AM; Petersen, H. (2002). "Límites mejorados para funciones relacionadas con Busy Beavers". Theory of Computing Systems . 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 lo tanto una demostración para el 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.). Cambridge University Press. ISBN 978-0-521-87752-7.
  • Kropitz, Pavel (2010). Problema del castor ocupado (PDF) (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 mediante ejecución paralela en 31 computadoras de 4 núcleos y, finalmente, los mejores resultados para la TM de 6 estados.
  • 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.
  • El estudio histórico de Pascal Michel sobre los resultados del estudio del castor trabajador incluye también los mejores resultados y algunos análisis.
  • Definición de la clase RTM - Máquinas de Turing de Inversión, subclase simple y fuerte de las TM.
  • " El problema del castor ocupado: un nuevo ataque del milenio " ( archivado ) en el Laboratorio RAIR de Rensselaer. Este trabajo halló varios récords nuevos y estableció varios valores para la formalización cuádruple.
  • Archivo 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 en Busy Beavers" . sligocki . Recuperado el 12 de julio de 2022 .
  • Aaronson, Scott (1999), ¿Quién puede nombrar el número mayor?
  • Weisstein, Eric W. "Busy Beaver" . MathWorld .
  • Máquinas de Turing Busy Beaver - Computerphile , YouTube
  • Pascal Michel. La competencia del castor trabajador: un estudio histórico . 70 páginas. 2017. <hal-00396880v5>
  • Secuencia OEIS A060843 (Problema del castor ocupado)
  • Página wiki del desafío Busy Beaver