He aprendido que la función del castor ocupado crece muy rápidamente.
Los primeros 4 valores son conocidos.
Me gustaría saber si hay algún límite superior conocido para
$$\Sigma(n)$$
para algunos $n\ge 5$ .
Además, ¿qué probabilidad hay de que $\Sigma(5) = 4098$ ?
¿Y qué tan grande es $\Sigma(6)$ ¿se cree que es?
No hay computable límite superior de la función del castor ocupado, así que no esperes que haya ninguna forma agradable para un límite superior de la misma. En particular, si hubiera una cota superior computable, entonces podríamos resolver el problema de la parada: si hacemos funcionar una máquina durante un número de pasos hasta que pase la cota superior correspondiente, sabemos que no se detiene. Por lo tanto, dicho número no puede ser computado - y hay que señalar que esto implica, en teoría (¡pero tan lejos de la práctica!) que conocer un límite superior nos permite calcular el valor real, ya que podemos eliminar, en tiempo finito, las máquinas que no se detienen.
Hay este La página parece tener una lista de todos los casos difíciles para encontrar ese valor de $\Sigma(5)$ - Yo supondría que alguien, en algún momento trató de hacerlos funcionar a todos durante un largo período de tiempo, y no se detuvieron, lo que podría sugerir que no se detienen, pero la especulación podría no ser sabia ya que, "Bueno, dudo que el castor ocupado sea que grande" no es una buena heurística. Según la Wikipedia, $\Sigma(6)$ se sabe que es al menos $3.5\times 10^{18267}$ que ya es mucho, y no necesariamente cercano al valor real.
Existe un límite superior no calculable para Σ(n), a saber, Σ(n+1). Σ(n) crece más rápido que cualquier función computable -si no lo hiciera, podríamos calcularla como han señalado muchas otras respuestas. Eso equivale a decir que Σ(n) no está acotado por una función computable.
Curiosamente, ¿existe alguna cota superior no computable f(n) para Σ(n) tal que f(n) < Σ(n+1) para todo n? Trivialmente: f(n) = Σ(n+1)-1 funciona. ¿Y qué pasa con f'(n) = Σ(n+1) - g(n) donde g(n) es cualquier función computable? Observa que f'(n) sigue creciendo más rápido que cualquier función computable: Supongamos que f'(n) está limitada por una función computable h(n) (para mostrar una contradicción). Entonces Σ(n+1) está limitada por j(n) = h(n)+g(n), que es computable por suposición. Σ(n) está acotado por Σ(n+1). Por tanto, Σ(n) está acotado por una función computable, lo cual es una contradicción: la suposición es falsa.
Esto no demuestra que f'(n) limite a Σ(n). Esa pregunta reformulada intuitivamente es preguntar: Σ(n) crece tan rápido, ¿podría pegar la salida de cualquier función computable entre Σ(n) y Σ(n+1) de algún n grande subiendo? ¿O la diferencia Σ(n+1)-Σ(n) está acotada por una función computable? Bien, supongamos que k es una función computable tal que k(n) > Σ(n+1)-Σ(n) para un n suficientemente grande (para demostrar que k no es computable). (Supongamos también que k es una función creciente, lo que puede hacerse sin pérdida de generalidad porque siempre hay una función computable y creciente que limita una función computable).
Consideremos la función z(n) = k(n)+k(n-1)+k(n-2)+...+k(n-n), que es computable si k es computable. Demuestre que z(n) limita a Σ(n), por inducción. Base: z(0) = k(0). k(0) > Σ(1)-Σ(0) o k(0)> 1. 1>Σ(0), por lo que z(0)>Σ(0).
Por tanto, por inducción z(n)>Σ(n). Pero Σ(n) no puede tener un límite superior computable. Por lo tanto, nuestra suposición de que hay una función computable k que limita la diferencia de salidas consecutivas de la función del castor ocupado es falsa. Por lo tanto, Σ(n+1)-g(n) para cualquier función computable g(n), es un límite superior de Σ(n).
Ahora bien, ¿qué hay de un límite en Σ(n) a partir de algún punto? En otras palabras, ¿qué pasa si la base de la inducción no se mantiene, pero para todo n>m>0 k(n)>Σ(n+1)-Σ(n)? En ese caso, definamos l(n) = {k(n) para n>m; k(m) en caso contrario}. l(n) es computable si k(n) lo es, y la inducción se mantiene, lo que implica que l(n) delimitaría Σ(n+1)-Σ(n) para todo n. Por tanto, ninguna k puede ser computable.
Pongámonos filosóficos. ¿Qué es un límite superior de la función del castor ocupado? Básicamente equivaldría a determinar la relación entre el número de estados de la máquina de Turing y la cinta finita mínima necesaria para ejecutar cada máquina que se detiene. Obviamente, eso resolvería el problema de la parada. Incluso las máquinas que nunca se detienen, pero que sólo visitan una cantidad finita de cinta, podrían resolverse ampliando dichas máquinas para que concatenen los trozos de cinta visitados por la versión más pequeña de la máquina. Esta máquina no se detendría nunca y pasaría por cualquier cantidad finita de cinta, y cuando se excediera el límite puesto en la cantidad de cinta para la máquina más grande, se sabría que la máquina más pequeña nunca se detendría. Esto no depende de la tesis de Turing porque tal máquina de Turing existe.
Como resultado, si asumimos la tesis de Turing, no hay una forma significativa de describir la velocidad a la que crece la función del castor ocupado. Eso es porque para cualquier función computable, se podría describir una función computable que crezca más rápido que ella por composición: g(n) = f(f(n)) siempre crece más rápido que f, cuando f es una función creciente. h(n) = g(g(n)), y así sucesivamente. Así que incluso si se dice que Σ crece más rápido que f, eso no significa mucho porque (infinitamente) muchas funciones computables crecen más rápido que f, pero no tan rápido como Σ. En ese sentido, f no me dice nada significativo sobre Σ.
Curiosamente, con las tasas de crecimiento computables de las funciones, si se grafica la función con una escala en el eje x tal que el espacio entre los números naturales aumente al mismo ritmo que la función, la gráfica de esa función aparecerá lineal. Esto no se puede hacer con Σ. Si escribes cualquier escala para el eje x, en algún punto de esa gráfica, Σ(n) (en el eje y) aumentará más rápido que cualquier función computable. ¡Eso sí que es rápido! ¿Es infinitamente rápido? Incluso si comprimes la escala en el eje y por alguna función computable, y expandes la escala del eje x por alguna función computable, en algún punto de esa gráfica Σ será (casi) vertical.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
