Busy beaver

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, avanza un espacio a la derecha y vuelve al estado 1.
• En el estado 1, si el símbolo actual es 1, escribe un 0, avanza un espacio a la derecha y se detiene.

Esta máquina de Turing se desplazaría hacia la derecha, intercambiando el valor de todos los bits que recorre. Dado que la cinta inicial está compuesta solo por ceros, generaría una cadena infinita de unos. Esta máquina no sería una máquina de Turing competitiva porque se ejecuta indefinidamente en una cinta en blanco.

Función de puntuación Σ

La función de puntuación cuantifica la puntuación máxima que puede alcanzar un castor ocupado de un tamaño dado. 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, ${\displaystyle \Sigma$ :\mathbb {N} \to \mathbb {N} } , se define de modo que ${\displaystyle \Sigma (n)}$ sea la puntuación máxima alcanzable (el número máximo de unos que finalmente aparecen en la cinta) entre todas las máquinas de Turing de dos símbolos y dos estados ${\displaystyle n}$ del tipo descrito anteriormente, que se detienen al iniciarse en una cinta en blanco.

Es evidente 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 isomorfismos, y por lo tanto, como máximo un número finito de tiempos de ejecución posibles.^[4]p. 880

Según la definición basada en la puntuación, cualquier máquina de Turing M de dos símbolos y dos estados que alcance la puntuación máxima (σ(M)= Σ(n)) se denomina "busy beaver" (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 todas las direcciones intercambiadas. 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.

Función del máximo número de desplazamientos S

Además de la función Σ, Radó [1962] introdujo otra función extrema para las máquinas de Turing, la función del máximo número de desplazamientos, 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 cualquier máquina de Turing de 2 símbolos y n estados que se detiene. Dado que las máquinas de Turing normales requieren un desplazamiento en cada transición o "paso" (incluida cualquier transición a un estado de parada), la función de desplazamientos máximos es, a su vez, una función del máximo de pasos.

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; por consiguiente, 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]

Lin y Radó utilizaron la siguiente relación entre Σ y S (Estudios Computacionales de Problemas de Máquinas de Turing, 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, momento en el cual cualquier máquina que aún no se haya detenido nunca se detendrá. En ese punto, al observar qué máquinas se han detenido con la mayor cantidad de 1s en la cinta (es decir, las máquinas más activas), 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, equivalentes a 2¹⁰3⁴) 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 detuvieron dentro de los 21 pasos, lograron demostrar que ninguna de esas máquinas se detendría jamás, y la mayoría de ellas seguían un patrón determinado. Esto demostró la conjetura de que S(3) = 21, y también determinó que Σ(3) = 6, valor que alcanzaron 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 el conjunto de Zermelo-Fraenkel. Para ello construyeron una máquina de Turing^[16] de 7910 estados cuyo comportamiento no puede probarse basándose en los axiomas usuales de la teoría de conjuntos (los axiomas de Zermelo-Fraenkel con el axioma de elección), bajo hipótesis de consistencia razonables (propiedad de Ramsey estacionaria, equivalente a la existencia de cardenales sutiles arbitrariamente grandes).^[17][18][19] Stefan O'Rear luego la redujo a 1919 estados, con la dependencia de la propiedad de Ramsey estacionaria eliminada,^[20][21] y más tarde a 748 estados.^[5] En julio de 2023, Riebel lo redujo a 745 estados.^[8][9] Se informan mejoras adicionales en el sitio web del BB Challenge .

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

Supóngase 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 escrita inicialmente en la cinta. Sea Double una máquina de Turing que evalúa la función n + n. Dada una cinta con n unos, producirá 2n unos en la cinta y luego se detendrá.

Sean las opciones disponibles 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₀ + n₀.

Sea BadS la composición Create_n₀ | 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₀ unos y luego la duplica, produciendo una secuencia de N unos. A continuación, EvalS producirá S(N) unos en la cinta, y finalmente borrará todos los unos y 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 cual contradice la definición de la función S(n).

La imposibilidad de calcular Σ(n) puede demostrarse de forma similar. En la demostración anterior, se debe 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 un 1.

La incomputabilidad de S(n) también se puede establecer haciendo referencia al problema de la parada en la 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 en una cinta vacía es equivalente al problema de la parada estándar y, por lo tanto, también es incomputable. Si S(n) fuera computable, se podría resolver el problema de la parada en la 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 en una cinta vacía no es computable, se deduce que S(n) también debe ser incomputable.

Incomputabilidad de espacio(n) y num(n)

