Sempre que as pessoas perguntam sobre o problema de parada no que se refere à programação, as pessoas respondem com "Se você acabou de adicionar um loop, você tem o programa de interrupção e, portanto, não pode automatizartarefa"

Faz sentido. Se o seu programa tem um loop infinito, então quando o seu programa está rodando, você não tem como saber se o programa ainda está processando a entrada, ou se está rodando infinitamente.

Mas algo disso parece contra-intuitivo. E se eu estivesse escrevendo um solucionador de problemas de interrupção, que usa o código-fonte como entrada.rascher@localhost$ ./haltingSolver source.c

Se meu código (source.c) for assim:

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

Parece que seria muito fácil para o meu programa ver isso. "Olhe o loop, e olhe para a condição. Se a condição é baseada apenas em literais, e sem variáveis, então você sempre sabe o resultado do loop. Se houver variáveis ​​(por exemplo, while (x <10)), veja se essas variáveis ​​são sempre modificadas. Se não, então você sempre sabe o resultado do loop. "

Concedido, essas verificações não seria trivial (cálculo de aritmética de ponteiro, etc), mas não parece impossível. por exemplo:

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

poderia ser detectado. juntamente com - embora não trivialmente:

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

Agora, e a entrada do usuário? Esse é o kicker, é isso que torna um programa imprevisível.

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

Agora meu programa pode dizer: "Se o usuário inserir um 10 ou mais, o programa será interrompido. Em todas as outras entradas, ele será repetido novamente".

O que significa que, mesmo com centenas de entradas, umadeveria ser capaz de listar as condições em que o programa irá parar. De fato, quando escrevo um programa, sempre me certifico de que alguém tenha a capacidade de terminá-lo! Eu não estou dizendo que a lista resultante de condições étrivial criar, mas não parece impossível para mim. Você poderia pegar a entrada do usuário, usá-la para calcular índices de ponteiro, etc - mas isso só aumenta o número de condições para garantir que o programa terminará, não torna impossível enumerá-las.

Então, qual é exatamente o problema da parada? O que não estou entendendo sobre a ideia de que não podemos escrever um problema para detectar loops infinitos? Ou, por que os "loops" são exemplos tão citados?

ATUALIZAR

Então, deixe-me mudar um pouco a questão: qual é o problema da paradacomo se aplica aos computadores? E então responderei a alguns dos comentários:

Muitas pessoas disseram que o programa deve ser capaz de lidar com "qualquer contribuição arbitrária". Mas nos computadores, nunca há entrada arbitrária. Se eu inserir apenas um único byte de dados, só tenho 2 ^ 8 entradas possíveis. Então, como exemplo:

int c = getchar()

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

De repente, acabei de explicar todas as possibilidades. E sec tem o padrão de bits 0x71, faz uma coisa. Para todos os outros padrões, faz outra coisa. Mesmo um programa que aceita entrada arbitrária de strings nunca é realmente "arbitrário", já que os recursos são finitos, o que significa que enquanto a teoria de "arbitrária" se aplica ... não é exatamente um-para-um com a prática.

O outro exemplo que as pessoas citaram é este:

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

Se n é um inteiro de 32 bits ... então eu posso dizer visualmente se isso irá ou não parar.

Eu acho que esta edição não está pedindo nada, mas o exemplo mais convincente que eu vi éeste:

Suponha que você tenha seu programa / método mágico para determinar que um programa é interrompido.

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
}

Agora vamos dizer que escrevemos um pequeno pedaço 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;
}

Então, para este exemplo, podemos escrever um programa para fazer exatamente o oposto do nosso método de parada mágica. Se de alguma forma determinarmos que um dado programa irá parar, nós apenas pulamos em um loop infinito; caso contrário, se determinarmos que o programa está em um loop infinito, terminamos o programa.

Então, novamente, se você intencionalmente escrever um programa que contenha um loop infinito ... "resolver o problema da parada" é meio discutível, não é?