problem halting explicacion explained computer-science halting-problem

computer science - halting - ¿Cuál es exactamente el problema de detención?



halting problem explicacion (22)

"Si solo agrega un bucle, tiene el programa de detención y, por lo tanto, no puede automatizar la tarea"

Suena como alguien que generaliza la aplicación del problema de detención. Hay muchos bucles particulares que puedes probar que terminan. Existe una investigación que puede realizar la verificación de terminación para amplias clases de programas. Por ejemplo, en Coq, usted está limitado a los programas que puede probar que terminan. Microsoft tiene un proyecto de investigación llamado Terminator que usa varias aproximaciones para probar que los programas terminarán.

Pero, recuerde, el problema de la detención no se trata solo de ejemplos de juguetes. Ninguno de los dos resuelve el ''problema de detención'' general, porque no funcionan para todos los programas.

El problema es que el problema de la detención indica que existen programas que no tiene forma de saber si terminarán sin ejecutarlos, lo que significa que es posible que nunca termine de decidir si se detienen.

Un ejemplo de un programa que puede o no detenerse (en Haskell):

collatz 1 = () collatz !n | odd n = collatz (3 * n + 1) | otherwise = collatz (n `div` 2)

O en algo más accesible:

while (n != 1) if (n & 1 == 1) n = 3 * n + 1; else n /= 2;

Dado cada entero> = 1, ¿se detendrá este programa? Bueno, ha funcionado hasta ahora, pero no hay un teorema que diga que se detendrá por cada entero. Tenemos una conjetura debida a Lothar Collatz que se remonta a 1937, pero no hay pruebas.

Cuando las personas preguntan sobre el problema de detención en lo que respecta a la programación, la gente responde con "Si solo agrega un ciclo, tiene el programa de detención y, por lo tanto, no puede automatizar la tarea "

Tiene sentido. Si su programa tiene un bucle infinito, entonces cuando su programa se está ejecutando, no tiene forma de saber si el programa todavía está generando una entrada, o si simplemente está realizando un bucle infinito.

Pero algo de esto parece contraintuitivo. ¿Qué pasa si estaba escribiendo un solucionador de problemas que se detiene, que toma el código fuente como entrada? rascher@localhost$ ./haltingSolver source.c

Si mi código (source.c) se ve así:

for (;;) { /* infinite loop */ }

Parece que sería bastante fácil para mi programa ver esto. "Mire el bucle y mire la condición. Si la condición se basa solo en literales y no en variables, entonces siempre sabrá el resultado del bucle. Si hay variables (por ejemplo, while (x <10)), vea si esas variables siempre se modifican. Si no, siempre se sabe el resultado del bucle ".

Por supuesto, estos controles no serían triviales (calcular aritmética de punteros, etc.) pero no parece imposible. p.ej:

int x = 0 while (x < 10) {}

podría ser detectado junto con - aunque no trivialmente:

int x = 0 while (x < 10) { x++; if (x == 10) { x = 0 } }

Ahora, ¿qué pasa con la entrada del usuario? Ese es el kicker, eso es lo que hace que un programa sea impredecible.

int x = 0; while (x < 10) { scanf("%d", &x); /* ignoring infinite scanf loop oddities */ }

Ahora mi programa puede decir: "Si el usuario ingresa un 10 o más, el programa se detendrá. En todas las demás entradas, se repetirá".

Lo que significa que, incluso con cientos de entradas, uno debería ser capaz de enumerar las condiciones en las que se detendrá el programa. De hecho, cuando escribo un programa, ¡siempre me aseguro de que alguien tenga la capacidad de terminarlo! No estoy diciendo que la lista resultante de condiciones sea trivial de crear, pero no me parece imposible. Puede recibir información del usuario, usarla para calcular índices de punteros, etc., pero eso se suma al número de condiciones para garantizar que el programa finalice, no hace que sea imposible enumerarlas.

Entonces, ¿qué es exactamente el problema de detención? ¿Qué es lo que no entiendo de la idea de que no podemos escribir un problema para detectar bucles infinitos? O, ¿por qué los "bucles" son un ejemplo tan citado?

ACTUALIZAR

Entonces, permítame cambiar un poco la pregunta: ¿cuál es el problema de la detención en lo que respecta a las computadoras? Y luego responderé a algunos de los comentarios:

