Detener el problema - Halting problem

En la teoría de la computabilidad , el problema de la detención es el problema de determinar, a partir de una descripción de un programa de computadora arbitrario y una entrada, si el programa terminará de ejecutarse o continuará ejecutándose para siempre. Alan Turing demostró en 1936 que no puede existir un algoritmo general para resolver el problema de detención para todos los posibles pares de entrada de programa.

Para cualquier programa f que pueda determinar si los programas se detienen, un programa "patológico" g , llamado con alguna entrada, puede pasar su propia fuente y su entrada af y luego hacer específicamente lo contrario de lo que f predice que g hará. No f puede existir que las manijas este caso. Una parte clave de la demostración es una definición matemática de una computadora y un programa, que se conoce como máquina de Turing ; el problema de la detención es indecidible en las máquinas de Turing. Es uno de los primeros casos de problemas de decisión.demostrado ser irresoluble. Esta prueba es importante para los esfuerzos prácticos de la computación, ya que define una clase de aplicaciones que ninguna invención de programación puede realizar perfectamente.

Jack Copeland (2004) atribuye la introducción del término problema de detención al trabajo de Martin Davis en la década de 1950.

Fondo

El problema de la detención es un problema de decisión sobre las propiedades de los programas de computadora en un modelo de cálculo completo de Turing fijo , es decir, todos los programas que pueden escribirse en un lenguaje de programación dado que sea lo suficientemente general como para ser equivalente a una máquina de Turing. El problema es determinar, dado un programa y una entrada al programa, si el programa finalmente se detendrá cuando se ejecute con esa entrada. En este marco abstracto, no existen limitaciones de recursos sobre la cantidad de memoria o el tiempo requerido para la ejecución del programa; puede llevar un tiempo arbitrario y utilizar una cantidad arbitraria de espacio de almacenamiento antes de detenerse. La pregunta es simplemente si el programa dado se detendrá alguna vez en una entrada en particular.

Por ejemplo, en pseudocódigo , el programa

while (true) continue

no se detiene; más bien, continúa para siempre en un bucle infinito . Por otro lado, el programa

print "Hello, world!"

se detiene.

Si bien decidir si estos programas se detienen es simple, los programas más complejos resultan problemáticos. Una forma de solucionar el problema podría ser ejecutar el programa durante una serie de pasos y comprobar si se detiene. Pero si el programa no se detiene, se desconoce si finalmente se detendrá o se ejecutará para siempre. Turing demostró que no existe un algoritmo que siempre decida correctamente si, para un programa y una entrada arbitrarios dados, el programa se detiene cuando se ejecuta con esa entrada. La esencia de la prueba de Turing es que se puede hacer que cualquier algoritmo de este tipo se contradiga y, por lo tanto, no sea correcto.

Consecuencias de la programación

Algunos bucles infinitos pueden resultar muy útiles. Por ejemplo, los bucles de eventos se codifican normalmente como bucles infinitos. Sin embargo, la mayoría de las subrutinas están destinadas a finalizar (detenerse). En particular, en la computación dura en tiempo real , los programadores intentan escribir subrutinas que no solo están garantizadas para terminar (detenerse), sino que también están garantizadas para terminar antes de una fecha límite determinada.

A veces, estos programadores usan algún lenguaje de programación de propósito general (Turing-completo), pero intentan escribir en un estilo restringido, como MISRA C o SPARK , lo que facilita probar que las subrutinas resultantes terminan antes de la fecha límite establecida.

Otras veces, estos programadores aplican la regla del menor poder: utilizan deliberadamente un lenguaje informático que no es completamente Turing-completo. Con frecuencia, son lenguajes que garantizan el final de todas las subrutinas, como Coq .

Errores comunes

La dificultad del problema de la detención radica en el requisito de que el procedimiento de decisión debe funcionar para todos los programas e insumos. Un programa en particular se detiene en una entrada determinada o no se detiene. Considere un algoritmo que siempre responde "se detiene" y otro que siempre responde "no se detiene". Para cualquier programa y entrada específicos, uno de estos dos algoritmos responde correctamente, aunque nadie sepa cuál. Sin embargo, ninguno de los algoritmos resuelve el problema de la detención en general.

