Preuve de terminaison de boucles

: recueil de méthodes et application par l'exemple

Résumé

Actuellement, il existe une multitude de méthodes qui permettent de prouver la terminaison de boucles. Ce mémoire rassemble, explique et compare, souvent par l’exemple les principales de ces méthodes jugées les plus pertinentes. Notons que ces méthodes peuvent dans certains cas prouver qu’une boucle se terminera. Par contre, aucune d’entre elles n’est capable de prouver la terminaison de toutes les boucles. En effet, nous savons par Turing que la terminaison est un problème indécidable. La plupart des méthodes présentées dans ce mémoire se basent sur la démonstration de Turing prouvant que si une fonction de rang existe, alors la boucle correspondante se terminera. Chacune des méthodes actuelles représente une amélioration d’une méthode précédente. Il n’existe pas encore de méthode universelle.

la date de réponse	17 juin 2015
langue originale	Français
L'institution diplômante	Universite de Namur
Superviseur	Wim Vanhoof (Promoteur)