¿Cuál es la relación entre la ZFC y la máquina de Turing?

Question

No aprendí bien la Lógica pero hasta ahora entiendo que los sistemas de pruebas pueden ser vistos como una especie de máquina. Para el sistema de prueba, ZFC parece ser el más poderoso que usamos hasta ahora. Del mismo modo, para el modelo de computación, la máquina de Turing parece ser la más poderosa.

Así que quiero preguntar cuál es la relación entre estos dos? He intentado formular la pregunta, pero si contiene algún malentendido, por favor, señálelo.

Dejemos que $L$ sea un lenguaje que contenga todos los enunciados que se pueden demostrar en ZFC. Es $L$ decidible por la máquina de Turing, o en otras palabras, es $L$ ¿computable?

Si esto es cierto, entonces la máquina de Turing es al menos tan potente como el sistema de pruebas ZFC en el sentido de que, si $a \in L$ Es decir, $a$ se puede demostrar en ZFC, entonces la máquina de Turing puede decidir si $a \in L$ también.

Por otro lado, decir que el sistema ZFC es al menos tan potente como la máquina de Turing:

¿Es el sistema de pruebas ZFC Turing-completo?

He intentado buscar la respuesta y lo que más me confunde es lo siguiente.

• La ZFC es de primer orden.
• De la teoría de la complejidad descriptiva, $FO=AC^0$ que es muy limitada.

¿Podría aclarar mi confusión? Muchas gracias.

Answer 1

$L$ no es computable. Pero es recursivamente enumerable. Si $\varphi$ es un teorema de ZFC, entonces $\varphi$ puede ciertamente ser probado por la máquina de Turing. Sólo hay que empezar a enumerar todas las pruebas. El problema es con las sentencias $\varphi$ que son no teoremas de ZFC.

En la otra dirección, una máquina de Turing universal puede codificarse en ZFC, incluso en teorías mucho más débiles, como fragmentos relativamente pequeños de la teoría de números.

Answer 2

Supongamos, por reducción, que una máquina de Turing pudiera decidir si la sentencia con número de Gödel $n$ es un teorema de ZFC. Entonces la propiedad $Prov(n)$ que $n$ tiene cuando $n$ números un teorema ZFC sería recursivo. Así que habría un wff ZFC que representa esa propiedad (ya que incluso PA puede representar todas las propiedades recursivas). Eso significa que habría un wff $\mathsf{Prov}()$ tal que para cualquier $\varphi$

Si ZFC $\vdash \varphi$ , entonces ZFC $\vdash \mathsf{Prov(\ulcorner\varphi\urcorner)}$

Si ZFC $\nvdash \varphi$ , entonces ZFC $\vdash \neg\mathsf{Prov(\ulcorner\varphi\urcorner)}$

donde $\ulcorner\varphi\urcorner$ es el número de Gödel de $\varphi$ .

Ahora, por el lema de la diagonalización, habría una sentencia del tipo Gödel $\gamma$ tal que

ZFC $\vdash \gamma \leftrightarrow \neg\mathsf{Prov(\ulcorner\gamma\urcorner)}$

Pero también tenemos, por nuestra suposición,

Si ZFC $\vdash \gamma$ , entonces ZFC $\vdash \mathsf{Prov(\ulcorner\gamma\urcorner)}$

Si ZFC $\nvdash \gamma$ , entonces ZFC $\vdash \neg\mathsf{Prov(\ulcorner\gamma\urcorner)}$

La contradicción es inmediata.