¿Hay una teoría efectiva que "soluciona" el problema de parada?

Question

Estoy en busca de un efectivo de la teoría de la $T$ que resuelve la suspensión problema, en el sentido de que para cada máquina de Turing $M$, $T$ tampoco demuestra que $M$ se detiene, o que no se puede detener.

En la cara de ella, que esto violaría del teorema de Turing que no se puede resolver la suspensión problema. El truco está en que $T$ lo haría de no ser en realidad el sonido, es decir, habría al menos una máquina de Turing $M$ tal que $T$ demuestra que $M$ se detiene, pero en realidad no. (Así que en realidad no resuelve el cese problema). (Por ejemplo, $PA+\lnot Con(PA)$ demuestra que la máquina de Turing que busca una contradicción en $PA$ se detiene, cuando en realidad esta máquina no.)

Como evitar trivial respuestas (tales como la teoría de que simplemente afirma que cada máquina de turing se detiene), yo también voy a exigir que $T$ demuestra todos los axiomas de la PA, y es consistient.

Algunas notas:

• Desde Turing del teorema puede ser internalizado a $T$ (ya que puede en $PA$), $T$ pueden demuestra que $T$ no resuelve el cese problema. Esto está bien aunque, desde la $T$ no está de sonido.
  • Esto implica que en cualquier modelo de $T$, no sería un no estándar de la máquina de Turing $M$ tal que $T$ no puede demostrar si es o no $M$ se detiene.
• $T$ demuestra que $T$ es incoherente, ya que se demuestra que la máquina en la que se busca una contradicción en $T$ se detiene (de lo contrario, sería necesario demostrar que esta máquina no se detiene, demostrando ser coherente, en violación de Goedel del segundo teorema de la incompletitud).

Answer 1

No hay tal $T$ existe (al menos, no $T$ ampliación de PA (o similar) que existe). El hecho clave es que la recursividad es el teorema de internos, en el siguiente sentido:

Para cada una de las $e$, hay algunos $c$ tales que PA demuestra la frase "Si $\Phi_e$ es total,$\Phi_{\Phi_e(c)}\cong\Phi_c$."

De hecho, la prueba y la $c$ son sólo los de siempre - el punto es que PA es lo suficientemente fuerte como para demostrar que el índice construido en la prueba del teorema de recursión hace lo que debe!

---

Ahora podemos aplicar el teorema de recursión, "interiorizado" como es arriba, de forma natural. Deje $T$ consistente computably axiomatized la teoría de la ampliación de PA. Por el interior de la recursión teorema, podemos encontrar una $e$ tales que PA lo demuestra:

• Si $T$ demuestra $\Phi_e(e)\downarrow$ antes de la prueba $\Phi_e(e)\uparrow$ (es decir, a través de una prueba que aparece por primera vez en alguna norma de orden de pruebas), a continuación,$\Phi_e(e)\uparrow$.

• Si $T$ demuestra $\Phi_e(e)\uparrow$ antes de la prueba $\Phi_e(e)\downarrow$,$\Phi_e(e)\downarrow$.

• Si $T$ demuestra ni, a continuación,$\Phi_e(e)\uparrow$.

(Lo primero que piensa acerca de por qué un $e$ con estas propiedades existe clásico, utilizando el teorema de recursión como normalmente declaró.)

Desde $T$ se extiende PA, $T$ también demuestra estos hechos. Pero entonces, si $T$ resuelve la suspensión problema en su sentido, es incoherente:

• Si $T$ demuestra $\Phi_e(e)\downarrow$ antes de la prueba $\Phi_e(e)\uparrow$, $T$ considera que, así que, por encima de la $T$ también es $\Phi_e(e)\uparrow$.

• Si $T$ demuestra $\Phi_e(e)\uparrow$ antes de la prueba $\Phi_e(e)\downarrow$, $T$ considera que, así que, por encima de la $T$ también es $\Phi_e(e)\downarrow$.

De hecho, lo que hemos demostrado es que los conjuntos de índices que PA demuestra detener y que PA demuestra no detener son recursivamente inseparables!

Answer 2

Usted está pidiendo una teoría de la $T$ tales que (1) $T$ es de forma recursiva axiomatized, (2) $T$ extends $PA$, (3) si una máquina de Turing $M$ se detiene, a continuación, $T$ demuestra que $M$ se detiene, y (4) para cada máquina de Turing $M$, $T$ demuestra que $M$ se detiene, o $T$ demuestra que no es así. Vamos a argumentar que no $T$ existe por la forma de la conocida

$\bf Theorem\ of\ Kleene:$ Hay un par de computably conjuntos enumerables $A, B$ de los números naturales tal que $A \cap B = \emptyset$, y de tal manera que para no computables del conjunto de $C$ do tenemos $A \subseteq C \subseteq \bar B$ donde $\bar B$ es el complemento de a $B$. Un par de $A,B$ se llama $\it computably\ inseparable$.

Fix $A$ $B$ como en el teorema. Nos dicen que si su $T$ existe, entonces podemos exhibir una computable $C$ del tipo prohibido por el teorema, una contradicción. Para cada una de las $n$, vamos a $M_n$ ser una máquina de Turing que se detiene si $n$ entra $A$ sin entrar por primera vez en $B$, y deje $M_n'$ ser que detiene el si $n$ entra $B$ sin entrar por primera vez en $A$. (A pesar de $A$ $B$ son disjuntas, 'sin' primero en la cláusula todavía puede entrar en juego no estándar en los modelos.) Ahora fix $n$; vamos a decidir si $n$ a $C$ o en su complementar $\bar C$. Desde $T$ es consistente, esto no es prueba de que tanto $M_n$ $M_n'$ detener. Si $T$ demuestra $M_n$ detiene, poner $n$ a $C$; si $T$ demuestra $M_n'$ detiene, poner $n$ a $\bar C$; y si ninguno de estos pasa por el diseño de $T$, resulta que ambos no parar, y nos arbitrariamente poner $n$ a $C$.

Hacer esto para cada $n \in \mathbb{N}$, llegamos a una computable $C$. Pretendemos que $A \subseteq C$$B \subseteq \bar C$. A ver $A \subseteq C$, corregir los $n \in A$, y el aviso de que $M_n$ se detiene, de modo que por la elección de $T$, $T$ demuestra que $M_n$ se detiene, y por lo tanto hemos colocado $n$ a $C$ en la construcción. La prueba de que $B \subseteq \bar C$ es similar. Por lo tanto $C$ es una computable separador de $A$$B$, prohibido por el teorema anterior, y hemos terminado.