Hay programas ( intérpretes ) que simulan la ejecución de cualquier código fuente que se les proporcione. Dichos programas pueden demostrar que un programa se detiene si este es el caso: el propio intérprete eventualmente detendrá su simulación, lo que muestra que el programa original se detuvo. Sin embargo, un intérprete no se detendrá si su programa de entrada no se detiene, por lo que este enfoque no puede resolver el problema de la detención como se indicó; no responde correctamente "no se detiene" para los programas que no se detienen.

El problema de la detención es teóricamente decidible para los autómatas acotados lineales (LBA) o máquinas deterministas con memoria finita. Una máquina con memoria finita tiene un número finito de configuraciones y, por lo tanto, cualquier programa determinista en ella debe eventualmente detener o repetir una configuración previa:

... cualquier máquina de estados finitos, si se deja completamente a sí misma, eventualmente caerá 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 ... (cursiva en el original, Minsky 1967, p. 24)

Sin embargo, Minsky señala que una computadora con un millón de partes pequeñas, cada una con dos estados, tendría al menos 2 ^{1,000,000 de} estados posibles:

Este 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 evolución galáctica no serían nada comparados con el tiempo de un viaje a través de dicho ciclo ( Minsky 1967 p. 25):

Minsky afirma que, aunque una máquina puede ser finita, y los autómatas finitos "tienen una serie de limitaciones teóricas":

... las magnitudes involucradas deberían llevar a uno a sospechar que los teoremas y argumentos basados ​​principalmente en la mera finitud [del] diagrama de estados pueden no tener una gran importancia. (Minsky pág.25)

También se puede decidir automáticamente si una máquina no determinista con memoria finita se detiene en ninguna, algunas o todas las posibles secuencias de decisiones no deterministas, enumerando estados después de cada posible decisión.

Historia

El problema de la detención es históricamente importante porque fue uno de los primeros problemas que se demostró indecidible . (La prueba de Turing se imprimió en mayo de 1936, mientras que la prueba de Alonzo Church de la indecidibilidad de un problema en el cálculo lambda ya se había publicado en abril de 1936 [Church, 1936]). Posteriormente, se han descrito muchos otros problemas indecidibles.

Cronología

• 1900: David Hilbert plantea sus "23 preguntas" (ahora conocidas como problemas de Hilbert ) en el Segundo Congreso Internacional de Matemáticos en París. “De estos, el segundo fue el de probar la consistencia de los ' axiomas de Peano ' de los que, como había demostrado, dependía el rigor de las matemáticas”. (Hodges p. 83, comentario de Davis en Davis, 1965, p. 108)
• 1920-1921: Emil Post explora el problema de la interrupción de los sistemas de etiquetas , considerándolo como un candidato a la imposibilidad de resolver. ( Problemas absolutamente irresolubles y proposiciones relativamente indecidibles: descripción de una anticipación , en Davis, 1965, págs. 340–433.) Su insolubilidad no fue establecida hasta mucho más tarde, por Marvin Minsky (1967).
• 1928: Hilbert reformula su "Segundo problema" en el Congreso Internacional de Bolonia. (Reid págs. 188-189) Hodges afirma que planteó tres preguntas: es decir, # 1: ¿Fueron completas las matemáticas ? # 2: ¿Las matemáticas fueron consistentes ? # 3: ¿ Fueron las matemáticas decidibles ? (Hodges pág.91). La tercera pregunta se conoce como Entscheidungsproblem (Problema de decisión). (Hodges pág.91, Penrose pág.34)
• 1930: Kurt Gödel anuncia una prueba como respuesta a las dos primeras preguntas de Hilbert de 1928 [cf. Reid p. 198]. "Al principio él [Hilbert] solo estaba enojado y frustrado, pero luego comenzó a tratar de abordar el problema de manera constructiva ... Gödel mismo sintió, y expresó el pensamiento en su artículo, que su trabajo no contradecía el punto formalista de Hilbert de ver "(Reid pág. 199)
• 1931: Gödel publica "Sobre proposiciones formalmente indecidibles de Principia Mathematica y sistemas relacionados I", (reimpreso en Davis, 1965, p. 5 y siguientes)
• 19 de abril de 1935: Alonzo Church publica "Un problema irresoluble de la teoría de números elementales", que propone que la noción intuitiva de una función efectivamente calculable puede ser formalizada por las funciones recursivas generales o de manera equivalente por las funciones definibles por lambda . Demuestra que el problema de detención para el cálculo lambda (es decir, si una expresión lambda dada tiene una forma normal ) no es efectivamente calculable.
• 1936: Church publica la primera prueba de que el problema de la Entscheidung es irresoluble. ( A Note on the Entscheidungsproblem , reimpreso en Davis, 1965, p. 110.)
• 7 de octubre de 1936: Se recibe el artículo de Emil Post "Procesos combinatorios finitos. Formulación I". Post agrega a su "proceso" una instrucción "(C) Detener". Llamó a dicho proceso "tipo 1 ... si el proceso que determina termina para cada problema específico". (Davis, 1965, pág.289 y siguientes)
• 1937: Alan Turing papel 's Sobre los números computables con una aplicación a la Entscheidungsproblem alcanza impresión en enero de 1937 (reimpreso en Davis, 1965, p 115.). La demostración de Turing se aparta del cálculo mediante funciones recursivas e introduce la noción de cálculo por máquina. Stephen Kleene (1952) se refiere a esto como uno de los "primeros ejemplos de problemas de decisión que resultaron insolubles".
• 1939: J. Barkley Rosser observa la equivalencia esencial de "método efectivo" definido por Gödel, Church y Turing (Rosser en Davis, 1965, p. 223, "Exposición informal de pruebas del teorema de Gödel y el teorema de Church")
• 1943: En un artículo, Stephen Kleene afirma que "Al establecer una teoría algorítmica completa, lo que hacemos es describir un procedimiento ... cuyo procedimiento necesariamente termina y de tal manera que del resultado podemos leer una respuesta definitiva, 'Sí 'o' No 'a la pregunta' ¿Es verdadero el valor del predicado? '".
• 1952: Kleene (1952) Capítulo XIII ("Funciones computables") incluye una discusión sobre la imposibilidad de resolver el problema de la detención para las máquinas de Turing y lo reformula en términos de máquinas que "eventualmente se detienen", es decir, se detienen: "... no hay algoritmo para decidir si una máquina determinada, cuando se inicia desde una situación determinada, finalmente se detiene ". (Kleene (1952) pág.382)
• 1952: " Martin Davis cree que es probable que haya utilizado por primera vez el término 'problema de detención' en una serie de conferencias que dio en el Laboratorio de Sistemas de Control de la Universidad de Illinois en 1952 (carta de Davis a Copeland, 12 de diciembre de 2001). " (Nota a pie de página 61 en Copeland (2004) págs. 40 y siguientes)

Formalización

En su prueba original, Turing formalizó el concepto de algoritmo al introducir las máquinas de Turing . Sin embargo, el resultado no es específico para ellos; se aplica igualmente a cualquier otro modelo de cálculo que sea equivalente en su poder computacional a las máquinas de Turing, como los algoritmos de Markov , el cálculo Lambda , los sistemas Post , las máquinas de registro o los sistemas de etiquetas .

Lo importante es que la formalización permite un mapeo sencillo de algoritmos a algún tipo de datos sobre los que el algoritmo puede operar. Por ejemplo, si el formalismo permite que los algoritmos definan funciones sobre cadenas (como las máquinas de Turing), entonces debería haber una asignación de estos algoritmos a cadenas, y si el formalismo permite que los algoritmos definan funciones sobre números naturales (como funciones computables ), entonces debería haber ser un mapeo de algoritmos a números naturales. La asignación a cadenas suele ser la más sencilla, pero las cadenas sobre un alfabeto con n caracteres también se pueden asignar a números interpretándolos como números en un sistema numérico n -ary .

Representación como conjunto

La representación convencional de problemas de decisión es el conjunto de objetos que poseen la propiedad en cuestión. El set que se detiene

K = {( i , x ) | el programa i se detiene cuando se ejecuta en la entrada x }

representa el problema de la detención.

