¿Qué error(es) en mi argumento sobre la representabilidad, la definibilidad y el problema de detención?

Question

Me gustaría pedir su ayuda para mostrarme los (muy probablemente: varios) defectos de mi argumento a continuación, relacionando débiles y fuertes representabilidad en un sistema formal y el problema de detención .

Al menos una parte del problema es que probablemente soy demasiado informal en mis definiciones, lo que lleva a conclusiones erróneas. Dicho esto, sigo sin poder señalar exactamente dónde se equivoca mi argumento. Esperemos que alguien sea lo suficientemente paciente como para pasar por alto la falta de rigor en aquellos pasos en los que el argumento es correcto en principio, y me ayude a entender los principales errores del mismo.

(1) El conjunto de parada $HALT$ que contiene todos los pares de números $(i, j)$ s.t. el programa de Turing (enumerado por) $i$ se detiene (es decir, produce una salida) después de pasos finitos en la entrada $j$ es enumerable de forma computable, mientras que su conjunto complementario (de pares programa/entrada que no se detienen) no es enumerable de forma computable.

(2) Suponiendo un sistema formal de primer orden $F$ tan expresiva como la aritmética de Peano (PA) es lo suficientemente fuerte para razonar sobre relaciones computables, podemos (¿podemos?) definir una fórmula $H$ en $F$ que representa débilmente el conjunto $HALT$ es decir $(i,j) \in HALT \iff \vdash H(i, j)$ .

Para una definición (descuidada) de $H$ : $\forall x,y \: \exists z.H(x, y) \iff CompStateSequence(z, x, y)$ , donde $CompStateSequence(z, x, y)$ se mantiene si $z$ codifica una secuencia finita de estados del programa para un par programa/entrada $(x, y)$ es decir, cada estado de la secuencia se desprende correctamente del estado anterior según las reglas del programa, el primer estado es el estado inicial de $(i,j)$ y el estado final es el estado de salida de un programa.

$(\rightarrow)$ Si $(i,j) \in HALT$ debe existir una secuencia finita de pasos de cálculo que compute $(i,j)$ por lo que debe existir una secuencia finita de estados que representen un cálculo exitoso de $(i, j)$ . Entonces podemos encontrar una prueba para $H(x, y)$ en $F$ , $\vdash H(i, j)$ , probando mecánicamente todos los números hasta $z$ si son la secuencia deseada de estados del programa.

$(\leftarrow)$ Supongamos que $(i,j) \notin HALT$ . Entonces no existe una secuencia (finita) de estados del programa, ya que la secuencia calcula $(i,j)$ . Supongamos que $\vdash H(i,j)$ . Entonces, por definición de $H$ debe haber un número $z$ que representa una secuencia finita de estados del programa que representa un cálculo de $(i,j)$ . Contradicción, por lo que sabemos $H$ representa (débilmente) el conjunto $HALT$ en $F$ .

(3) Además, podemos utilizar $H$ a definir (en el sentido más débil de verdad, no de demostrabilidad) conjunto $HALT$ en $F$ es decir $(i, j) \in HALT \iff$ $H(i, j)$ es verdadera en el modelo previsto de F, mediante un argumento similar al de (2) anterior, con "verdad" en lugar de "demostrabilidad".

(4) (Ahora, la parte en la que probablemente me confundo...) Supongamos que $(i,j) \notin HALT$ . Por definición de $H$ (y el argumento de (3) anterior) sabemos que $H(i,j)$ es falso en el modelo previsto de $F$ .

Pero si $H(i,j)$ es falso en un modelo de $F$ debe ser falsa en todos los modelos de $F$ ya que $(i,j)$ no se detendrá en ningún modelo (correcto) de una teoría que represente la computabilidad de Turing.

Entonces $\neg H(i,j)$ es cierto en todos los modelos de $F$ Así que $\neg H(i,j)$ es válido, por lo que por completitud (semántica) de $F$ hay una prueba de $\neg H(i,j)$ en $F$ . Pero entonces $\not H$ también es débilmente representable, por lo que junto con la representabilidad débil de $H$ , $HALT$ es fuertemente representable en $F$ lo que (por equivalencia de representabilidad fuerte y decidibilidad) contradice el resultado de que el problema de detención es indecidible.

Answer 1

Creo que aquí hay un error:

Pero si $H(i,j)$ es falso en un modelo de $F$ debe ser falsa en todos los modelos de $F, ...$

Tenga en cuenta que una declaración "El programa $i$ se detiene en la entrada $j$ " es en realidad un enunciado aritmético existencialmente cuantificado de la forma "Hay un número $n$ de manera que el programa $i$ se detiene en la entrada $j$ después de $n$ pasos" .

Pero hay modelos no estándar de la aritmética que tienen enteros no estándar (un modelo puede incluso tener un conjunto arbitrario e incontable de ellos). Un modelo no estándar puede pensar que un programa particular se detiene en una entrada particular después de $n$ pasos, donde $n$ es un entero no estándar, mientras que el modelo estándar pensará que este programa no se detiene (porque no existe tal $n$ en el modelo estándar), por lo que en realidad puede No estoy de acuerdo con eso.

Supongamos que, de alguna manera, te convences de que un modelo particular no estándar es incorrecto en este caso, y el programa no se detiene realmente. Puede añadir un axioma adicional a $F$ que indique específicamente que este programa no se detiene, y esto descartará ese modelo particular no estándar. Pero no importa qué conjunto recursivamente enumerable de nuevos axiomas estés añadiendo, siempre habrá muchos (una clase propia de) otros modelos no estándar restantes. Se trata del famoso fenómeno de incompletitud .

Con respecto a su siguiente argumento:

... desde $(i,j)$ no se detendrá en ningún modelo (correcto) de una teoría que represente la computabilidad de Turing.

parece que no demuestra nada, porque está diciendo explícitamente sólo sobre un modelo correcto (supongo, estándar).

Answer 2

Independientemente de cualquier formulación matemática razonable para la afirmación en cursiva, veamos qué ocurre cuando $F=PA$ .

Discutir dentro de $ZFC$ :

"Dado que existe un modelo de $PA$ (el modelo estándar de la aritmética de primer orden), entonces tenemos $\text{Con}(PA)$ por el teorema de integridad. Por lo tanto, $PA\nvdash\text{Con}(PA)$ por el segundo teorema de incompletitud. Por lo tanto, tenemos $\text{Con}(PA+\neg$ $\text{Con}(PA))$ y, por lo tanto, existe un modelo para $PA+\neg\text{Con}(PA)$ aplicando de nuevo el teorema de la completitud".

Y fíjate entonces que $\neg\text{Con}(PA)$ es un $\Sigma_1$ frase que es falsa en el modelo estándar de $PA$ y verdadero en algún otro modelo de $PA$ .