Problème de l'arrêt
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

En théorie de la calculabilité, le problème de l'arrêt consiste, étant donné un programme informatique quelconque (au sens machine de Turing), à dire s'il finira par s'arrêter ou non.

Ce problème n'est pas décidable, c'est-à-dire qu'il n'existe pas de programme informatique (Un programme informatique est une liste d'ordres indiquant à un ordinateur ce qu'il doit faire. Il se présente sous la forme d'une ou plusieurs séquences d'instructions, comportant souvent des données de base, devant être exécutées dans...) qui prendrait comme entrée un autre programme informatique (L´informatique - contraction d´information et automatique - est le domaine d'activité scientifique, technique et industriel en rapport avec le traitement automatique de...) quelconque et qui ressortirait VRAI si le programme s'arrête et FAUX sinon. Plus concrètement, on ne peut élaborer un compilateur capable de vous dire à tous les coups si le programme que vous avez écrit bouclera indéfiniment ou non. Ce résultat est généralisé par le théorème de Rice (En théorie de la calculabilité, le théorème de Rice dit que toute propriété non triviale (c.-à-d. qui n'est pas toujours vraie ou toujours fausse) sur la sémantique dénotationnelle d'un langage de programmation...) à de nombreuses autres propriétés concernant l'analyse des programmes.

Preuve

La preuve de ce résultat repose sur un argument diagonal (Dans les preuves mathématiques, notamment celles de logique mathématique, l'argument diagonal est un mécanisme de construction réflexive menant le plus souvent à une impossibilité. Une telle construction est donc...), tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) comme la preuve d'indénombrabilité des réels Cantor (1891) et celle du théorème (Un théorème est une proposition qui peut être mathématiquement démontrée, c'est-à-dire une assertion qui peut être établie comme vraie au travers d'un raisonnement logique construit à partir...) d'incomplétude (On parle de complétude en mathématiques dans des sens très différents. On dit d'un objet mathématiques qu'il est complet pour exprimer que rien ne peut lui être ajouté, en un sens qu'il...) de Gödel (1931).

Dans le cas général tout programme est une fonction PROG() qui transforme une chaîne (Le mot chaîne peut avoir plusieurs significations :) de bits ch (appelée l'entrée) en une autre chaîne de bits PROG(ch) (appelée la sortie, éventuellement la sortie peut ne pas dépendre de l'entrée). Bien sûr, tout programme PROG() est en fait une chaîne de bits prog (qui représente le codage (De façon générale un codage permet de passer d'une représentation des données vers une autre.) de PROG). Dans la suite on notera ch1ch2 la chaîne obtenue en concaténant les deux chaînes ch1 et ch2.

Supposons par l'absurde qu'il existe un programme HALT() tel que HALT(progch)=1 si PROG(ch) s'arrête, et HALT(progch)=0 si au contraire PROG(ch) boucle infiniment. On pourrait alors construire le programme TROUBLE() suivant:

TROUBLE(ch)

1. faire HALT(chch)

2. si HALT(chch)=1, alors faire{...} tant que(vrai)

Mais, on obtient une contradiction (Une contradiction existe lorsque deux affirmations, idées, ou actions s'excluent mutuellement.) pour l'entrée trouble. En effet, supposons que TROUBLE(trouble) s'arrête, alors par définition (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la division entre les définitions réelles et les définitions nominales.) de HALT(), on a HALT(troubletrouble)=1. Par définition de TROUBLE(), on a alors que TROUBLE(trouble) boucle infiniment. Admettons alors que TROUBLE(trouble) boucle infiniment. Dans ce cas par définition de HALT(), on a HALT(troubletrouble)=0 et donc par définition de TROUBLE(), on a TROUBLE(trouble) qui s'arrête. Cette contradiction prouve donc que HALT() n'existe pas.

Applications

De très nombreux problèmes en informatique, notamment concernant l'analyse statique (Le mot statique peut désigner ou qualifier ce qui est relatif à l'absence de mouvement. Il peut être employé comme :) 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 (D'une manière générale, la mémoire est le stockage de l'information. C'est aussi le souvenir d'une information.) 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.

Page générée en 0.108 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique