¿El $k$th adelante diferencia de Radó $\Sigma$ finalmente dominan cada función computable?

Question

Deje $\Sigma$ ser Radó del Busy Beaver función, y deje $\Delta[\Sigma]$ denotan el avance diferencia de $\Sigma$, de tal manera que $\Delta[\Sigma] \ (n) = \Sigma(n+1) - \Sigma(n)$ todos los $n \in \mathbb{N}$. Definir $\Delta^0[\Sigma] = \Sigma$, e $\Delta^{k+1}[\Sigma] = \Delta[\Delta^{k}[\Sigma]]$, para todos los $k \in \mathbb{N}$.

Pregunta: Es el caso que para todos los $k \in \mathbb{N}$, la función $\Delta^k [\Sigma]$ tiempo domina cada función computable $f: \mathbb{N} \rightarrow \mathbb{N}$?

(Creo que este es el caso, pero no saben cómo demostrarlo. Los punteros o fuentes en probar esto-o refutar, si estoy equivocado?)

He aquí una diferencia tabla que muestra todos los valores conocidos de estas secuencias:

     n:  0      1      2      3      4      5     ...
     ------------------------------------------------
     Σ:  0      1      4      6      13    ≥4098  ...
    ΔΣ:  1      3      2      7     ≥4085  ...
   ΔΔΣ:  2     -1      5     ≥4078  ...
  ΔΔΔΣ: -3      6     ≥4073  ...
 ΔΔΔΔΣ:  9     ≥4067  ...
ΔΔΔΔΔΣ: ≥4058  ...

Fuentes conocidas: "Una nota sobre Ocupado Castores y otras criaturas" (1996), por Ben Amram, Julstrom, y Zwick, contiene la conjetura de que, para cualquier función computable $f$, existe una constante $N_f$ tal que $\forall n \gt N_f, \Sigma(n+1) > f(\Sigma(n))$. En apoyo de esta prueban el resultado más débil que para cualquier función computable $f$, $\Sigma(n+1) > f(\Sigma(n))$ para un número infinito de valores de $n$. (Teniendo en cuenta los $f(x) = 2x$, por ejemplo, la conjetura implica que $\Delta[\Sigma]$ tiempo domina cada función computable.)

Motivación: En el "Busy Beaver juego" clase de máquinas de Turing, que eventualmente detener después de comenzar con una cinta en blanco, la "puntuación" de una máquina es el número de $1$s restante en la cinta después de detener. Una variante de la complejidad de Kolmogorov $C: \mathbb{N} \rightarrow \mathbb{N}$ define $C(n)$ menos $k$ tal que $n$ es la puntuación de algunos $k$-estado de la máquina. (cf "la Computabilidad y la Lógica" por Boolos, Burgess & Jeffrey, 2007, p229.) Yo creo que se puede demostrar que si la primera diferencia $\Delta[\Sigma]$ tiempo domina cada función computable, entonces esto $C$ no es monótona no decreciente, es decir, no existe $m \lt n$ tal que $C(m) \gt C(n)$.

NOTA: Debido a no recibir respuesta satisfactoria aquí, he puesto el caso más simple de esta pregunta en cstheory.SE.

Answer 1

Para la eventual conclusión "no existe $m<n$ tal que $C(m)>C(n)$" parece ser más fácil sólo para demostrar que para algunos $k$ existe un $k$-estado de la máquina con una puntuación mayor que el número de posibles $k$-máquinas de estado. Luego, por el principio del palomar no tiene que ser un número menor que este a la que se llega sólo por una máquina con $>k$ estados.

Dependiendo de los detalles, hay en la mayoría de los alrededor de $(6k)^{2k}$ diferentes $k$-máquinas de estado, y esto es fácilmente una función computable. Por lo tanto, si agregar algunos estados iniciales de que la precarga debe ser lo suficientemente grande $k$ (que se puede hacer en $O(\log k)$ estados) eventualmente llegar a un equipo con una puntuación que es lo suficientemente alto en relación a su tamaño.

Answer 2

Uso http://mathworld.wolfram.com/NewtonsForwardDifferenceFormula.html para obtener $D^k [z] (n)>f(k,n)z(n+k)$ para algunos computable $f(k,n)$ y cada estrictamente creciente función positiva $z$. Por lo tanto si $g(n)>D^k [z](n)$ para algunos computable $g$, entonces no es una computable obligado en cualquier $z(n+k)$. Contradicción.