Detener el problema

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 22 de noviembre de 2021; las comprobaciones requieren 4 ediciones .

El problema de la detención es uno de los problemas de la teoría de algoritmos [1] , que puede expresarse informalmente como:

Se da la descripción del procedimiento y sus datos iniciales de entrada. Se requiere determinar: ¿finalizará alguna vez la ejecución del procedimiento con estos datos? o que el procedimiento se ejecutará todo el tiempo sin detenerse.

Alan Turing demostró en 1936 que el problema de la detención es indecidible en una máquina de Turing . En otras palabras, no existe un algoritmo general para resolver este problema. [2]

El problema de la detención es fundamental para la teoría de la computabilidad porque es el primer ejemplo de un problema que no puede resolverse algorítmicamente.

En términos de funciones, el problema se puede describir fácilmente de la siguiente manera:

Para cualquier función F(G, start_state) que pueda determinar si otra función se detiene, siempre puede escribir una función G(start_state) que, cuando se pasa a F, tendrá el resultado de ejecución opuesto al que predice F.

Para muchas otras tareas[ ¿Qué? ] uno puede probar su indecidibilidad algorítmica tratando de reducirlos al problema de la detención. Esto se hace de acuerdo con el esquema "por el contrario": que haya un cierto problema para el cual se requiere establecer su irresolubilidad. Luego asumimos que es solucionable e intentamos, usando este hecho, escribir un algoritmo para resolver el problema de detención para este problema. Si esto tiene éxito, entonces llegaremos a una contradicción, porque se sabe que no existe un algoritmo para resolver el problema de la detención. Esto significa que la suposición era incorrecta y que el problema original tampoco tiene solución.

Prueba

Considere un conjunto de algoritmos que toman un número natural como entrada y también dan un número natural como salida. Elijamos algún lenguaje de programación completo de Turing. Cada algoritmo se puede escribir como una secuencia finita de caracteres en este lenguaje. Ordenemos el conjunto (esto es posible, ya que es un conjunto de secuencias finitas de elementos de un conjunto finito y por lo tanto contable ), y cada algoritmo recibirá su propio número de serie. Llamemos al Analizador un algoritmo hipotético que recibe un par de números naturales como entrada y: $S$ $S$ $(N,X)$

se detiene y devuelve 1 si el algoritmo con el número no se detiene después de recibir $norte$ $X$
no se detiene de lo contrario (si el algoritmo con el número se detiene después de recibir ). $norte$ $X$

El problema de la detención se puede reformular de la siguiente manera: ¿Existe un analizador?

Teorema. El analizador no existe.

Demostrémoslo por contradicción. Digamos que el Analizador existe. Escribamos el algoritmo Diagonalizer, que toma un número como entrada , pasa un par de argumentos al Analyzer y devuelve el resultado de su trabajo. En otras palabras, el Diagonalizer se detiene si y solo si el algoritmo con el número no se detiene después de recibir el número como entrada . Sea el número ordinal del Diagonalizador en el conjunto . Ejecute el Diagonalizer pasándole este número . El diagonalizador se detendrá si y solo si el algoritmo con el número (es decir, él mismo) no se detiene cuando recibe un número como entrada (que le pasamos). De esta contradicción se deduce que nuestra suposición es incorrecta: el Analizador no existe, lo cual debía probarse. $norte$ $(n,n)$ $norte$ $norte$ $k$ $S$ $k$ $k$ $k$

Véase también

El gráfico de flujo de control se puede utilizar para categorizar rápidamente cuando el programa no tiene bucles (y, por lo tanto, se detiene), tiene bucles triviales (y, por lo tanto, se detiene), tiene bucles no triviales (indecidible) o entra en un bucle infinito.

Notas

↑ N.K. Vereshchagin, A. Shen Conferencias sobre lógica matemática y teoría de algoritmos. Parte 3. Funciones computables Archivado el 12 de noviembre de 2015 en Wayback Machine .
↑ Turing A. On Computable Numbers, with a Application to the Entscheidungsproblem // Proceedings of the London Mathematical Society - London Mathematical Society , 1937. - vol. s2-42, edición. 1.- Pág. 230-265. — ISSN 0024-6115 ; 1460-244X - doi:10.1112/PLMS/S2-42.1.230 (en esta publicación, Turing presenta la definición de una máquina de Turing , formula el problema de bloqueo y muestra que, al igual que el problema de resolución , no tiene solución).

Enlaces

c2: problema de detención
Problema de congelación