En este artículo Scott Aaronson habla sobre el uso de las máquinas de Turing para demostrar el teorema de Rosser.
¿Qué relación existe entre la numeración que utilizó Gödel en su prueba de incompletitud y las máquinas de Turing?
Es sencillo. Si el problema de detención es indecidible, entonces PA no es completa, ya que, de lo contrario, se podría resolver el problema de detención mediante la búsqueda de pruebas en PA. Y el mismo argumento funciona para cualquier teoría computable axiomatizable $T$ capaz de expresar la aritmética. Dada una máquina de Turing $M$ en la entrada $i$ , usted formula la afirmación $\sigma$ afirmando que $M$ se detiene en $i$ y luego buscar una prueba en $T$ de $\sigma$ o una prueba de $\neg\sigma$ . Si su teoría fuera completa, entonces encontrará una u otra, y esto resolvería el problema de detención. Dado que el problema de detención no se puede resolver, debe haber sentencias de esta forma que no son resueltas por la teoría.
Este argumento demuestra el primer teorema de incompletitud como una consecuencia elemental del problema de detención. El segundo teorema de incompletitud requiere un poco más de trabajo.
Hay más debates sobre ¿Están relacionadas las dos acepciones de indecidibilidad? y ¿Cómo de indecidible es el problema de la brecha espectral?
También va en sentido contrario. Si el problema de detención fuera decidible, se podría hacer una PA completa.
Estoy de acuerdo con esa afirmación; pero quizás pintaría una imagen algo más completa decir que las terminaciones de PA son ramas a través de un cierto árbol computable. De ello se desprende que hay terminaciones que son bajo y estos tienen una complejidad estrictamente menor en los grados de Turing que el problema de detención. Mientras tanto, otras terminaciones son mucho más complicadas que el problema de detención.
Por ejemplo, la aritmética verdadera es una terminación de PA con complejidad Turing $0^{(\omega)}$ .
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.
0 votos
Tal vez quiera leer este Puesto de MO.
0 votos
Las máquinas de Turing pueden numerarse según su representación para una máquina de Turing universal.