Los límites inferiores de Milton Green de la función del castor ocupado

Question

Wikipedia afirma que Milton Green demostró en 1964, que el castor ocupado función $\Sigma(n)$ tiene el límite inferior

$$\Sigma(2k)>3\uparrow^{k-2}3$$

He leído la charla sobre el artículo del castor ocupado y alguien tenía dudas sobre estos límites. No estoy muy seguro, si los límites resultaron ser verdaderos al final.

Así que mi pregunta: ¿Son los límites correctos, y si es así, hay una manera simple de entender los límites?

Otra pregunta: ¿Se conocen límites inferiores más altos para la función función castor $\Sigma(n)$ para $n\ge10$ ?

Answer 1

Puedes encontrar algunos límites inferiores más grandes en la wiki de Googology, aquí .

Algunos límites inferiores notables:

He encontrado un límite inferior $\Sigma(25) > F_{\omega+1}(6143) > $ El número de Graham. Los detalles son aquí . Wythagoras entonces mejoró la máquina para demostrar el límite inferior $\Sigma(23) > F_{\omega+1} ( F_{\omega+1}(9)) >$ El número de Graham; los detalles están en los comentarios de la página anterior.

LittlePeng9 implementó una serie de algoritmos para funciones de crecimiento rápido para proporcionar límites inferiores muy grandes, y estas máquinas de Turing también fueron optimizadas por Wythagoras. Las máquinas se enumeran aquí . Entre ellos se encuentran:

-Una implementación de la Hidra Kirby-Paris para probar $\Sigma(41) > F_{\varepsilon_0}(374676379)$ .

-Una implementación de la Hidra de Buchholz con dos etiquetas para probar $\Sigma(81,10) > F_{\vartheta(\varepsilon_{\Omega+1})}(2050)$ . Aquí $\Sigma(m,n)$ indica el mayor número de unos imprimibles por una máquina de Turing con m estados y n símbolos.

-Una implementación de la Hidra de Buchholz con etiquetas finitas para demostrar $\Sigma(134,7) > F_{\psi_{\Omega_1}(\Omega_{\omega})}(2050)$ . Podemos convertir esto en una máquina de dos símbolos con un algoritmo de conversión (ideado por LittlePeng9) que demuestra $\Sigma (3350) > F_{\psi_{\Omega_1}(\Omega_{\omega})}(2050)$ .

-Una aplicación de la Hidra de Buchholz con $\omega+1$ etiquetas para probar $\Sigma(150, 7) > F_{\psi_{\Omega_1}(\varepsilon_{\Omega_{\omega}+1})}(683)$ . El mismo algoritmo de reducción demuestra $\Sigma(3750) > F_{\psi_{\Omega_1}(\varepsilon_{\Omega_{\omega}+1})}(683)$ .

Es probable que no estés familiarizado con las notaciones de estos límites inferiores. Para entenderlos, hay que estar familiarizado con la jerarquía de crecimiento rápido y las notaciones para los ordinales grandes. Basta decir que estos números son MUY grandes, ¡haciendo que el número de Graham parezca un infinitesimal!

Tenga en cuenta que estas máquinas son bastante complejas, y son bastante difíciles de depurar ya que no se pueden ejecutar hasta el final. Por lo tanto, existe la posibilidad de que se produzcan errores.

Finalmente, Wythagoras modificó la máquina de Busy Beaver para seis estados para crear una máquina de siete estados que imprime más de $10^{10^{10^{10^{18705353}}}}$ los. La máquina está catalogada aquí y el cálculo se verifica aquí .

Answer 2

• He publicado esa pregunta "dudosa", pero (como se detalla en el página de discusión ) estos límites inferiores se desprenden efectivamente del documento de Green: $$\Sigma(2k) > 3 \uparrow^{k-2} 3 \quad (k \ge 2)$$ Obsérvese que los límites publicados por Green se expresan en términos de relaciones de recurrencia, y son algo mayores que los que da la fórmula de la flecha de Knuth, más sencilla.

• ¿Existe una forma sencilla de entenderlos? La cuestión se vuelve más bien filosófica. Si por "entenderlos" entendemos "comprender su magnitud", entonces la respuesta (al menos para $k \ge 6$ ) es "probablemente no". Harvey Friedman propuesta $2\uparrow^{4}5$ como punto de referencia, de manera que la magnitud de cualquier número al menos tan grande se considera incomprensible . Escribe que "surge un profundo nivel de incomprensibilidad. Las definiciones no son incomprensibles, pero la amplitud es incomprensible". (Para mí, esto ya es cierto de $3 \uparrow^{3} 3$ . Simplemente no puedo comprender la magnitud del número que denota una torre exponencial de trillones de $3$ s.)

• ¿Se conoce algún límite inferior más alto para $\Sigma(n)$ para $n\ge10$ ? Sí; por ejemplo aquí es un $64$ -máquina de Turing de clase BB diseñada para calcular un número mucho mayor que El número de Graham ( $G$ ). Como se muestra en el artículo, se detiene finalmente, dejando exactamente $h_{\omega+1}(h_{\omega+1}(4)) + 1 $ contiguos en la cinta, donde $h_\omega$ se define mediante una versión acelerada del jerarquía de rápido crecimiento : $$h_\alpha(n) = \begin{cases} & n+1, & \mbox{if }\alpha = 0 \\ & (h_{\alpha-1})^{n+2}(n+4), & \mbox{if }\alpha\mbox{ is a successor ordinal} \\ & (h_{\alpha[n+1]})^{n+5}(n+7), & \mbox{if }\alpha\mbox{ is a limit ordinal} \end{cases}$$ Por lo tanto, $$ \Sigma(64) \ \ge \ h_{\omega+1}(h_{\omega+1}(4)) + 1 \ \ggg \ f_{\omega+1}(f_{\omega+1}(4)) + 1 \ \ggg \ G $$ Por supuesto, esta máquina de Turing tiene una "lógica de diseño estructurada" que no requiere un Castor Ocupado, por lo que seguramente no está ni cerca de tener el número mínimo de estados necesarios para lograr resultados similares. (Por lo que sabemos, incluso $12$ estados con una lógica humanamente impenetrable podría ser suficiente).