« Il suffit de l'exécuter »

Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 31 — Décidabilité et classes de complexité

Énoncé

Un élève propose : « pour savoir si $p$ s'arrête sur $x$ , il suffit de l'exécuter. S'il s'arrête, on répond oui ; s'il tourne encore au bout d'une heure, on répond non. » Que vaut cet algorithme ? Que décide-t-il exactement ?

Corrigé

Il ne décide rien, mais il fait quelque chose, et c'est ce quelque chose qu'il faut nommer.

Ce qu'il fait de correct. Si $p$ s'arrête sur $x$ , l'exécution le révèle — au bout d'un temps fini. La procédure « exécuter et attendre » répond donc oui sur toutes les instances positives. On dit que arrêt est semi-décidable : il existe un procédé qui reconnaît les « oui », et qui sur les « non » ne s'arrête jamais.

Ce qu'il fait de faux. Le seuil d'une heure. Répondre « non » parce qu'on n'a pas fini est un pari, et rien ne le justifie.

Une mesure qui rend la chose concrète. Prenons le programme de Syracuse : tant que n <> 1 faire n <– si n impair alors 3n+1 sinon n/2. Il termine sur tous les entiers essayés, mais on ignore s'il termine sur tous. Voici le plus long temps d'arrêt observé, par tranche :

Entrées essayées	Arrêt le plus long	Atteint en
$n < 1 0^{3}$	$178$ étapes	$n = 871$
$n < 1 0^{4}$	$261$ étapes	$n = 6171$
$n < 1 0^{5}$	$350$ étapes	$n = 77031$
$n < 1 0^{6}$	$524$ étapes	$n = 837799$
$n < 1 0^{7}$	$685$ étapes	$n = 8400511$

Aucun seuil ne tient : pour chaque budget fixé, une entrée le dépasse. Avec un budget de $160$ étapes, $n = 703$ le dépasse ; avec $320$ , c'est $n = 35655$ . Et $n = 27$ , qui a l'air minuscule, demande $111$ étapes en montant jusqu'à $9232$ — soit $342$ fois sa propre valeur.

La distinction à retenir.

Décidable	un programme répond oui ou non, et s'arrête toujours
Semi-décidable	un programme répond oui quand c'est oui, et boucle sinon

arrêt est semi-décidable et non décidable. Son complémentaire — « $p$ ne s'arrête pas sur $x$ » — n'est même pas semi-décidable : si les deux l'étaient, on obtiendrait un décideur en lançant les deux procédures en parallèle et en gardant celle qui répond.

Et voilà pourquoi les outils réels répondent « je ne sais pas » : c'est la seule troisième réponse qui permette à un programme de toujours s'arrêter.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.