Este conjunto se puede enumerar de forma recursiva , lo que significa que hay una función computable que enumera todos los pares ( i ,  x ) que contiene. Sin embargo, el complemento de este conjunto no se puede enumerar de forma recursiva.

Hay muchas formulaciones equivalentes del problema de la detención; cualquier conjunto cuyo grado de Turing sea igual al del problema de detención es una formulación de este tipo. Ejemplos de tales conjuntos incluyen:

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

Concepto de prueba

Christopher Strachey esbozó una prueba por contradicción de que el problema de la detención no tiene solución. La demostración procede de la siguiente manera: Suponga que existe una función calculable total se detiene (f) que devuelve verdadero si la subrutina f se detiene (cuando se ejecuta sin entradas) y devuelve falso en caso contrario. Ahora considere la siguiente subrutina:

def g():
    if halts(g):
        loop_forever()

halts (g) debe devolver verdadero o falso, porque se asumió que las detenciones eran totales . 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 general, g hace lo contrario de lo que hats dice que debería hacer g , por lo que hats (g) no puede devolver un valor de verdad que sea consistente con si g se detiene. Por lo tanto, la suposición inicial de que se detiene es una función computable total debe ser falsa.

Boceto de prueba rigurosa

El concepto anterior muestra el método general de la demostración, pero la función calculable se detiene no toma directamente una subrutina como argumento; en su lugar, toma el código fuente de un programa. Además, la definición de g es autorreferencial . Una prueba rigurosa aborda estos problemas. El objetivo general es mostrar que no existe una función computable total que decida si un programa arbitrario i se detiene en una entrada arbitraria x ; es decir, la siguiente función h (para "se detiene") no es computable (Penrose 1990, p. 57-63):

${\ displaystyle h (i, x) = {\ begin {cases} 1 & {\ text {if}} {\ text {program}} i {\ text {se detiene en la entrada}} x, \\ 0 & {\ text { de lo contrario.}} \ end {cases}}}$

Aquí el programa i se refiere al i- ésimo programa en una enumeración de todos los programas de un modelo de cálculo completo de Turing 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 bosquejo 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 {if}} f (i, i) = 0, \\ {\ text {undefined}} & {\ text {de lo contrario.}} \ finalizar {casos}}}$

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 ),
• bifurcació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, haciendo un bucle para siempre),
• devolviendo un valor de 0.

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

procedure compute_g(i):
    if f(i, i) == 0 then
        return 0
    else
        loop forever

Dado que g es computable parcial, debe haber un programa e que calcule g , asumiendo que el modelo de cálculo es 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 entonces g ( e ) = 0. En este caso h ( e , e ) = 1, porque el programa e se detiene en la entrada e .
• f ( e , e ) ≠ 0 y, por lo tanto, g ( e ) no está definida. En este caso h ( e , e ) = 0, porque el programa e no se detiene en la entrada e .

En cualquier caso, f no puede ser la misma función que h . Como f era una función calculable total arbitraria con dos argumentos, todas esas funciones deben diferir 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 . Debido a que se supone que f es una función calculable total, 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á definido. La contradicción proviene del hecho de que hay alguna columna e de la matriz correspondiente a g misma. Ahora suponga que f era la función de detención h , si g ( e ) está definida ( g ( e ) = 0 en este caso), g ( e ) se detiene entonces f ( e, e ) = 1. Pero g ( e ) = 0 solo cuando f ( e, e ) = 0, contradiciendo f ( e, e ) = 1. De manera similar, si g ( e ) no está definida, entonces la función de detención f ( e, e ) = 0, lo que lleva a g ( e) ) = 0 bajo la construcción de g . Esto contradice el supuesto de que g ( e ) no está definido. En ambos casos surge la contradicción. Por lo tanto, cualquier función f calculable arbitraria no puede ser la función de detención h .

Teoría de la computabilidad

Un método típico para probar que un problema es indecidible es reducirlo al problema de la detención. Por ejemplo, no puede haber un algoritmo general que decida si un enunciado dado sobre números naturales es verdadero o falso. La razón de esto es que la proposición que indica que cierto programa se detendrá dada una determinada entrada puede convertirse en una proposición equivalente sobre números naturales. Si un algoritmo pudiera encontrar el valor de verdad de cada enunciado sobre números naturales, ciertamente podría encontrar el valor de verdad de éste; pero eso determinaría si el programa original se detiene.

