Scooping the Loop Snooper — Geoffrey K. Pullum

O problema da parada de um programa é indecidível. Existem programas que não se pode decidir se eles param ou não.

Seja um programa P que se queira saber se ele para ou se entra em "loop". Utiliza-se um programa Q para avaliar se P para. P pode ser feito para avaliar Q de modo que se Q concluir que P para, então P retorna para a primeira linha e recomeça tudo outra vez, infinitamente; e se Q conclui que P entrou em "loop", então P para imediatamente.

Scooping the Loop Snooper — Geoffrey K. Pullum