Problema de parada

Algunos bucles infinitos pueden ser bastante útiles. Por ejemplo, los bucles de eventos suelen codificarse como bucles infinitos. ^{[ 5 ]} Sin embargo, la mayoría de las subrutinas están diseñadas para finalizar. ^{[ 6 ]}

En la computación en tiempo real estricto , las subrutinas no solo deben terminar, sino que deben terminar antes de una fecha límite determinada. ^{[ 7 ]} Para cumplir con estos requisitos, los programadores aplican la regla de mínima potencia y utilizan estilos restringidos, que no son completamente Turing-completos, lo que facilita demostrar que las subrutinas resultantes terminan antes de la fecha límite dada. Estos incluyen lenguajes como MISRA C , SPARK y Rocq .

El problema de la parada requiere un procedimiento de decisión que funcione para todos los programas y entradas. Sin embargo, para cualquier programa y entrada específicos, la respuesta es simplemente "se detiene" o "no se detiene". Consideremos dos procedimientos de decisión sencillos: uno que siempre responde "se detiene" y otro que siempre responde "no se detiene". En cualquier caso dado, uno de estos dos algoritmos responde correctamente, pero ninguno resuelve el problema de la parada.

Los intérpretes son programas que simulan la ejecución de programas, independientemente del código fuente que se les proporcione. Dichos programas pueden demostrar que un programa se detiene, ejecutándolo durante un número determinado de pasos. Sin embargo, un intérprete no se detendrá si el programa de entrada no se detiene, por lo que este enfoque no resuelve el problema de la parada tal como se plantea; no responde satisfactoriamente a la pregunta "¿no se detiene?" para programas que no se detienen, ni determina si un programa se detendrá finalmente o se ejecutará indefinidamente.

El problema de la parada es decidible para autómatas lineales acotados (LBA) o máquinas deterministas con memoria finita. Dicha máquina tiene un número finito de configuraciones posibles, por lo que cualquier programa determinista en ella debe eventualmente detenerse o repetir una configuración anterior: ^{[ 8 ]}

... cualquier máquina de estados finitos, si se la deja completamente a su suerte, acabará cayendo en un patrón repetitivo perfectamente periódico . La duración de este patrón repetitivo no puede exceder el número de estados internos de la máquina...

Sin embargo, Minsky señala: ^{[ 9 ]}

...las magnitudes involucradas deberían llevar a sospechar que los teoremas y argumentos basados ​​principalmente en la mera finitud [del] diagrama de estado pueden no tener mucha importancia.

Por ejemplo, una computadora con un millón de componentes de dos estados tendría al menos 2 ^{1 000 000} de estados posibles: ^{[ 9 ]}

Esto es un 1 seguido de unos trescientos mil ceros... Incluso si una máquina así funcionara a las frecuencias de los rayos cósmicos, los eones de la evolución galáctica no serían nada comparados con el tiempo de un viaje a través de un ciclo de ese tipo.

En el caso de las máquinas de memoria finita no deterministas , también es posible decidir si la máquina se detiene en ninguna, algunas o todas las secuencias posibles de decisiones no deterministas, enumerando los estados después de cada decisión posible.