El teorema de Rice generaliza el teorema de que el problema que se detiene no tiene solución. Establece que para cualquier propiedad no trivial, no existe un procedimiento de decisión general que, para todos los programas, decida si la función parcial implementada por el programa de entrada tiene esa propiedad. (Una función parcial es una función que no siempre puede producir un resultado, por lo que se utiliza para modelar programas, que pueden producir resultados o no detenerse). Por ejemplo, la propiedad "detener para la entrada 0" es indecidible. Aquí, "no trivial" significa que el conjunto de funciones parciales que satisfacen la propiedad no es ni el conjunto vacío ni el conjunto de todas las funciones parciales. Por ejemplo, "se detiene o no se detiene en la entrada 0" es claramente cierto para todas las funciones parciales, por lo que es una propiedad trivial y puede decidirse mediante un algoritmo que simplemente informa "verdadero". Además, este teorema sólo se aplica a las propiedades de la función parcial implementada por el programa; El teorema de Rice no se aplica a las propiedades del programa en sí. Por ejemplo, "detener en la entrada 0 dentro de 100 pasos" no es una propiedad de la función parcial implementada por el programa; es una propiedad del programa que implementa la función parcial y es muy decidible.

Gregory Chaitin ha definido una probabilidad de detención , representada por el símbolo Ω , un tipo de número real que se dice informalmente que representa la probabilidad de que un programa producido al azar se detenga. Estos números tienen el mismo grado de Turing que el problema de la detención. Es un número normal y trascendental que se puede definir pero no se puede calcular por completo . Esto significa que se puede probar que no existe un algoritmo que produzca los dígitos de Ω, aunque sus primeros dígitos se pueden calcular en casos simples.

Si bien la prueba de Turing muestra que no puede haber un método o algoritmo general para determinar si los algoritmos se detienen, las instancias individuales de ese problema pueden muy bien ser susceptibles de ser atacadas. Dado un algoritmo específico, a menudo se puede demostrar que debe detenerse por cualquier entrada y, de hecho, los científicos informáticos a menudo hacen eso como parte de una prueba de corrección . Pero cada prueba debe desarrollarse específicamente para el algoritmo en cuestión; No existe una forma mecánica general de determinar si los algoritmos de una máquina de Turing se detienen. Sin embargo, hay algunas heurísticas que se pueden utilizar de forma automatizada para intentar construir una prueba, que suele tener éxito en programas típicos. Este campo de investigación se conoce como análisis de terminación automatizado .

Dado que la respuesta negativa al problema que se detiene muestra que hay problemas que no pueden ser resueltos por una máquina de Turing, la tesis de Church-Turing limita lo que puede lograrse con cualquier máquina que implemente métodos efectivos . Sin embargo, no todas las máquinas concebibles para la imaginación humana están sujetas a la tesis de Church-Turing (por ejemplo, máquinas de oráculo ). Es una cuestión abierta si puede haber procesos físicos deterministas reales que, a la larga, eluden la simulación por una máquina de Turing y, en particular, si cualquier proceso hipotético de este tipo podría aprovecharse de manera útil en la forma de una máquina de calcular (una hipercomputadora ). eso podría resolver el problema de la detención de una máquina de Turing, entre otras cosas. También es una pregunta abierta si tales procesos físicos desconocidos están involucrados en el funcionamiento del cerebro humano , y si los humanos pueden resolver el problema de la detención (Copeland 2004, p. 15).

Teoremas de incompletitud de Gödel

Los conceptos planteados por los teoremas de incompletitud de Gödel son muy similares a los planteados por el problema de la detención, y las demostraciones son bastante similares. De hecho, una forma más débil del primer teorema de incompletitud es una consecuencia fácil de la indecidibilidad del problema de la detención. Esta forma más débil se diferencia del enunciado estándar del teorema de incompletitud al afirmar que una axiomatización de los números naturales que sea completa y sólida es imposible. La parte "sólida" es el debilitamiento: significa que requerimos que el sistema axiomático en cuestión pruebe sólo enunciados verdaderos sobre números naturales. Dado que la solidez implica consistencia , esta forma más débil puede verse como 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 tiene nada que ver con el valor de verdad de un enunciado, sino que solo se refiere a la cuestión de si es posible encontrarlo a través de una demostración matemática .

