Cuando las personas preguntan sobre el problema de la 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 automatizartarea"

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 observe la condición. Si la condición se basa únicamente 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, unaDebería ser capaz de enumerar las condiciones en 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 de condiciones resultante seatrivial 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 terminará, no hace que sea imposible enumerarlas.

Entonces, ¿cuál 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ítanme cambiar un poco la pregunta: ¿cuál es el problema que se detiene?¿Como se aplica a las computadoras? Y luego responderé a algunos de los comentarios:

Muchas personas han dicho que el programa debe ser capaz de 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, acabo de explicar todas las posibilidades. Sic 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 pregunta nada, pero el ejemplo más convincente que he visto eséste:

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, nuevamente, si escribes intencionalmente un programa que contiene un bucle infinito ... "resolver el problema de detención" es un poco discutible, ¿no es así?