• 1900  ( 1900 ) : David Hilbert plantea sus "23 preguntas" (ahora conocidas como los problemas de Hilbert ) en el Segundo Congreso Internacional de Matemáticos en París. "De estas, la segunda era la de demostrar la consistencia de los ' axiomas de Peano ' de los que, como había demostrado, dependía el rigor de las matemáticas". ^{[ 10 ]}
• 1920  ( 1920 )  – 1921  ( 1921 ) : Emil Post explora el problema de la parada para los sistemas de etiquetas , considerándolo como un candidato a ser irresoluble. ^{[ 11 ]} Su irresolubilidad no se estableció hasta mucho más tarde, por Marvin Minsky . ^{[ 12 ]}
• 1928  ( 1928 ) : Hilbert reformula su «Segundo Problema» en el Congreso Internacional de Bolonia. ^{[ 13 ]} Planteó tres preguntas: 1. ¿Eran las matemáticas completas ? 2. ¿Eran las matemáticas consistentes ? 3. ¿Eran las matemáticas decidibles ? ^{[ 14 ]} La tercera pregunta se conoce como el Entscheidungsproblem (Problema de Decisión). ^{[ 15 ]}
• 1930  ( 1930 ) : Kurt Gödel anuncia una demostración como respuesta a las dos primeras preguntas de Hilbert de 1928. ^{[ 16 ]} "Al principio, él [Hilbert] solo estaba enojado y frustrado, pero luego comenzó a tratar de abordar el problema de manera constructiva... El propio Gödel sintió —y expresó esa idea en su artículo— que su trabajo no contradecía el punto de vista formalista de Hilbert". ^{[ 17 ]}
• 1931  ( 1931 ) : Gödel publica "Sobre proposiciones formalmente indecidibles de Principia Mathematica y sistemas relacionados I". ^{[ 18 ]}
• 19  de abril  de 1935  ( 1935-04-19 ) : Alonzo Church publica "Un problema irresoluble de la teoría elemental de números", en el que propone que la noción intuitiva de una función efectivamente calculable puede formalizarse mediante las funciones recursivas generales o, equivalentemente, mediante las funciones definibles por lambda . Demuestra que el problema de la parada para el cálculo lambda (es decir, si una expresión lambda dada tiene una forma normal ) no es efectivamente calculable. ^{[ 19 ]}
• 1936  ( 1936 ) : Church publica la primera prueba de que el Entscheidungsproblem es irresoluble, utilizando una noción de cálculo mediante funciones recursivas . ^{[ 20 ]}
• 7  de octubre  de 1936  ( 1936-10-07 ) : Se recibe el artículo de Emil Post titulado "Procesos combinatorios finitos. Formulación I". Post añade a su "proceso" una instrucción "(C) Stop". Denominó a dicho proceso "tipo 1... si el proceso que determina termina para cada problema específico". ^{[ 21 ]}
• Mayo  de 1936  ( 1936-05 )  – Enero  de 1937  ( 1937-01 ) : El artículo de Alan Turing, «Sobre los números computables con una aplicación al problema de decisión» , se imprimía en mayo de 1936 y se publicaba en enero de 1937. ^{[ 22 ]} Turing demostró que tres problemas eran indecidibles: el problema de la «satisfacción», el problema de la «impresión» y el problema de decisión . ^{[ 23 ]} La demostración de Turing difiere de la de Church al introducir la noción de computación por máquina. Este es uno de los «primeros ejemplos de problemas de decisión que se demostraron irresolubles». ^{[ 24 ]}
• 1939  ( 1939 ) : J. Barkley Rosser observa la equivalencia esencial del "método efectivo" definido por Gödel, Church y Turing. ^{[ 25 ]}
• 1943  ( 1943 ) : En un artículo, Stephen Kleene afirma que "Al establecer una teoría algorítmica completa, lo que hacemos es describir un procedimiento... que necesariamente termina y de tal manera que a partir del resultado podemos leer una respuesta definida, 'Sí' o 'No', a la pregunta, '¿Es verdadero el valor del predicado?'".
• 1952  ( 1952 ) : Kleene incluye una discusión sobre la imposibilidad de resolver el problema de la parada para las máquinas de Turing y lo reformula en términos de máquinas que "eventualmente se detienen", es decir, se detienen: "...no existe un algoritmo para decidir si una máquina dada, cuando se inicia desde una situación dada, eventualmente se detiene ." ^{[ 24 ]}
• 1952  ( 1952 ) : Martin Davis utiliza el término «problema de parada» en una serie de conferencias en el Laboratorio de Sistemas de Control de la Universidad de Illinois en 1952. Es probable que este sea el primer uso de este término. ^{[ 26 ]}