Mucha gente ha dicho que el programa debe poder lidiar con "cualquier aporte arbitrario". Pero en las computadoras, nunca hay una entrada arbitraria. Si solo ingreso un solo byte de datos, entonces solo tengo 2 ^ 8 entradas posibles. Entonces, como ejemplo:

int c = getchar() switch (c) { case ''q'': /* quit the program */ }

De repente, he explicado todas las posibilidades. Si c tiene el patrón de bits 0x71, hace una cosa. Para todos los demás patrones, hace algo más. Incluso un programa que acepta la entrada de cadenas arbitrarias nunca es realmente "arbitrario", ya que los recursos son finitos, lo que significa que, si bien la teoría de "arbitrario" se aplica ... no es exactamente uno a uno con la práctica.

El otro ejemplo de personas citadas es este:

while (n != 1) if (n & 1 == 1) n = 3 * n + 1; else n /= 2;

Si n es un entero de 32 bits ... entonces puedo decirle visualmente si esto se detendrá o no.

Supongo que esta edición no está preguntando nada, pero el ejemplo más convincente que he visto es este :

Supongamos que tiene su programa / método mágico para determinar que un programa se detiene.

public bool DeterminesHalt(string filename, string[] args){ //runs whatever program you tell it do, passing any args //returns true if the program halts, false if it doesn''t }

Ahora digamos que escribimos un pequeño trozo de código como ...

public static void Main(string[] args){ string filename = Console.ReadLine(); //read in file to run from user if(DeterminesHalt(filename, args)) for(;;); else return; }

Entonces, para este ejemplo, podemos escribir un programa para hacer exactamente lo contrario de nuestro método mágico de detención. Si de alguna manera determinamos que un programa dado se detendrá, simplemente saltamos a un bucle infinito; de lo contrario, si determinamos que el programa está en un bucle infinito, terminamos el programa.

Entonces, de nuevo, si escribes intencionalmente un programa que contiene un bucle infinito ... "resolver el problema de detención" es un poco discutible, ¿no es así?

Aquí hay un programa que el problema de la detención nunca podrá resolver.

Supongamos que tiene su programa / método mágico para determinar que un programa se detiene.

public bool DeterminesHalt(string filename, string[] args){ //runs whatever program you tell it do, passing any args //returns true if the program halts, false if it doesn''t }

Ahora digamos que escribimos un pequeño trozo de código como ...

public static void Main(string[] args){ string filename = Console.ReadLine(); //read in file to run from user if(DeterminesHalt(filename, args)) for(;;); else return; }

Entonces, para este ejemplo, podemos escribir un programa para hacer exactamente lo contrario de nuestro método mágico de detención. Si de alguna manera determinamos que un programa dado se detendrá, simplemente saltamos a un bucle infinito; de lo contrario, si determinamos que el programa está en un bucle infinito, terminamos el programa.

No importa cuántas comprobaciones de entrada realice, no hay una solución posible para determinar si TODOS los programas escritos se detienen o no.

Aquí hay una explicación simple de la prueba de que el problema de la detención es indecidible.

Supongamos que tiene un programa, H, que calcula si un programa se detiene o no. H toma dos parámetros, el primero es una descripción de un programa, P, y el segundo es una entrada, I. H devuelve verdadero si P se detiene en la entrada I, y en caso contrario, es falso.

Ahora escriba un programa, p2, que tome como entrada la descripción de otro programa, p3. p2 llama a H (p3, p3), luego realiza un bucle si H devuelve true y, de lo contrario, se detiene.

¿Qué pasa cuando ejecutamos p2 (p2)?

Debe girar y detenerse al mismo tiempo, haciendo que el universo explote.

De Programming Pearls , de Jon Bentley.

4.6 problemas

5. Demuestre que este programa termina cuando su entrada x es un entero positivo.

while x != 1 do if even(x) x = x/2 else x = 3*x +1

EDITAR (mucho más tarde que la respuesta original): MarkCC de Good Math, Bad Math recientemente escribió una excelente discusión del problema de Halting con ejemplos concretos.

El problema de la detención es básicamente una forma formal de preguntarle si puede saber si un programa arbitrario terminará o no.

En otras palabras, ¿puede escribir un programa llamado oracle en espera, HaltingOracle (programa, entrada), que devuelve verdadero si el programa (entrada) se detendría finalmente, y cuál devuelve falso si no lo haría?

La respuesta es: no, no puedes.

Continuando con las preguntas sobre si la entrada al problema de Detener es relevante o una pista falsa: Sí, la entrada es importante. Además, parece haber cierta confusión en cuanto a que veo que se usa "infinito" donde "arbitrario" es más correcto.

Ejemplo práctico : imagine que está trabajando en una posición de control de calidad y debe escribir un programa de control de detención (también conocido como un oráculo) que confirmará eso para cualquier programa arbitrario escrito por el equipo de desarrollo (D) y cualquier entrada arbitraria proporcionada por el final -usuario (I), el programa D finalmente se detendrá cuando se le dé la entrada I.

Voz de Cue Manager : "Ho ho, esos usuarios tontos, asegurémonos de que no importa qué basura escriban, nuestras tareas de servidor nunca terminarán en un bucle sin fin. ¡Hágalo así, código mono!"

Esto parece una gran idea, ¿verdad? No quieres que tu servidor se cuelgue, ¿verdad?

Lo que el problema de detención le está diciendo es que se le está entregando una tarea sin solución. En su lugar, en este caso particular, debe planificar las tareas que se ejecutan más allá de un tiempo límite y estar listo para cancelarlas.

Mark usa código en lugar de entrada para ilustrar el problema:

def Deciever(i): oracle = i[0] in = i[1] if oracle(Deceiver, i): while True: continue else: return i

En mi discusión en los comentarios, tomé la ruta de la manipulación de entrada maliciosa para forzar un problema sin solución. El ejemplo de Mark es mucho más elegante, usando el oráculo que se detiene para derrotarse a sí mismo:

Entonces, la entrada a Deceiver es en realidad una lista de dos elementos: el primero es un oráculo propuesto para detener. La segunda es otra entrada. Lo que hace el asesino que se detiene es preguntarle al oráculo: "¿Crees que me detendré para la entrada i?". Si el oráculo dice "Sí, se detendrá", entonces el programa entra en un bucle infinito. Si el oráculo dice "No, no te detendrás", entonces se detiene. Así que no importa lo que diga el oráculo, está mal.

Dicho de otra manera, sin trampas, reformateo de entradas, infinitos contables / incontables o cualquier otra distracción, Mark ha escrito un fragmento de código que puede derrotar a cualquier programa oracle que se detiene. No puedes escribir un oracle que responda a la pregunta de si Deceiver alguna vez se detiene.

Respuesta original:

De la gran Wikipedia :

En la teoría de la computabilidad, el problema de la detención es un problema de decisión que puede establecerse de la siguiente manera: dada una descripción de un programa y una entrada finita, decide si el programa termina de ejecutarse o se ejecutará para siempre, dada esa entrada.

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. Decimos que el problema de la detención es indecidible en las máquinas de Turing. Copeland (2004) atribuye el problema de detención del término real a Martin Davis.

Uno de los puntos críticos es que no tiene control sobre el programa o la entrada. Se te entregan esos y depende de ti responder la pregunta.

Tenga en cuenta también que las máquinas de Turing son la base para modelos efectivos de computabilidad. Dicho de otra manera, todo lo que haga en los lenguajes informáticos modernos se puede asignar a estas máquinas de Turing arquetípicas. Como resultado, el problema de la detención es indecidible en cualquier lenguaje moderno útil.

El gran ejemplo de Turing fue autorreferencial. Supongamos que existe un programa que puede examinar otro y determinar si se detendrá o no. Alimente el verificador de programas de parada ESTO MISMO en el verificador de programas de detención: ¿qué debería hacer?

En referencia al punto secundario "la gente responde con" Si solo agrega un ciclo, tiene el programa de detención y, por lo tanto, no puede automatizar la tarea "", agregaré este detalle:

Las publicaciones que dicen que no puede calcular algorítmicamente si un programa arbitrario se detendrá son absolutamente correctas para una máquina de Turing.

La cosa es que no todos los programas requieren máquinas de Turing. Estos son programas que pueden computarse con una máquina conceptualmente "más débil", por ejemplo, las expresiones regulares pueden incorporarse completamente mediante una máquina de estados finitos, que siempre se detiene en la entrada. ¿No es eso agradable?

Apuesto a que cuando la gente dice "agregar un bucle", están tratando de expresar la idea de que, cuando un programa es lo suficientemente complejo, requiere una máquina de Turing y, por lo tanto, se aplica el problema de detención (como idea).

Esto puede ser un poco tangencial a la pregunta, pero creo que, dado el detalle en la pregunta, vale la pena señalarlo. :)

Esto ha sido golpeado hasta la muerte tan bien que en realidad hay una prueba poética , escrita en el estilo de Lewis Carroll Dr. Seuss por Geoffrey Pullum (él de la fama del registro de idiomas ).

Cosas graciosas. Aquí hay un gusto:

Aquí está el truco que usaré, y es simple de hacer.
Definiré un procedimiento, que llamaré Q,
Eso usará las predicciones de P para detener el éxito.
Para agitar un terrible desorden lógico.

...

No importa cómo se desempeñe P, Q lo recogerá:
Q usa la salida de P para hacer que P se vea estúpido.
Lo que P diga, no puede predecir Q:
P es correcto cuando está mal, y es falso cuando es verdad!

Hay una buena prueba de que el problema de detención está en wikipedia.

Para ilustrar, exactamente, por qué no basta con aplicar alguna técnica a los bucles, considere el siguiente programa (pseudocódigo):

int main() { //Unbounded length integer Number i = 3; while(true) { //example: GetUniquePositiveDivisiors(6) = [1, 2, 3], ...(5) = 1, ...(10) = 1, 2, 5, etc. Number[] divisiors = GetUniquePositiveDivisiors(i); Number sum = 0; foreach(Number divisor in divisiors) sum += divisor; if(sum == i) break; i+=2; } }

¿Puedes pensar en un enfoque que resulte verdadero si este código se detiene, y falso de lo contrario?

Pensar con cuidado

Si por casualidad estás en una seria disputa por una medalla Fields, imagina algún código para estos problemas en lugar de los anteriores.

La definición precisa del problema es que necesita escribir un programa que haga lo siguiente: - toma un programa arbitrario - determina si el programa se detiene debido a una entrada finita arbitraria en el programa

Sin embargo, esta es una barra muy alta. Hay muchas soluciones parciales al problema de la detención, pero no hay una solución general. Peor aún, se sabe que incluso encontrar programas que resuelvan parcialmente el problema de la detención es difícil:

BBC h2g2 artículo sobre el problema de la detención

Si realmente resolvió el problema de la detención, trabaje en sitios como rentacoder.com para usted. Hace unos meses hubo una publicación en uno de ellos de un usuario llamado ATuring que ofreció un contrato para resolver el problema de la detención. :)

Muchos ejemplos / analogías específicas interesantes hasta ahora. Si desea leer más a fondo, hay un buen libro en el artículo original de Turing, The Annotated Turing , de Charles Petzold.

En una vena relacionada, de lado a lado, hay un ensayo muy bueno en la web, ¿Quién puede nombrar el número más grande? Que cepilla en las máquinas de Turing y en las funciones de Ackermann.

Para resolver el problema de la detención, tendría que desarrollar un algoritmo que pudiera determinar si un programa arbitrario se detiene para una entrada arbitraria , no solo los casos relativamente simples en sus ejemplos.

Suponga que escribe un algoritmo que puede verificar cualquier pieza de código arbitrario y diga si se detiene.

Ahora dale tu propio algoritmo para comprobarlo.

Usted enumeró algunos de los casos simples.

Ahora, piensa en pensar en el resto de los casos.

Hay un número infinito de posibles escenarios, tendrías que enumerarlos todos.

A menos que por supuesto puedas generalizarlo.

Ahí es donde entra el problema de detención. ¿Cómo lo generalizas?

Ya hay muchas respuestas buenas, pero no he visto a nadie abordar el hecho de que, en una especie de combinación selectiva de teoría y practicidad, el Problema de Detención realmente puede resolverse.

En primer lugar, el problema de la detención es básicamente la tarea de escribir un programa que tome cualquier segundo programa arbitrario y determine si el programa secundario se detendrá en una entrada arbitraria. Así que dices "Sí, este programa se detendrá en esta entrada" o "No, no lo hará". Y, de hecho, es imposible de resolver en el caso general (otras personas parecen haber proporcionado pruebas de esto ya) en una máquina de Turing. El problema real es que puedes averiguar si algo se va a detener ejecutándolo (solo espera hasta que se detenga), pero realmente no puedes averiguar si algo no se detendrá al ejecutarlo solo sigue esperando por siempre).

Este es un problema en una máquina de Turing que, por definición, tiene una cantidad infinita de memoria y por lo tanto infinitos estados. Sin embargo, nuestras computadoras solo tienen una cantidad finita de memoria. Sólo hay tantos bits en la computadora. Entonces, si de alguna manera pudiera hacer un seguimiento de todos los estados anteriores (configuraciones de bits) que ha visto mientras ejecuta el programa, puede garantizar que su verificador nunca entrará en un bucle infinito. Si el programa secundario finalmente se detiene, dices "Sí, este programa se detendrá en esta entrada". Si ve la misma configuración de bit dos veces antes de que se detenga, sabrá "No, no lo hará". Probablemente no sea de gran importancia técnica, pero es bueno saber que muchas veces los problemas realmente "difíciles" que enfrentamos son más difíciles en teoría que en la práctica.

Una prueba desde otra perspectiva.

Supongamos que tenemos una CPU con instrucciones como mov, add, jmp, pero sin entrada ni salida. Y tenemos memoria. No como otros CPUs, este tiene otro registro, llamado paraReg . Este registro es como un archivo, podemos mover contenido ilimitado en él, obtener el tamaño del mismo, buscarlo en la mitad, eliminar parte del contenido, que se realiza a través de algunas instrucciones adicionales.

Antes de empezar, definamos algunas palabras. Un programa es un conjunto de instrucciones, que es una cadena. Antes de ejecutar un programa, borramos todos los registros y la memoria a cero, excepto paraReg, que contiene el parámetro (una cadena), y luego colocamos el programa en la ubicación de memoria cero y configuramos el registro ip a cero. Un proceso es cuando un programa se está ejecutando.

Ahora el problema de la detención se puede plantear así: dado cualquier programa, llamado proObj (si toma un parámetro para0, agregamos una instrucción en la primera línea: mov paraReg, para0), ¿hay un programa que tome proObj como el parámetro y puede decidir si proObj se detendrá cuando proObj comience a ejecutarse en paraReg establecido en cero?

Supongamos que tenemos un programa llamado p1. Luego podemos crear otro programa, llamado p2 que toma un parámetro para0. A través de p1, podemos saber si un programa cuyo contenido es para0, cuyo parámetro es para0, se detendrá o no. (Lo hacemos de esta manera. Construya un programa cuya primera línea sea [mov paraReg, para0], el resto es para0. Nombra este programa pro0. Luego configuramos paraReg en pro0 y llamamos p1.) Si se detiene, dejamos que p2 entre en un bucle infinito, de lo contrario dejamos que p2 se detenga.

Si ponemos p2 en paraReg y ejecutamos p2, ¿se detendrá el proceso o no? Si se detiene, de la definición de p2, sabemos que cuando colocamos p2 en paraReg y ejecutamos p2, no debería detenerse; del mismo modo, si no se detiene, sabemos que cuando se coloca p2 en paraReg y se ejecuta p2, se debe detener. Entonces podemos decir que no hay p2, y no hay p1.

Puede resultarle útil considerar la historia del tipo que corta el césped de cualquiera que no corte su propio césped y preguntarse si corta o no su propio césped.

La importancia del problema de detención no radica en la importancia del problema en sí; por el contrario, las pruebas automatizadas serían de poco uso práctico en la ingeniería de software (probar que un programa se detiene no prueba que sea correcto y, en cualquier caso, el algoritmo hipotético solo proporciona una prueba para una entrada finita dada, mientras que una vida real El desarrollador de software estaría más interesado en una prueba para todas las posibles entradas finitas).

Más bien, el problema de la detención fue uno de los primeros en probarse como indecidible , lo que significa que no existe ningún algoritmo que funcione en el caso general. En otras palabras, Turing demostró hace más de 70 años que hay algunos problemas que las computadoras no pueden resolver, no solo porque todavía no se ha encontrado el algoritmo correcto, sino porque tal algoritmo no puede existir lógicamente.

Otro ejemplo más. Recientemente me encontré con algo llamado números de granizo. Estos números forman una secuencia con estas reglas.

f(n) is odd - f(n+1) = 3*f(n)+1 f(n) is even - f(n+1) = f(n)/2

Actualmente, se asume que todos los puntos de partida eventualmente llegarán a 1 y luego se repetirán. 4,2,1,4,2,1,4,2,1...Sin embargo, no hay pruebas de esto. Entonces, ahora mismo, la única forma de determinar si un número termina cuando se ingresa en la secuencia de granizo es en realidad calcularlo hasta que llegue a 1.

Esta es la clave de cómo yo entiendo el problema de la parada. Lo que entiendo es que no puede estar seguro de que un programa no se detendrá a menos que realmente lo ejecute . Por lo tanto, cualquier programa que escriba que pueda darle una respuesta segura al problema de la detención, tendría que ejecutar el programa.