La forma más débil del teorema se puede demostrar a partir de la indecidibilidad del problema de detención como sigue. Supongamos que tenemos una axiomatización sólida (y por tanto coherente) y completa de todos los enunciados lógicos de primer orden verdaderos sobre los números naturales . Entonces podemos construir un algoritmo que enumere todas estas declaraciones. Esto significa que hay un algoritmo N ( n ) que, dado un número natural n , calcula un enunciado lógico de primer orden verdadero sobre números naturales, y que para todos los enunciados verdaderos, hay al menos uno n tal que N ( n ) produce esa declaración. Ahora suponga que queremos decidir si el algoritmo con representación a se detiene en la entrada i . Sabemos que este enunciado se puede expresar con un enunciado lógico de primer orden, digamos H ( a , i ). Dado que la axiomatización es completa, se deduce que o hay una n tal que N ( n ) = H ( a , i ) o hay una n ' tal que N ( n' ) = ¬ H ( a , i ). Entonces, si iteramos sobre todo n hasta que encontremos H ( a , i ) o su negación, siempre nos detendremos y, además, la respuesta que nos dé será verdadera (por solidez). Esto significa que esto nos da un algoritmo para decidir el problema de la detención. Como sabemos que no puede haber tal algoritmo, se deduce que la suposición de que existe una axiomatización consistente y completa de todos los enunciados lógicos de primer orden verdaderos sobre números naturales debe ser falsa.

Generalización

Se pueden encontrar muchas variantes del problema de la detención en los libros de texto de computabilidad (por ejemplo, Sipser 2006, Davis 1958, Minsky 1967, Hopcroft y Ullman 1979, Börger 1989). Por lo general, su indecidibilidad se deriva de la reducción del problema estándar de detención. Sin embargo, algunos de ellos tienen un mayor grado de insolubilidad . Los siguientes dos ejemplos son típicos.

Deteniendo todas las entradas

El problema de la detención universal , también conocido (en la teoría de la recursividad ) como totalidad , es el problema de determinar si un programa de computadora 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 sólo es indecidible, como problema que se detiene, sino altamente indecidible. En términos de jerarquía aritmética , es -completo (Börger 1989, p. 121). ${\ Displaystyle \ Pi _ {2} ^ {0}}$

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

Reconociendo soluciones parciales

Hay muchos programas que, para algunas entradas, devuelven una respuesta correcta al problema de detención, mientras que para otras entradas no devuelven una respuesta en absoluto. Sin embargo, el problema "dado el programa p , es un solucionador de detenciones parciales" (en el sentido descrito) es al menos tan difícil como el problema de detenciones. Para ver esto, suponga que hay un algoritmo PHSR ("reconocedor de solucionador de detención parcial") para hacer eso. Luego se puede usar para resolver el problema de detención, como sigue: Para probar si el programa de entrada x se detiene en y , construya un programa p que en la entrada ( x , y ) informe verdadero y diverja en todas las demás entradas. Luego pruebe p con PHSR.

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

Computación con pérdidas

Una máquina de Turing con pérdidas es una máquina de Turing en la que parte de la cinta puede desaparecer de forma no determinista. El problema de la detención es decidible para la máquina de Turing con pérdidas, pero no es recursivo primitivo .

Máquinas Oracle

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

Ver también

• Castor ocupado
• Teorema de incompletitud de Gödel
• Controversia Brouwer-Hilbert
• Complejidad de Kolmogorov
• Problema de P versus NP
• Análisis de terminación
• Tiempo de ejecución en el peor de los casos

Notas

Referencias