Muchos artículos y libros de texto remiten la definición y la prueba de la indecidibilidad del problema de la parada al artículo de Turing de 1936. Sin embargo, esto no es correcto. ^{[ 23 ] [ 27 ]} Turing no utilizó los términos "halt" ni "halting" en ninguna de sus obras publicadas, incluido su artículo de 1936. ^{[ 28 ]} Una búsqueda en la literatura académica de 1936 a 1958 mostró que el primer material publicado que utilizó el término "problema de la parada" fue Rogers (1957) . Sin embargo, Rogers dice que tenía disponible un borrador de Davis (1958) , ^{[ 23 ]} y Martin Davis afirma en la introducción que "el experto tal vez encuentre alguna novedad en la organización y el tratamiento de los temas", ^{[ 29 ]} por lo que la terminología debe atribuirse a Davis. ^{[ 23 ] [ 27 ]} Davis afirmó en una carta que se había referido al problema de la parada desde 1952. ^{[ 26 ]} El uso en el libro de Davis es el siguiente: ^{[ 30 ]}

"[...] deseamos determinar si [una máquina de Turing] Z, al ser colocada en un estado inicial dado, eventualmente se detendrá o no. A este problema lo llamamos el problema de la parada para Z. [...]

Teorema 2.2 Existe una máquina de Turing cuyo problema de parada es irresoluble recursivamente .

Un problema relacionado es el problema de impresión para una máquina de Turing simple Z con respecto a un símbolo S _i ".

Un posible precursor de la formulación de Davis es la declaración de Kleene de 1952, que difiere únicamente en la redacción: ^{[ 23 ] [ 24 ]}

No existe ningún algoritmo para decidir si una máquina determinada, al ser puesta en marcha desde una situación dada, finalmente se detendrá.

El problema de la parada es Turing equivalente tanto al problema de impresión de Davis («¿imprime alguna vez una máquina de Turing que parte de un estado dado un símbolo dado?») como al problema de impresión considerado en el artículo de Turing de 1936 («¿imprime alguna vez una máquina de Turing que parte de una cinta en blanco un símbolo dado?»). Sin embargo, la equivalencia de Turing es bastante imprecisa y no significa que los dos problemas sean iguales. Hay máquinas que imprimen pero no se detienen, y que se detienen pero no imprimen. Los problemas de impresión y parada abordan cuestiones diferentes y presentan importantes diferencias conceptuales y técnicas. Por lo tanto, Davis simplemente estaba siendo modesto cuando dijo: ^{[ 23 ]}

También cabe mencionar que la imposibilidad de resolver esencialmente estos problemas fue demostrada por primera vez por Turing.

Se dice que un problema de decisión es decidible si existe un algoritmo que siempre da la respuesta correcta, y un problema indecidible si no existe tal algoritmo. En su demostración original, Turing formalizó el concepto de algoritmo introduciendo las máquinas de Turing . Sin embargo, el resultado no es exclusivo de ellas; se aplica igualmente a cualquier otro modelo de computación que sea equivalente en su potencia computacional a las máquinas de Turing, como los algoritmos de Markov , el cálculo lambda , los sistemas de Post , las máquinas de registro o los sistemas de etiquetas .

Lo importante es que la formalización permita una correspondencia directa entre algoritmos y algún tipo de dato sobre el que puedan operar. Por ejemplo, si el formalismo permite que los algoritmos definan funciones sobre cadenas (como las máquinas de Turing), entonces debería existir una correspondencia entre estos algoritmos y las cadenas; y si el formalismo permite que los algoritmos definan funciones sobre números naturales (como las funciones computables ), entonces también debería existir una correspondencia entre los algoritmos y los números naturales. La correspondencia con cadenas suele ser la más directa, pero las cadenas sobre un alfabeto de n caracteres también pueden asignarse a números interpretándolas como números en un sistema numérico n -ario .

Existen muchos problemas indecidibles; cualquier conjunto cuyo grado de Turing sea igual al del problema de la parada es una formulación de este tipo. Ejemplos de tales conjuntos incluyen, además del problema de la parada:

• { i | el programa i finalmente se detiene cuando se ejecuta con la entrada 0}
• { i | existe una entrada x tal que el programa i finalmente se detiene cuando se ejecuta con la entrada x }.

Christopher Strachey esbozó una demostración por contradicción de que el problema de la parada no tiene solución. ^{[ 32 ] [ 33 ]} La demostración procede de la siguiente manera: Supongamos que existe una función computable total halts(f) que devuelve verdadero si la subrutina f se detiene (cuando se ejecuta sin entradas) y falso en caso contrario. Ahora consideremos la siguiente subrutina:

def g () -> None : if halts ( g ): loop_forever ()

La función `halts(g)` debe devolver verdadero o falso, ya que se asumió que `halts` era una función computable total . Si `halts(g)` devuelve verdadero, entonces `g` llamará a `loop_forever` y nunca se detendrá, lo cual es una contradicción. Si `halts(g) ` devuelve falso, entonces `g` se detendrá, porque no llamará a `loop_forever` ; esto también es una contradicción. En resumen, `g` hace lo contrario de lo que ` halts` indica que debería hacer, por lo que `halts(g)` no puede devolver un valor de verdad que sea consistente con si `g` se detiene o no. Por lo tanto, la suposición inicial de que `halts` es una función computable total debe ser falsa.

El concepto anterior muestra el método general de la demostración, pero la función computable ` halts` no toma directamente una subrutina como argumento; en cambio, toma el código fuente de un programa. Además, la definición de `g` es autorreferencial . Una demostración rigurosa aborda estos problemas. El objetivo general es demostrar que no existe una función computable total que decida si un programa arbitrario `i` se detiene ante una entrada arbitraria `x` ; es decir, la siguiente función `h` (de "halts") no es computable: ^{[ 34 ]}

${\displaystyle h(i,x)={\begin{cases}1&{\text{si }}{\text{ el programa }}i{\text{ se detiene en la entrada }}x,\\0&{\text{en otro caso.}}\end{cases}}}$

Aquí, el programa i se refiere al i -ésimo programa en una enumeración de todos los programas de un modelo de computación Turing-completo fijo.

La demostración procede estableciendo directamente que ninguna función computable total con dos argumentos puede ser la función requerida h . Como en el esbozo del concepto, dada cualquier función binaria computable total f , la siguiente función parcial g también es computable por algún programa e :

${\displaystyle g(i)={\begin{cases}0&{\text{si }}f(i,i)=0,\\{\text{indefinido}}&{\text{en otro caso.}}\end{cases}}}$

La verificación de que g es computable se basa en las siguientes construcciones (o sus equivalentes):

• subprogramas computables (el programa que calcula f es un subprograma en el programa e ),
• duplicación de valores (el programa e calcula las entradas i , i para f a partir de la entrada i para g ),
• ramificación condicional (el programa e selecciona entre dos resultados dependiendo del valor que calcula para f ( i , i )),
• no producir un resultado definido (por ejemplo, mediante un bucle infinito),
• devuelve un valor de 0.

El siguiente pseudocódigo para e ilustra una forma sencilla de calcular g :

procedimiento e ( i ) : si f ( i , i ) == 0 entonces devolver 0 sino bucle infinito

Dado que g es parcialmente computable, debe existir un programa e que calcule g , suponiendo que el modelo de computación sea Turing-completo. Este programa es uno de todos los programas en los que se define la función de parada h . El siguiente paso de la demostración muestra que h ( e , e ) no tendrá el mismo valor que f ( e , e ).

De la definición de g se deduce que debe cumplirse exactamente uno de los dos casos siguientes:

• f ( e , e ) = 0 y por lo tanto g ( e ) = 0. En este caso, el programa e se detiene en la entrada e , por lo tanto h ( e , e ) = 1.
• f ( e , e ) ≠ 0 y por lo tanto g ( e ) no está definido. En este caso, el programa e no se detiene en la entrada e , por lo que h ( e , e ) = 0.

En cualquier caso, f no puede ser la misma función que h . Dado que f era una función total computable arbitraria con dos argumentos, todas esas funciones deben ser diferentes de h .

