¿Cómo puede Busy beaver($10 \uparrow \uparrow 10$) no tienen comprobable límite superior?

Question

Este artículo de la wikipedia afirma que el número de pasos de un $10 \uparrow \uparrow 10$ estado (interrumpiendo) Máquina de Turing para detener no tiene comprobable límite superior:

"... en el contexto de ordinario las matemáticas, ni el valor ni ninguno-límite superior de $\Sigma(10\uparrow\uparrow10)$ puede ser probada..."

¿Cómo es esto posible? En principio, no listado de los cálculos de todos los (un número finito) de detener las máquinas de Turing de ese tamaño, y las pruebas de no detener para todos los no-detener (de nuevo, un número finito) crear una prueba?

Estoy suponiendo que el "ordinario matemáticas" que se menciona no tiene ningún significado formal.

Answer 1

El artículo de la Wikipedia se explica exactamente lo que significa. Aquí es una elaboración.

Definir la complejidad de un número $n$ a ser el número más pequeño de los estados de una máquina de Turing que devuelve $n$ cuando se ejecuta con $0$ como una entrada. Ciertamente, cada número tiene una complejidad. Ahora vamos a $T$ ser una teoría formal de la lengua incluye las declaraciones de la forma "$n$ ha complejidad mayor que $k$" para cada una de las $n$$k$. Algunas de estas frases puede ser comprobada en la teoría, y algunos no. Decir que la teoría es la complejidad de sonido si cada instrucción "$n$ ha complejidad mayor que $k$" que es demostrable en la teoría es correcta. Tanto la autoridad palestina y de ZFC son eficaces, la complejidad de sonido teorías.

Teorema. Para cualquier efectiva, la complejidad de sonido de la teoría de la $T$, hay algunos $k$ de manera tal que la teoría no es prueba de que cualquier número de $n$ ha complejidad mayor que la de a $k$.

La prueba por contradicción. Suponga $T$ es la complejidad de sonido y demuestra que las declaraciones de la forma "$n$ ha complejidad mayor que $k$" por arbitrariamente grande,$k$. Considere la posibilidad de un programa de $P$ que hace lo siguiente cuando se ejecuta con $0$ como una entrada. En primer lugar, $P$ calcula su propio código fuente (como un Quine; formalmente, la prueba utiliza Kleene del teorema de recursión). A continuación, $P$ cuenta el número de estados de la $s$ en este código fuente. La próxima $P$ enumera todas las afirmaciones de la forma "$n$ ha complejidad mayor que $k$" que son demostrables a partir de $T$, hasta que encuentra uno con $k > s$. Se encuentra uno por supuesto. Finalmente, $P$ vuelve $n$. Debido a $T$ es efectivo en teoría, $P$ puede hacer todo esto computably. Pero, a continuación, el número de $n$ es devuelto por $P$, lo que ha $s$ estados, sino $T$ demuestra "$n$ ha complejidad mayor que $k$" para algunos $k > s$, lo $T$ no es la complejidad de sonido, la cual es una contradicción. Que completa la prueba.

Así pues, existe un límite en el más grande de $k$ tal que $T$ demuestra "$n$ ha complejidad mayor que $k$" para cualquier $n$. De hecho, podemos escribir $P$ explícitamente, y por lo tanto $k$ no es más que el número de estados de la versión de $P$ escribimos. Para cualquier teoría razonable, como PA o ZFC, esta $k$ va a ser enorme, pero no en cualquier lugar cerca de $10\uparrow\uparrow 10$.

Si una lo suficientemente fuerte, la teoría no puede demostrar nada, $n$ ha complejidad mayor que $k$, entonces también puede probar cualquier declaración de la forma "$m$ es un límite superior en $\Sigma(k)$", porque si se pudiera demostrar que también sería probar "$m+1$ ha complejidad mayor que $k$". Así, en particular, ni PA ni ZFC puede ser un límite superior en $\Sigma(k)$ al $k$ es lo suficientemente grande.

Así como el artículo de la Wikipedia dice que el teorema anterior es sólo una refundición de Chaitin del teorema de la incompletitud en las que la duración del programa es reemplazado con el número de estados.

Answer 2

Mientras que lo que se ha discutido en los comentarios es relevante (existen individuales de máquinas de Turing que han indecidible Detener los problemas), dudo que esto sea lo que la declaración en el artículo de la Wikipedia se refiere, principalmente porque no hay absolutamente ninguna necesidad de mencionar un salto tan alto como $10 \uparrow \uparrow 10$ encontrar una Busy Beaver con un indecidible Detener problema.

Cualquier máquina de Turing universal tiene un indecidible Detener problema, por que si no, usted sería capaz de resolver la Paralización problema para cualquier máquina que simula. Hay máquinas de Turing universal, con sólo un puñado de estados (ver, por ejemplo, este papel de Neary y Bosques.) La restricción de que un Busy Beaver comienza con una cinta en blanco no es de consecuencia, porque la máquina sólo puede escribir una descripción de la máquina en la cinta y, a continuación, proceder a simular.

Sospecho que la frase "ordinario matemáticas" es una referencia oblicua a la de primer orden de la Aritmética de Peano o similar, y la declaración se refiere a algún tipo de prueba que cualquier prueba de un obligado para TM con $10 \uparrow \uparrow 10$ estados deben utilizar transfinito métodos, incluso si la TM es total (como la Hidra de reescritura de juego, o algo en una vena similar.) Pero esto es sólo una conjetura.

("Ordinario matemáticas" normalmente sugiere ZFC para mí, pero una prueba de que este resultado es independiente de ZFC sería algo demasiado sorprendente para mí, para mí tomar esa interpretación aquí.)

Answer 3

Aquí es un simple argumento de que no depende explícito de diagonalización. Por otro lado, en contraste con Carl Mummert la respuesta sólo funciona para los de primer orden de las teorías o de otro axiomático marco donde algo como Gödel integridad del teorema sostiene. Pero eso es suficiente para cubrir los sospechosos de siempre de "ordinario matemáticas", es decir, PA y ZFC.

---

En primer lugar, por supuesto, la revisión de un particular de primer orden de la teoría de la $T$ que quieres demostrar que la afirmación acerca de. Asumimos que es efectivamente axiomatized y no es prueba de aritmética falsedades (en particular es consistente).

Deje $M$ ser una máquina de Turing que se repite a través de los números naturales hasta que encuentra uno que es el número de Gödel de una prueba de $T\vdash 0\ne0$, y luego se detiene. Ya que "es el número de Gödel de una prueba de $T\vdash0\ne0$" (primitivo) recursiva, ciertamente hay una máquina de Turing que lo hace, tendrá mucho menos de $10\mathop{\uparrow\uparrow}10$ estados. (La enorme atado de $10\mathop{\uparrow\uparrow}10$ debe ser el fin de satisfacer realmente despilfarro formas de implementar p.r. funciones como máquinas de Turing).

Ahora $M$ nunca puede detener, ya que estamos suponiendo que nuestra teoría de la prueba sin falsedades.

Por otro lado, si $T$ demuestra que $M$ no detener, entonces efectivamente se ha demostrado que sí es coherente, y que es imposible de acuerdo a la segunda Gödel-Rosser teorema de la incompletitud.

Desde $M$ no detener en cualquier número de pasos, y no puede ser comprobado en el que nunca se detiene, no debe ser un modelo de $T$ que $M$ se detiene en un no estándar del número de pasos. Por lo tanto no estándar límite superior para $\Sigma(|M|)$ es verdadera en el modelo, y por lo tanto $T$ puede resultar no tan obligado.