• Turing, AM (1937). "Sobre números computables, con una aplicación al Entscheidungsproblem" . Actas de la London Mathematical Society . Wiley. t2-42 (1): 230-265. doi : 10.1112 / plms / s2-42.1.230 . ISSN  0024-6115 ., Turing, AM (1938). "Sobre números computables, con una aplicación al Entscheidungsproblem. Una corrección" . Actas de la London Mathematical Society . Wiley. p. 2-43 (1): 544-546. doi : 10.1112 / plms / s2-43.6.544 . ISSN  0024-6115 .Este es el documento de época en el que Turing define las máquinas de Turing , formula el problema de la detención y muestra que (así como el problema de Entscheidungsproblem ) es irresoluble.
• Sipser, Michael (2006). "Sección 4.2: El problema de la detención" . Introducción a la Teoría de la Computación (Segunda ed.). Publicación de PWS. págs.  173-182 . ISBN 0-534-94728-X.
• c2: Problema de detención
• Iglesia, Alonzo (1936). "Un problema insoluble de la teoría de números elemental". Revista Estadounidense de Matemáticas . 58 (2): 345–363. doi : 10.2307 / 2371045 . JSTOR  2371045 .
• B. Jack Copeland ed. (2004), The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma, Clarendon Press (Oxford University Press), Oxford Reino Unido, ISBN  0-19-825079-7 .
• Davis, Martín (1965). Los artículos básicos e indecidibles sobre proposiciones indecidibles, problemas irresolubles y funciones computables . Nueva York: Raven Press.. El artículo de Turing es el número 3 de este volumen. Los artículos incluyen los de Godel, Church, Rosser, Kleene y Post.
• Davis, Martin (1958). Computabilidad e insolubilidad . Nueva York: McGraw-Hill..
• Alfred North Whitehead y Bertrand Russell , Principia Mathematica to * 56, Cambridge at the University Press, 1962. Re: el problema de las paradojas, los autores discuten el problema de que un conjunto no sea un objeto en ninguna de sus "funciones determinantes", en particular "Introducción, Cap. 1 p. 24" ... dificultades que surgen en la lógica formal ", y Cap. 2.I." El principio del círculo vicioso "p. 37 y siguientes, y Cap. 2.VIII." Las contradicciones "pág. 60ss.
• Martin Davis , "What is a computation", en Mathematics Today , Lynn Arthur Steen, Vintage Books (Random House), 1980. Un pequeño artículo maravilloso, quizás el mejor escrito sobre Máquinas de Turing para los no especialistas. Davis reduce la máquina de Turing a un modelo mucho más simple basado en el modelo de cálculo de Post. Discute la prueba de Chaitin . Incluye pequeñas biografías de Emil Post , Julia Robinson .
• Marvin Minsky , Computación: Máquinas finitas e infinitas , Prentice-Hall, Inc., Nueva Jersey, 1967. Véase el capítulo 8, Sección 8.2 "Inestabilidad del problema de detención".
• Roger Penrose , The Emperor's New Mind: Concerning Computers, Minds and the Laws of Physics , Oxford University Press , Oxford, Inglaterra, 1990 (con correcciones). Cf. Capítulo 2, "Algoritmos y máquinas de Turing". Una presentación demasiado complicada (ver el artículo de Davis para un mejor modelo), pero una presentación completa de las máquinas de Turing y el problema de la detención, y el cálculo Lambda de Church.
• John Hopcroft y Jeffrey Ullman , Introducción a la teoría, los lenguajes y la computación de los autómatas , Addison-Wesley, Reading Mass, 1979. Consulte el capítulo 7 "Máquinas de Turing". Un libro centrado en la interpretación automática de "lenguajes", NP-Completeness, etc.
• Andrew Hodges , Alan Turing: The Enigma , Simon and Schuster , Nueva York. Cf. Capítulo "El espíritu de la verdad" para una historia que conduzca y una discusión de su prueba.
• Constance Reid , Hilbert , Copernicus: Springer-Verlag, Nueva York, 1996 (publicado por primera vez en 1970). Historia fascinante de las matemáticas y la física alemanas desde la década de 1880 hasta la de 1930. En sus páginas aparecen cientos de nombres familiares para matemáticos, físicos e ingenieros. Quizás empañado por ninguna referencia abierta y pocas notas a pie de página: Reid afirma que sus fuentes fueron numerosas entrevistas con aquellos que conocían personalmente a Hilbert, y las cartas y documentos de Hilbert.
• Edward Beltrami , ¿Qué es Random? El azar y el orden en las matemáticas y la vida , Copérnico: Springer-Verlag, Nueva York, 1999. Una lectura agradable y suave para los no especialistas con inclinaciones matemáticas, pone las cosas más difíciles al final. Tiene un modelo de máquina de Turing. Analiza las contribuciones de Chaitin .
• Moore, Cristopher ; Mertens, Stephan (2011), La naturaleza de la computación , Oxford University Press, ISBN 9780191620805
• Ernest Nagel y James R. Newman , Godel's Proof , New York University Press, 1958. Maravilloso escrito sobre un tema muy difícil. Para los no especialistas con inclinaciones matemáticas. Analiza la prueba de Gentzen en las páginas 96–97 y notas al pie. Los apéndices discuten brevemente los axiomas de Peano e introducen amablemente a los lectores a la lógica formal.
• Taylor Booth , Sequential Machines and Automata Theory , Wiley, Nueva York, 1967. Cf. Capítulo 9, Máquinas de Turing. Libro difícil, destinado a ingenieros eléctricos y especialistas técnicos. Discute la recursividad, recursividad parcial con referencia a las Máquinas de Turing, problema de detención. Tiene un modelo de Turing Machine . Las referencias al final del Capítulo 9 recogen la mayoría de los libros más antiguos (es decir, 1952 hasta 1967, incluidos los autores Martin Davis, FC Hennie, H. Hermes, SC Kleene, M. Minsky, T. Rado) y varios artículos técnicos. Vea la nota en Programas Busy-Beaver.
• Los programas Busy Beaver se describen en Scientific American, agosto de 1984, también marzo de 1985 p. 23. Una referencia en Booth los atribuye a Rado, T. (1962), On non-computable functions, Bell Systems Tech. J. 41. Booth también define el problema del castor ocupado de Rado en los problemas 3, 4, 5, 6 del capítulo 9, p. 396.
• David Bolter , Turing's Man: Western Culture in the Computer Age , The University of North Carolina Press, Chapel Hill, 1984. Para el lector general. Puede estar fechado. Tiene otro modelo de Turing Machine (muy simple).
• Egon Börger. "Computabilidad, Complejidad, Lógica". Holanda Septentrional, 1989.
• Stephen Kleene , Introducción a las metamatemáticas , Holanda Septentrional, 1952. El capítulo XIII ("Funciones computables") incluye una discusión sobre la imposibilidad de resolver el problema de las paradas para las máquinas de Turing. En un alejamiento de la terminología de Turing de máquinas sin paradas libres de círculos, Kleene se refiere en cambio a máquinas que "se detienen", es decir, se detienen.
• Sven Köhler, Christian Schindelhauer, Martin Ziegler, Sobre la aproximación de problemas de detención del mundo real , páginas 454-466 (2005) ISBN  3540281932 Notas de la conferencia de Springer en Computer Science volumen 3623: La indecidibilidad del problema de detención significa que no todas las instancias pueden responderse correctamente ; pero tal vez "algunos", "muchos" o "la mayoría" puedan. Por un lado, la respuesta constante "sí" será correcta infinitamente a menudo y errónea también infinitamente a menudo. Para que la pregunta sea razonable, considere la densidad de instancias que se pueden resolver. Esto resulta depender significativamente del sistema de programación considerado.
• Limitaciones lógicas a la ética de las máquinas, con consecuencias para las armas autónomas letales - artículo discutido en: ¿El problema de la detención significa que no hay robots morales?
• Nicholas J. Daras y Themistocles M. Rassias , Análisis y matemáticas discretas modernas: con aplicaciones en criptografía, sistemas de información y modelado Springer, 2018. ISBN  978-3319743240 . El Capítulo 3 La Sección 1 contiene una descripción de calidad del problema que se detiene, una prueba por contradicción y una representación gráfica útil del problema que se detiene.

enlaces externos

• Scooping the loop snooper : una prueba poética de la indecidibilidad del problema de la detención
• Película animada : una animación que explica la prueba de la indecidibilidad del problema de la detención.
• Una prueba de 2 minutos del segundo teorema más importante del segundo milenio : una prueba en solo 13 líneas