Tanto las funciones ${\displaystyle {\text{espacio}}(n)}$ como ${\displaystyle {\text{num}}(n)}$ son incomputables.^[10] Esto se puede demostrar para ${\displaystyle {\text{espacio}}(n)}$ observando que cada casilla de cinta en la que una máquina de Turing escribe un uno, también debe visitarla; en otras palabras, ${\displaystyle \Sigma (n)\leq {\text{espacio}}(n)}$.^[10] Se puede demostrar que la función ${\displaystyle {\text{num}}(n)}$ es incomputable probando, por ejemplo, que ${\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 menos ${\displaystyle {\text{espacio}}(n)}$ unos contiguos en la cinta.^[10]

Diferentes números de símbolos

Una generalización sencilla 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, iniciada en una cinta inicialmente en blanco, antes de detenerse, y
2. S(n, m): el mayor número de pasos que puede dar 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 tardado en ejecutarse, 119 112 334 170 342 540 pasos antes de detenerse.^[24][25]

Máquinas de Turing no deterministas

El problema puede extenderse a una máquina de Turing no determinista buscando el sistema con el mayor número 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 necesario para encontrar una NDTM que se detenga 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 muestra el número máximo de pasos antes de la parada y el número máximo de estados únicos creados por la NDTM.

Problemas matemáticos abiertos

Además de plantear un juego matemático bastante desafiante, las funciones Σ(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 sistemáticamente 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 de n estados.^[5]

Considérese cualquier conjetura ${\displaystyle \Pi _{1}^{0}}$: cualquier conjetura que pueda ser refutada mediante un contraejemplo entre un conjunto de casos numerable (por ejemplo, la conjetura de Goldbach). Escríbase entonces un programa informático que pruebe secuencialmente esta conjetura para valores crecientes. En el caso de la conjetura de Goldbach, se consideraría cada número par igual a 4 de forma secuencial y se comprobaría si es o no la suma de dos números primos. Supóngase que este programa se simula en una máquina de Turing de n estados. Si se encuentra un contraejemplo (un número par igual a 4 que no es la suma de dos primos en el presente ejemplo), se detiene e indica que no lo es. Sin embargo, si la conjetura es verdadera, el programa nunca se detendrá. Este programa se detiene "solo" si encuentra un contraejemplo.^[5]

Ahora bien, este programa se simula en una máquina de Turing de n estados, por lo que si se conoce S(n), se puede 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, se sabe 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 probaría que la conjetura es verdadera.^[5] Así, 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.^[5]

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

• Es extremadamente difícil demostrar valores para la función del castor ocupado (y para la función del máximo de desplazamientos). Cada valor exacto conocido de S(n) se demostró enumerando cada máquina de Turing de n estados y probando si cada una se detiene o no. Habría que calcular S(n) mediante algún método menos directo para que fuera realmente útil.
• 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 ${\displaystyle ^{^{^{^{9}2}2}}2}$, es decir, 2 elevado a la 2 elevado a la 2 elevado a la 9, que es al menos 2 pentado a la 5.^[28] El valor de S(25), que es el número de pasos que el programa capaz de verificar la conjetura de Goldbach necesitaría ejecutar para dar una respuesta concluyente, es incomprensiblemente enorme, y no remotamente posible escribirlo, y mucho menos materializar una máquina capaz de ejecutar el programa en el universo observable.^[6][7]

Tesis física de Church-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] Las funciones simples de ${\displaystyle BB(n)}$ también impondrían un límite inferior a las tasas de crecimiento, así como límites superiores e inferiores a las tasas de convergencia.^[33][32]

Límites inferiores

Valores exactos y cotas inferiores y superiores

La siguiente tabla muestra los valores exactos y algunas cotas inferiores conocidas para S(n), Σ(n) y otras funciones de la máquina de Turing de dos símbolos. En esta tabla se utilizan máquinas de Turing de dos símbolos. Las entradas marcadas con "?" son al menos tan grandes como las demás entradas a la izquierda (ya que todas las máquinas de n estados son también máquinas de (n+1) estados) y no mayores que las entradas superiores (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, puesto que espacio(n) ≥ Σ(n) y Σ(6) > 2${\displaystyle \uparrow \uparrow \uparrow }$5. 47 176 870 es una cota superior para espacio(5), porque S(5) = 47 176 870 (^[3]) y S(n) ≥ espacio(n). 4098 es una cota superior para num(5), ya que Σ(5) = 4098 y Σ(n) ≥ num(n). La última entrada marcada como "?" es num(6), porque Σ(n) > (6) > 2${\displaystyle \uparrow \uparrow \uparrow }$5, pero Σ(n) ≥ num(n), lo mismo ocurre con num(7).

Más información > 2 ...

Valores de las funciones de Busy Beaver

Función	2 estados	3 estados	4 estados	5 estados	6 estados	7 estados
S(n)	6[5]	21[5]	107[5]	47 176 870[3][38]	> 2${\displaystyle \uparrow \uparrow \uparrow }$5[36]	> 2${\displaystyle \uparrow ^{11}}$2${\displaystyle \uparrow ^{11}}$3[36]
espacio(n)	4[37]	7[37]	16[37]	12289[38]	> 2${\displaystyle \uparrow \uparrow \uparrow }$5 espacio(n) ≥ Σ(n)	> 2${\displaystyle \uparrow ^{11}}$2${\displaystyle \uparrow ^{11}}$3[36]
Σ(n)	4[37]	6[37]	13[37]	4098[38][36]	> 2${\displaystyle \uparrow \uparrow \uparrow }$5[36]	> 2${\displaystyle \uparrow ^{11}}$2${\displaystyle \uparrow ^{11}}$3[36]
num(n)	4[37]	6[37]	12[37]	165[39]	?	?

Cerrar

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 mejor problema del castor ocupado, mediante una demostración formalizada en Coq.^[40][41]

Lista de castores ocupados

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 el símbolo leído de la cinta. Cada entrada es una cadena de tres caracteres que indica el símbolo a escribir en la cinta, la dirección de movimiento 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 de resultado: (comienza en la posición del texto con raya superior, termina en la posición del texto con raya inferior

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)

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 generan seis "1". A diferencia de las máquinas anteriores, esta es muy eficiente para Σ, pero no para S. (S(3) = 21, y la máquina obtiene solo cinco "1".^[15])

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.

Obsérvese 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 una tetración.