Le piège du « il suffit d'exécuter »

Si p s'arrête, on le constate au bout d'un temps fini (réponse oui). Mais si p boucle, l'observation ne se termine jamais : on ne pourra jamais répondre non avec certitude — peut-être s'arrêtera-t-il à l'étape suivante ? On obtient un semi-décideur (correct sur les oui), pas un décideur. C'est précisément cette asymétrie qui rend l'arrêt non décidable.