Busy Beaver función de la tasa de crecimiento en comparación con funciones computables

Question

Fijar una definición de una máquina de turing (o un lenguaje de programación) y definir $BB(n)$ a ser el máximo número de pasos de un programa con menos de $n$ estados (o con menos de $n$ bits) puede tomar para detener. En particular, hacemos caso de programas que no se detenga.

No hay un estándar, fácil prueba de que para cualquier función computable $f(n)$, existe un $n$ que $BB(n) > f(n)$. Si esto fuera falsa, entonces podemos resolver la suspensión problema mediante la simulación de una máquina $M$ $n$ estados de a $BB(n)$ pasos y si no se detiene por entonces, sabemos que nunca va a parar.

Sin embargo, he visto que se declaró a veces ese $BB(n)$ crece más rápido de lo $f(n)$ en el sentido más fuerte que la de todos $n \geq N$, ($N$ un gran número dependiendo $f$) $BB(n) > f(n)$.

Cómo es esto resultó? Por ejemplo, yo no veo cómo descartar el caso de que $BB(n) < f(n)$ todos los $n$ a excepción de un determinado valor, pero este valor particular resulta ser uncomputable.

Answer 1

Este en realidad es un poco desordenado.

---

En primer lugar, he aquí un esbozo de la prueba de la reclamación:

Fijar un aumento del total de la función computable $f$. Hay una natural manera de producir, dado $k\in\mathbb{N}$, una máquina de Turing $M_k$ que en una cinta en blanco en primer lugar, calcula $f(k)$ y, a continuación, titubea alrededor para que muchos de los pasos y, a continuación, se detiene. Mediante el examen de esta construcción, podemos ver que el número de estados de $M_k$ está delimitado por $C_f+k$ para algunas constantes $C_f$. Esto nos dice que:

Por cada aumento del total computable $f$ hay algunas constantes $C_f$ tal que $BB(C_f+n)\ge f(n)$ todos los $n$.

Ahora hacemos la siguiente definición:

Para un aumento del total de la función computable $f$, vamos a $g_f: x\mapsto f(2x)$.

Es fácil ver que desde $BB(C_{g_f}+n)\ge g(n)$ todos los $n$ y algunas constantes $C_{g_f}$, debemos tener $BB$ eventualmente dominar $f$: $\color{red}{\mbox{if $m\ge C_{g_f}$}}$ $$BB(C_{g_f}+m)\ge g(m)=f(2m)\color{red}{\ge} f(C_{g_f}+m),$$ and so $BB(x)\ge f(x)$ for all $x\ge C_{g_f}$.

---

Ahora, tenga en cuenta que en el anterior que no acaba de uso general de los argumentos sobre la computabilidad; en realidad nos habló acerca de la construcción de máquinas de Turing (y bullsh!montarán un poco - "mediante el examen de esta construcción, podemos ver" ...). Resulta que hay una buena razón para ello: la afirmación no es verdadera para "grueso" razones. El resto de esta respuesta se analiza esta situación.

Permítanme comenzar por considerar una variante de la busy beaver, el "adicto al trabajo Wombat:"

$WW(n)=\max\{t:$ por alguna máquina de Turing $M$ $<n$ a los estados y algunos $k<n$, $M$ se detiene después de exactamente $t$ pasos en la entrada de $k\}.$

Nota el nuevo ingrediente: estamos permitiendo que los insumos como de máquinas. WW y BB son Turing equivalente, por supuesto, el punto crucial de que las entradas permitió $WW(n)$ están delimitadas por $n$. Sin embargo, $WW(n)$ tiene mucho mejor educados asymptotics:

Para cada computable total $f$, $WW$ domina $f$.

Prueba. Fix $f$ total computable. Deje $M$ ser la máquina de Turing que en la entrada de $k$ calcula el $f(k+1)$, titubea alrededor de $f(k)$-de muchos pasos, y luego se detiene. Supongamos $M$ $n$ estados; a continuación, para cada una de las $m\ge n$ hemos $WW(m+1)>f(m+1)$. $\quad\Box$

Este es un ejemplo de una gruesa argumento: que no dependen de los detalles finos de es exactamente cómo representamos máquinas de Turing. Este argumento vale para cualquier "razonable enumeración" (o "finito-a-uno enumeración" - varias máquinas de Turing pueden tener el mismo número de estados, pero hay sólo un número finito con un determinado número de estados) de máquinas de Turing. Sin embargo, hay un montón de resultados que son más quisquillosos. Mi ejemplo favorito es el Relleno Lema. Esto obviamente-hecho cierto resulta ser dependiente en el modo de lista de máquinas de Turing:

Hay un efectivo de la enumeración de las funciones computables de tal forma que cada parcial computable de la función ocurre exactamente una vez en la lista.

Tal enumeración es llamado un Friedberg enumeración. En la declaración anterior, tenemos que ser muy cuidadosos de lo que queremos decir por "la eficacia de la enumeración de las funciones computables," y pensar acerca de este problema con el tiempo le llevará a la noción de "admisible de numeración", que las reglas de este tipo de tonterías. Hay otros sillinesses que las enumeraciones de las funciones computables puede mostrar, y puede ser divertido para jugar con ellos.

Ahora, de cualquier manera eficaz de listado parcial de funciones computables da lugar a la correspondiente Busy Beaver función y en un adicto al trabajo Wombat función. Como se observó anteriormente, la GUERRA todavía dominan cada total computable de la función; sin embargo, no es difícil cocinar listados cuyos BBs no dominan cada total computable de la función. La conclusión es que:

Demostrando que la BB domina cada total computable de la función que va a tardar un poco jugando con la precisión de los detalles de máquinas de Turing, y no sólo puede realizarse a través de los generales "grueso" de las consideraciones.

