Sea S el conjunto de todos los TMs cuya detención es decidible en ZFC (para cada TM en S, podemos encontrar un algoritmo en ZFC que determine si la máquina se detiene o no). ¿Es S recursivo? ¿Existe un algoritmo que pueda enumerar tanto las máquinas que paran como las que no paran de S?
Por ejemplo, ¿el conjunto de ecuaciones diofantinas seguiría siendo no computable si elimináramos las instancias que son independientes de ZFC?
Supongamos que $\mathsf{ZFC}$ es $\Sigma^0_1$ -Sonido.
Para cada frase $\varphi$ en el lenguaje de la teoría de conjuntos, considere la máquina $T_\varphi$ que, independientemente de la entrada, busca un $\mathsf{ZFC}$ -prueba o refutación de $\varphi$ y se detiene si encuentra uno. Entonces $T_\varphi$ se detiene si $\varphi$ es $\mathsf{ZFC}$ -decidible, y $\mathsf{ZFC}$ demuestra esto.
Desde $\mathsf{ZFC}$ es $\Sigma^0_1$ -completa, si $T_\varphi$ se detiene (en la entrada $0$ , digamos) entonces $\mathsf{ZFC}$ demuestra que $T_\varphi$ se detiene. ¿Y si $T_\varphi$ no se detiene? Pues bien, entonces $\mathsf{ZFC}$ no puede probar que $T_\varphi$ hace por la hipótesis de solidez anterior, y por las cuatro últimas palabras del párrafo anterior + el segundo teorema de incompletitud de Godel $\mathsf{ZFC}$ no puede probar que $T_\varphi$ no lo hace detener cualquiera de los dos (de lo contrario $\mathsf{ZFC}$ demostraría que $\mathsf{ZFC}$ es coherente).
Por lo tanto, el estado de parada de $T_\varphi$ es $\mathsf{ZFC}$ -decidible si $\mathsf{ZFC}$ decide $\varphi$ . Pero es un ejercicio estándar que el conjunto de $\mathsf{ZFC}$ -no es computable, ya que de lo contrario podríamos construir una extensión completa computable y consistente de $\mathsf{ZFC}$ contradiciendo el primer teorema de incompletitud.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