Esta demostración es análoga al argumento diagonal de Cantor . Se puede visualizar una matriz bidimensional con una columna y una fila para cada número natural, como se indica en la tabla anterior. El valor de f ( i , j ) se coloca en la columna i , fila j . Dado que se supone que f es una función totalmente computable, cualquier elemento de la matriz se puede calcular usando f . La construcción de la función g se puede visualizar usando la diagonal principal de esta matriz. Si la matriz tiene un 0 en la posición ( i , i ), entonces g ( i ) es 0. De lo contrario, g ( i ) no está definida. La contradicción proviene del hecho de que hay alguna columna e de la matriz que corresponde a la propia g . Ahora supongamos que f fuese la función de parada h . Si g ( e ) está definida ( g ( e ) = 0 en este caso), entonces el programa e se detiene con la entrada e , por lo tanto f ( e,e ) = 1. Pero g ( e ) = 0 solo cuando f ( e,e ) = 0, lo que contradice f ( e,e ) = 1. De manera similar, si g ( e ) no está definida, entonces el programa e no se detiene con la entrada e , por lo tanto f ( e,e ) = 0, lo que lleva a g ( e ) = 0 bajo la construcción de g . Esto contradice la suposición de que g ( e ) no está definida. En ambos casos surge una contradicción. Por lo tanto, cualquier función computable arbitraria f no puede ser la función de parada h .

La prueba de Turing demuestra que no existe un método mecánico general (es decir, una máquina de Turing o un programa en algún modelo de computación equivalente ) para determinar si los algoritmos se detienen. Sin embargo, cada instancia individual del problema de la parada tiene una respuesta definitiva, que puede o no ser computable en la práctica. Dado un algoritmo y una entrada específicos, a menudo se puede demostrar si se detiene o no, y de hecho, los informáticos suelen hacerlo como parte de una prueba de corrección . Existen algunas heurísticas que se pueden utilizar de forma automatizada para intentar construir una prueba, las cuales suelen tener éxito en programas típicos. Este campo de investigación se conoce como análisis de terminación automatizado .

Se han establecido algunos resultados sobre el rendimiento teórico de las heurísticas del problema de la parada, en particular la fracción de programas de un tamaño dado que pueden ser clasificados correctamente por un algoritmo recursivo. Estos resultados no proporcionan cifras precisas porque las fracciones son incalculables y también dependen en gran medida de la codificación del programa elegida para determinar el "tamaño". Por ejemplo, consideremos clasificar los programas por su número de estados y utilizar un modelo específico de computación de "cinta semiinfinita de Turing" que genera un error (sin detenerse) si el programa se sale del lado izquierdo de la cinta.${\displaystyle \lim _{n\to \infty }P(x\,{\text{se detiene es decidible}}\mid x\,{\text{tiene}}\,n\,{\text{estados}})=1}$, sobre programas${\displaystyle x}$elegidos uniformemente por número de estados. Pero este resultado es en cierto sentido "trivial" porque estos programas decidibles son simplemente los que se desprenden de la cinta, y la heurística consiste simplemente en predecir que no se detendrán debido a un error. Por lo tanto, un detalle aparentemente irrelevante, a saber, el tratamiento de los programas con errores, puede resultar ser el factor decisivo para determinar la fracción de programas. ^{[ 36 ]}

