Décidabilité, indécidabilité algorithmique d'un problème et programmes informatiques


Définition : Décidabilité, indécidabilité algorithmique d'un problème
Un problème est dit décidable s'il existe un algorithme, une procédure qui termine en un nombre fini d'étapes, qui le décide, c'est-à-dire qui réponde par oui ou par non à la question posée par le problème.
S'il n'existe pas de tels algorithmes, le problème est dit indécidable.

Exemple de problème indécidable : L'indécidabilité du problème de l'arrêt
L'indécidabilité du problème de l'arrêt a été démontrée par Alan Turing en 1936 :
« Il n'existe pas d'algorithme qui permette de décider si, étant donnée une machine de Turing quelconque et son état initial, le calcul de celle-ci s'arrête ou non ».

Du fait de la thèse de Church (du mathématicien Alonzo Church), ce résultat est très général. Depuis l'apparition de l'informatique, on peut l'interpréter ainsi :
« Il n'existe pas de programme permettant de tester n'importe quel programme informatique écrit dans un langage suffisamment puissant, tel que tous ceux qui sont utilisés aujourd'hui en pratique, afin de conclure dans tous les cas s'il s'arrêtera en un temps fini ou bouclera à jamais ! »

Aucun commentaire:

Enregistrer un commentaire

Remarque : Seul un membre de ce blog est autorisé à enregistrer un commentaire.