Asintóticas funciones ligadas a todo computable inferior la función Castor ocupado

Question

El castor ocupado la función $BB$ asintóticamente limita cualquier función computable. Es fácil demostrar que existen límites inferiores, por ejemplo, $log(BB)$.

¿Hay una función $f$ que asintóticamente límites incluso de todas las funciones computables, por lo que $BB$ no es computable por una máquina con un oracle para $f$? (obviamente, $f$ tiene que ser menor que $BB$)

Answer 1

Sí.

El Busy Beaver función de Turing grado $0'$: si yo conozco a $BB$, me puede decir si una máquina de Turing se va a detener.

Una función dominante de cada total computable de la función, mientras tanto, puede ser construido por cualquier alto grado de Turing (esto es Martin dominación del teorema), y hay un alto grado estrictamente $<_T0'$ (esto fue demostrado por Friedberg creo; Sacos construido un c.e. alto grado por debajo de lo $0'$, pero que no es necesario aquí).

---

Entonces, ¿cómo podemos construir una función de este tipo? ADVERTENCIA: Esto es bastante técnico.

Una condición es un par $(p, S)$ donde

• $p$ es un mapa de algunos finito set$\{0, 1, . . . , n\}$$\mathbb{N}$,

• $S$ es un conjunto finito de productos naturales, y

• cada una de las $e\in S$ es el índice de un total computable de la función.

Podemos decir $(p, S)$ extends $(q, T)$ - y escribir $(p, S)\le (q, T)$ (no, no es un error - esta notación puede parecer confuso al principio, pero hay una buena razón para ello) - si $p$ se extiende $q$, $S$ contiene $T$, y para cada una de las $n\in dom(p)\setminus dom(q)$ y $e\in T$, $p(n)>\varphi_e(n)$.

Vamos a construir una secuencia de condiciones de $(p_i, S_i)$ tal que

• $(p_0, S_0)\ge(p_1, S_1)\ge(p_2, S_2)\ge...$,

• $dom(p_i)\supseteq \{0, 1, . . . , i\}$, y

• $e_i\in S_i$ donde $e_i$ $i$th índice para un total computable de la función.

Estas propiedades asegurarse de que la función $$f=\bigcup p_i$$ is in fact a function from $\mathbb{N}$ to $\mathbb{N}$, que domina todas las funciones computables.

Además, nos aseguraremos de que $\Phi_e^f\not=BB$ cualquier $e$. Esta es la parte difícil.

Comenzamos la construcción con $p_0=\emptyset$, $S_0=\emptyset$, y proceder inductivamente. Digamos que hemos definido a $(p_n, S_n)$.

Ahora nos preguntamos:

Hay algunos $k\in\mathbb{N}$ y algunos finito mapa de $q$ con dominio estrictamente mayor que el de $p_n$ tal que $(q, S_n)\le (p_n, S_n)$ pero $\Phi_n^q(k)\downarrow\not=BB(k)$?

Si sí: Vamos a $p_{n+1}=q$, $S_{n+1}=S_n\cup\{t_n\}$ (donde $\{t_i: i\in\mathbb{N}\}$ es el conjunto de índices del total de funciones computables).

Si no: Vamos a $p_{n+1}$ cualquier ser finito parcial mapa tal que $(p_{n+1}, S_n)\le (p_n, S_n)$, y deje $S_n=S_n\cup\{t_n\}$.

Ahora es un divertido ejercicio para demostrar que esto funciona! SUGERENCIA: en "no" en el caso, parece que estamos esencialmente en no hacer nada en absoluto. Eso es correcto! Piense acerca de por qué esto no va a ser un problema . . .