Es el conjunto de PA teoremas de la misma como el conjunto de solucionable detener los problemas?

Question

No estoy seguro de si esta es una pregunta trivial. Por el Post del teorema sabemos que cada PA (de primer orden de la lógica) teorema es equivalente a decir que una determinada entrada C en una máquina de Turing, se detiene o no se detenga. Pero no me queda claro si eso significa que conociendo todos los PA teoremas (quiero decir, aquellos wff. que son comprobable), es equivalente a conocer la detención problema para detener cualquier problema que puede ser resuelto, es decir, aquellos que, en principio, se podría probar a frenar o no frenar (por supuesto, esto excluye a aquellos más allá de la primera Turing salto), independientemente de la entrada y, sin importar la máquina de Turing.

Pregunta de expansión después de las respuestas: Cuando me envió la pregunta, que no tenía en mente ninguna teoría concreta para demostrar si una máquina de Turing se iba o no iba a detener. En ese sentido T97778 era correcta. Pero yo tenía en mente una prueba de que le da la correcta (true) respuesta. No tiene que limitarse a PA. Ahora me doy cuenta de esta manera de pensar no es precisa, o bien nunca podemos estar seguros de que es una prueba de que un determinado TM detiene es correcta. O es incorrecto? ¿hay algún sistema formal de T que nos garantiza que una prueba de T de que una máquina se detiene o no detener es cierto? Por "verdadera" supongo que es un determinado valor de verdad para la detención problema, por lo que no hay estándar de interpretaciones de una máquina de Turing. Así que por mi pregunta, para tener sentido, primero necesita ser respondida (afirmativa) la pregunta anterior: ¿hay algún sistema formal de T que nos garantiza que una prueba de T de que una máquina se detiene o no detener es cierto? ¿Esta pregunta tiene sentido en absoluto? (Supongo que un sistema que asume Con(PA) no reúne los requisitos, porque no todo el mundo está de acuerdo en que el PA es consistente, por otro lado, no quiero restringir la prueba a finitist).

Nueva edición: Creo que tienes razón, el TM instrucción equivalente a la de París Harrington teorema sería lo que la máquina hace es buscar el mínimo de n, m, k, para la que existe un N. La máquina se detendrá si no se encuentra tal n, m, k. Un oráculo de la máquina es capaz de utilizar oracle ∅' repetidamente probar si cada triplete n, m, k está en el conjunto y, a continuación, detener si encuentra un triplete que no está en el conjunto. Así que el París Harrington (PH) conjetura es equivalente a la afirmación de que la máquina no se detiene cuando se ejecuta con un oráculo de ∅'. Si nunca se detiene, que quiere decir que nunca encuentra un triplete para el cual no existe N. el PH teorema demuestra que no siempre es tal N para cada triplete, por lo que la máquina no halt (Como usted dice). Estoy en lo cierto? es que lo que quiso decir T9996725? Si ese es el caso, entonces la respuesta a mi pregunta original sería un NO!!! el PH se muestra un ejemplo de detener un problema que podemos resolver (por resolver me refiero a saber si el TM se va a parar o no), y que no puede ser probado de PA (que es, no es un teorema de PA). Por favor alguien responda si esto es correcto.

Answer 1

Por el estándar de esquemas de codificación uno debe ser capaz de codificar la detención de una máquina de turing universal en el PA. Primero codifica el estado de la Máquina de Turing como (a) un número natural que representa a la cinta, y (b) un número natural que representa el estado de la máquina, a continuación, vincule estos dos valores en un único número entero. Ya que cada paso de la TM es finito, la cinta de estado siempre puede ser codificado como (posiblemente arbitrariamente larga) número finito; de la misma manera, no sólo el estado de la TM, pero toda la operación de la TM puede ser fácilmente codificados en $\mathbb{N}$, usando el estándar de codificación de las técnicas para la representación finita colecciones de productos naturales como productos naturales. Esto permite definir un $\Delta_0$ función de $f$ que si $s$ representa un dado (TM estado, cinta de estado) par, a continuación, $f(s)$ representa el estado de la máquina y la cinta después de la ejecución del ciclo. Del mismo modo, desde 'la máquina se ha detenido' es simplemente 'la máquina se encuentra actualmente en un alto estado", lo que es fácilmente codificado como un $\Delta_0$ predicado $g(s)$. Con esto en su lugar, puede utilizar el teorema de recursión para codificar el concepto de '$x$ códigos de un (finito) de la secuencia con un determinado $x_0$ tal que $\forall i\lt \text{len}(x)$, $x_{i+1}=f(x_i)$ y $g(x_{\text{len}(x)})$' como una función de $h(x, x_0)$. La detención de la máquina en un determinado algunos de entrada de $x_0$ es equivalente a la declaración de $\exists x h(x,x_0)$.

Answer 2

La respuesta a la pregunta es NO. El París Harrington teorema muestra un ejemplo de detener un problema que podemos resolver (por resolver me refiero a saber si el TM se va a parar o no), y que no puede ser probado de PA (que es, no es un teorema de PA), pero se ha demostrado que el verdadero uso de una teoría más fuerte que la PA.