Problème de l'arrêt
Un article de Wikipédia, l'encyclopédie libre.
Le problème de l'arrêt est le problème de décider si un programme informatique (ou une machine de Turing) finit par s'arrêter ou non.
L'impossibilité de la décision du problème de l'arrêt est un résultat central de la théorie de la calculabilité. On a ainsi démontré qu'il était impossible pour un programme informatique de décider automatiquement et dans tous les cas, à la lecture d'autres programmes informatiques, si ceux-ci terminent. Cela signifie concrètement qu'il n'existera jamais de compilateur capable de vous dire que le programme que vous avez écrit est mal conçu et qu'il bouclera indéfiniment. Ce résultat est généralisé par le théorème de Rice à de nombreuses autres propriétés concernant l'analyse des programmes.
[modifier] Preuve
La preuve de ce résultat repose, comme celle du théorème d'incomplétude de Gödel, sur un argument diagonal.
On considère qu'un programme est une fonction prog qui transforme une chaîne de bits ch, appelée l'entrée, en une autre chaîne de bits prog(ch), appelée la sortie. De plus, on peut associer à tout programme prog, une chaîne ch_prog qui représente le codage de prog. On notera ch1,ch2 la chaîne obtenue en concaténant les deux chaînes ch1 et ch2.
Supposons par l'absurde qu'il existe une programe halt tel que halt(ch_prog,ch)=1 si prog(ch) s'arrête, et autrement (si prog(ch) boucle indéfiniment), halt(ch_prog,ch)=0.
On peut alors construire le programme trouble suivant:
trouble(ch)
1. faire halt(ch,ch)
2. si halt(ch,ch)=1, alors faire{...} tant que(vrai)
Mais, on obtient une contradiction. En effet, si l'on suppose que trouble(ch_trouble) s'arrête, alors par définition de halt c'est que halt(ch_trouble,ch_trouble)=1, et donc, par définition de trouble, on a que trouble(ch_trouble) boucle; contradiction. Il nous faut donc admettre que trouble(ch_trouble) boucle; mais alors par définition de halt, c'est que halt(ch_trouble,ch_trouble)=0, et par définition de trouble, trouble(ch_trouble) s'arrête. Contradiction.
[modifier] Applications
De très nombreux problèmes en informatique, notamment concernant l'analyse statique de programmes, sont équivalents au problème de l'arrêt. On le montre là encore en réduisant la résolution du problème de l'arrêt à celle du problème étudié.
Citons par exemple le problème du ramasse-miettes : on cherche à libérer des zones mémoires juste après leur dernière utilisation. Ce problème est équivalent à celui de l'arrêt. La réduction est simple : soit P un programme dont on veut tester l'arrêt ; considérons le programme :
- créer une zone mémoire X (jamais utilisée dans P)
- exécuter P
- écrire dans X.
Clairement, la zone mémoire X sert après sa création si et seulement si P termine. Donc, si on savait déterminer automatiquement au vu de la lecture du programme si on peut libérer X juste après son allocation, on saurait si P termine. Cela est impossible, donc il n'existe aucun algorithme de ramasse-miette optimalement précis.