Answer 2

Si no sería, en el caso de que $BB(n) < f(n)$ todos los $n$ a excepción de un determinado valor de $n_0$, entonces el Busy Beaver función se convierte en computables, porque sabemos que $BB(n) < BB(n+1)$ todos los $n$, y por lo $BB(n_0) < BB(n_0+1) < f(n_0+1)$, y, por supuesto, para todos los demás $n$: $BB(n) < f(n)$, y así tenemos que $BB(n) < max(f(n), f(n+1))$ todos los $n$, y así, podemos tener una función computable, es decir,$max(f(n), f(n_1))$, lo que da una computable de límite superior de ... que el Busy Beaver función no tiene.

Answer 3

El argumento básico parece mostrar que no hay ninguna total función recursiva $f:\mathbb{N} \rightarrow \mathbb{N}$ que con el tiempo domina la función de $bb:\mathbb{N} \rightarrow \mathbb{N}$. Es decir, el argumento básico parece mostrar que $bb(n)>f(n)$ infinitamente muchos de los valores de $n$.

Si queremos demostrar que las $bb$ tiempo domina cada total de la función recursiva $f$, entonces parece que un poco más de trabajo que se necesita. Más precisamente, queremos mostrar que para cada total de la función recursiva $f$, existe un valor de $N$, de modo que para todos los $n\ge N$ tenemos $bb(n)>f(n)$. Parece que esto debe ser cierto bastante bajo supuestos razonables.

Sin embargo, antes de eso, usted escribió en el último párrafo de su pregunta: "Por ejemplo, yo no veo cómo descartar el caso de que $BB(n) < f(n)$ todos los $n$ a excepción de un determinado valor, pero este valor particular resulta ser uncomputable." A menos que no he entendido esto, es descartado debido a razones básicas. Es decir, supongamos que el valor de $a$ tenemos $BB(a) \ge f(a)$. Sólo tiene que modificar el dado (supuestamente) función computable $f$ a a (supuestamente) función computable $g$, de modo que $g(x)=f(x)$ cuando $x\neq a$ ..... y, además,$g(a)=BB(a)$. Ahora podemos utilizar el habitual argumento básico para mostrar que $g$ no es computable, y por lo tanto llegar a una contradicción.

---

Ahora, volviendo a la pregunta original, mostrando que la $bb$ tiempo domina cada total de la función recursiva $f$ (lo siento si esto es sólo una repetición de las otras respuestas). Considere la posibilidad razonable de que la enumeración de los programas (de una variable de entrada) para que un programa con un tamaño más pequeño tiene siempre menor índice de un programa con mayor tamaño (para el fin de facilitar la visualización). Definir una función $h:\mathbb{N} \rightarrow \mathbb{N}$ con la siguiente ecuación(para todos $n$): $h(n)=bb(2n)$. Ahora se puede demostrar que $h$ tiempo domina cada total de la función recursiva, en los siguientes supuestos/observaciones:

(1) Si suponemos que las variables de nuestro programa sólo puede ser incrementado por $1$ en la mayoría de los (en uno de los comandos), entonces podemos observar que podemos re-escribir un programa $P1$ de la longitud de la $N$ (cuando se le da una entrada de $a$) como un programa de $P2$ de la longitud de la $a+N$ (mediante la colocación de incremento de comandos para la variable de entrada en el principio). El punto importante es que la salida de $P1$ en la entrada de $a$ será el mismo que el de salida de $P2$ en la entrada de $0$.

(2) suponemos además que contamos con el tiempo de tal manera que el tiempo se incrementa, al menos, por $1$ a "todos los comandos". Y además cada una de las variables (excepto la variable de entrada) se inicia con el valor de $0$. Con estas premisas es fácil ver que si un programa de $P$ de la longitud de la $N$ calcula una arbitraria total de la función recursiva $f$, $f(n) \le bb(n+N)$ para todos los valores de $n$.

Ahora para cualquier valor de $n \ge N$, tenemos: $f(n) \le bb(n+N) \le bb(n+n)=bb(2n)=h(n)$. Esto completa la primera parte de la prueba, creo. Pero esto no prueba que $bb$ tiempo domina cada total de la función recursiva $f$. Sólo muestra que $h(n)=bb(2n)$ tiempo domina cada total de la función recursiva $f$.

EDIT: Mi argumento anterior con respecto a $bb$ eventualmente dominar cada función recursiva es demasiado vaga. Aquí está una explicación más clara. Definir una función $stair:\mathbb{N} \rightarrow \mathbb{N}$ por lo que: $stair(n)=bb(n)$ al $n$ es incluso y más $stair(n)=bb(n-1)$ al $n$ es impar.

Ahora se puede demostrar sin dificultad que la función de $stair$ tiempo domina cada total de la función recursiva. Por contradicción, supongamos que existe una función computable $f$ que era mayor que $stair(n)$ infinitamente muchos de los valores de $n$. Entonces podemos definir una función computable $g$ por lo que:
$g(n)=max(f(2n),f(2n+1))$

Pero ahora la función de $g(n)$ debe ser mayor que $bb(2n)=h(n)$ para un número infinito de valores. Ya que esto no puede ser verdad, nuestra hipótesis original es incorrecta.

También es claro que $bb(n) \ge stair(n)$ todos los $n$. Por lo tanto $bb$ el tiempo también domina cada total de la función recursiva. FINAL

Con una máquina basada en el modelo computacional, a mí me parece que un par de detalles específicos, quizás, puede que tenga que ser cambiado. Pero supongo que las ideas básicas que debe seguir siendo el mismo.