Para evitar estos problemas, se han desarrollado varias nociones restringidas del "tamaño" de un programa. Una numeración densa de Gödel asigna números a los programas de tal manera que cada función computable aparece una fracción positiva en cada secuencia de índices del 1 al n, es decir, una Gödelización φ es densa si y solo si para todo${\displaystyle i}$, existe un${\displaystyle c>0}$de tal manera que${\displaystyle \liminf _{n\to \infty }\#\{j\in \mathbb {N} :0\leq j<n,\phi _{i}=\phi _{j}\}/n\geq c}$. Por ejemplo, una numeración que asigna índices${\displaystyle 2^{n}}$Para programas no triviales y todos los demás índices, el estado de error no es denso, pero existe una numeración de Gödel densa de programas Brainfuck sintácticamente correctos. ^{[ 37 ]} Una numeración de Gödel densa se denomina óptima si, para cualquier otra numeración de Gödel${\displaystyle \alpha }$, hay una función recursiva total 1-1${\displaystyle f}$y una constante${\displaystyle c}$de tal manera que para todos${\displaystyle i}$,${\displaystyle \alpha _{i}=\phi _{f(i)}}$y${\displaystyle f(i)\leq ci}$Esta condición garantiza que todos los programas tengan índices no mucho mayores que sus índices en cualquier otra numeración de Gödel. Las numeraciones de Gödel óptimas se construyen numerando las entradas de una máquina de Turing universal . ^{[ 38 ]} Una tercera noción de tamaño utiliza máquinas universales que operan sobre cadenas binarias y mide la longitud de la cadena necesaria para describir el programa de entrada. Una máquina universal U es una máquina para la cual para cada otra máquina V existe una función computable total h tal que${\displaystyle V(x)=U(h(x))}$Una máquina óptima es una máquina universal que alcanza la cota de invariancia de complejidad de Kolmogorov , es decir, para cada máquina V , existe c tal que para todas las salidas x , si un programa V de longitud n produce x , entonces existe un programa U de longitud como máximo${\displaystyle n+c}$generando x . ^{[ 39 ]}

Consideramos funciones computables parciales (algoritmos).${\displaystyle A}$. Para cada${\displaystyle n}$consideramos la fracción${\displaystyle \epsilon _ {n}(A)}$de errores entre todos los programas de tamaño métrico como máximo${\displaystyle n}$, contando cada programa${\displaystyle x}$para qué${\displaystyle A}$no termina, produce una respuesta de "no lo sé" o produce una respuesta incorrecta, es decir${\displaystyle x}$paradas y${\displaystyle A(x)}$salidas DOES_NOT_HALT, o${\displaystyle x}$no se detiene y${\displaystyle A(x)}$salidas HALTS. El comportamiento puede describirse de la siguiente manera, para Gödelizaciones densas y máquinas óptimas: ^{[ 37 ] [ 39 ]}

• Para cada algoritmo${\displaystyle A}$,${\displaystyle \liminf _{n\to \infty }\epsilon _{n}(A)>0}$En otras palabras, cualquier algoritmo tiene una tasa de error mínima positiva, incluso cuando el tamaño del problema se vuelve extremadamente grande.
• Existe${\displaystyle \epsilon >0}$de tal manera que para cada algoritmo${\displaystyle A}$,${\displaystyle \limsup _{n\to \infty }\epsilon _{n}(A)\geq \epsilon }$En otras palabras, existe una tasa de error positiva para la cual cualquier algoritmo tendrá un rendimiento peor que esa tasa de error con una frecuencia arbitraria, incluso a medida que el tamaño del problema crece indefinidamente.
• ${\displaystyle \inf _{A}\liminf _{n\to \infty }\epsilon _{n}(A)=0}$En otras palabras, existe una secuencia de algoritmos tal que la tasa de error se aproxima arbitrariamente a cero para una secuencia específica de tamaños crecientes. Sin embargo, este resultado permite secuencias de algoritmos que producen respuestas incorrectas.
• Si consideramos únicamente algoritmos "honestos" que pueden no estar definidos pero que nunca producen respuestas incorrectas, entonces, dependiendo de la métrica,${\displaystyle \inf _{A\,{\textrm {honesto}}}\liminf _{n\to \infty }\epsilon _{n}(A)}$puede ser 0 o no. En particular, es 0 para máquinas universales de total izquierdo, pero para máquinas efectivamente óptimas es mayor que 0. ^{[ 39 ]}

La naturaleza compleja de estos límites se debe al comportamiento oscilatorio de${\displaystyle \epsilon _ {n}(A)}$Existen variedades nuevas de programas que aparecen con poca frecuencia y que se presentan en "bloques" arbitrariamente grandes, y una fracción de repeticiones que crece constantemente. Si se incluyen completamente los bloques de variedades nuevas, la tasa de error es al menos${\displaystyle \epsilon }$, pero entre bloques la fracción de repeticiones correctamente categorizadas puede ser arbitrariamente alta. En particular, una heurística de "conteo" que simplemente recuerda las primeras N entradas y reconoce sus equivalentes permite alcanzar una tasa de error arbitrariamente baja infinitamente a menudo. ^{[ 37 ]}

Los conceptos planteados por los teoremas de incompletitud de Gödel son muy similares a los del problema de la parada, y las demostraciones son bastante parecidas. De hecho, una forma más débil del Primer Teorema de Incompletitud es una consecuencia directa de la indecidibilidad del problema de la parada. Esta forma más débil se diferencia del enunciado estándar del teorema de incompletitud al afirmar que es imposible una axiomatización efectiva de los números naturales que sea a la vez completa y sólida . La parte de "sólida" es el debilitamiento: implica que exigimos que el sistema axiomático en cuestión demuestre únicamente enunciados verdaderos sobre los números naturales. Dado que la solidez implica consistencia , esta forma más débil puede considerarse un corolario de la forma fuerte. Es importante observar que el enunciado de la forma estándar del Primer Teorema de Incompletitud de Gödel no se preocupa en absoluto por el valor de verdad de un enunciado, sino únicamente por la posibilidad de hallarlo mediante una demostración matemática .

La forma más débil del teorema se puede demostrar a partir de la indecidibilidad del problema de parada de la siguiente manera. ^{[ 40 ]} Supongamos que tenemos una axiomatización efectiva sólida (y por lo tanto consistente) y completa de todas las afirmaciones lógicas de primer orden verdaderas sobre los números naturales . Entonces podemos construir un algoritmo que enumere todas estas afirmaciones. Esto significa que hay un algoritmo N ( n ) que, dado un número natural n , calcula una afirmación lógica de primer orden verdadera sobre los números naturales, y que para todas las afirmaciones verdaderas, hay al menos un n tal que N ( n ) produce esa afirmación. Ahora supongamos que queremos decidir si el algoritmo con representación a se detiene en la entrada i . Sabemos que esta afirmación se puede expresar con una afirmación lógica de primer orden, digamos H ( a , i ). Dado que la axiomatización es completa, se deduce que o bien existe un n tal que N ( n ) = H ( a , i ) o bien existe un n ′ tal que N ( n ′ ) = ¬H ( a , i ). Por lo tanto, si iteramos sobre todos los n hasta encontrar H ( a , i ) o su negación, siempre nos detendremos, y además, la respuesta que nos dé será verdadera (por corrección). Esto significa que esto nos proporciona un algoritmo para resolver el problema de la parada. Dado que sabemos que no puede existir tal algoritmo, se deduce que la suposición de que existe una axiomatización efectiva, completa y correcta de todas las proposiciones verdaderas de lógica de primer orden sobre números naturales debe ser falsa.

El problema de la parada universal , también conocido (en teoría de la recursión ) como totalidad , es el problema de determinar si un programa informático dado se detendrá para cada entrada (el nombre totalidad proviene de la pregunta equivalente de si la función calculada es total ). Este problema no solo es indecidible, como lo es el problema de la parada, sino altamente indecidible. En términos de la jerarquía aritmética , es${\displaystyle \Pi _{2}^{0}}$-completo. ^{[ 42 ]}

Esto significa, en particular, que no se puede decidir ni siquiera con un oráculo para el problema de la parada.

Hay muchos programas que, para algunas entradas, devuelven una respuesta correcta al problema de la parada, mientras que para otras entradas no devuelven ninguna respuesta. Sin embargo, el problema "dado el programa p , ¿es un solucionador parcial de la parada?" (en el sentido descrito) es al menos tan difícil como el problema de la parada. Para ver esto, supongamos que existe un algoritmo PHSR ("reconocedor de solucionadores parciales de la parada") para hacer eso. Entonces se puede usar para resolver el problema de la parada, de la siguiente manera: Para probar si el programa de entrada x se detiene en y , construya un programa p que para la entrada ( x , y ) reporte verdadero y diverja para todas las demás entradas. Luego pruebe p con PHSR.

El argumento anterior es una reducción del problema de parada al reconocimiento PHS, y de la misma manera, problemas más difíciles como la parada en todas las entradas también pueden reducirse, lo que implica que el reconocimiento PHS no solo es indecidible, sino que ocupa un lugar más alto en la jerarquía aritmética , específicamente${\displaystyle \Pi _{2}^{0}}$-completo.

Una máquina de Turing con pérdida es una máquina de Turing en la que parte de la cinta puede desaparecer de forma no determinista. El problema de la parada es decidible para una máquina de Turing con pérdida, pero no recursivo primitivo . ^{[ 43 ]}

Una máquina con un oráculo para el problema de la parada puede determinar si determinadas máquinas de Turing se detendrán con determinadas entradas, pero no puede determinar, en general, si las máquinas equivalentes a sí mismas se detendrán.