Terminaison d'un algorithme

La terminaison est une propriété fondamentale des algorithmes. Elle stipule que les calculs décrits par l'algorithme s'arrêteront. En général cet arrêt doit avoir lieu quelles que soient les données initiales que l'on fournit à l'algorithme, si l'on veut insister sur ce point on parle alors souvent de terminaison uniforme, mais le plus généralement « terminaison » couvre aussi bien l'arrêt sur une donnée que l'arrêt sur toutes les données et c'est le contexte qui décide. La terminaison forme avec la correction partielle un des aspects de la correction des programmes, la correction partielle et la terminaison forment ce que l'on appelle la correction totale.

Dans la cas spécifique des machine de Turing, la terminaison s'appelle l'arrêt (halting en anglais dans le vocabulaire de Turing). Un cas particulier d'étude de la terminaison est la terminaison d'un système de réécriture.

Notion de terminaison

Étant donné un algorithme et des valeurs, la question de sa terminaison est de savoir si il va s'arrêter s'il prend en entrée ces valeurs. Par exemple l'algorithme de pseudo-code

tant que i est supérieur à 0 remplacer i par i+1,

ne s’arrêtera pas sur aucune entrée positive.

Preuve de terminaison

L'une des méthodes classiques pour prouver la terminaison d'un algorithme, est de définir une fonction, parfois appelée fonction de terminaison, qui satisfait les conditions suivantes. Elle a pour variables, les variables du programme, elle décroît pendant l'exécution et elle est à valeur dans un ensemble bien ordonné, typiquement l'ensemble des entiers. Par exemple, on choisira une fonction qui, pour un algorithme itératif décroît à chaque boucle, et pour un programment récursif décroît à chaque appel.

Problème de l'arrêt

Le problème de l'arrêt consiste, étant donné un algorithme, à décider si il termine ou pas. Ce problème est indécidable, au sens algorithmique du terme.

Un concept dual: la vivacité

Dans le cas des processus non déterministes, la vivacité est un concept dual de la terminaison. En effet, au lieu de garantir que tous les calculs s'arrêteront, la vivacité garantit qu'aucun des calculs ne s'arrêtera.

Voir aussi

• Complexité en temps, une autre caractéristique importante pour les programme qui terminent : le temps de calcul en fonction de la taille de l'entrée