البـــــوابـــة
.2 Indécidabilité de la terminaisonLes logiciens Gödel et Turing ont démontré dans les années 30 qu'il était impossible d'espérer trouver un programme sachant tester si une fonction récursive termine son calcul. L'arrêt d'un calcul est en effet indécidable. Dans cette section, nous montrons qu'il n'existe pas de fonction qui permette de tester si une fonction Java termine. Nous présentons cette preuve sous la forme d'une petite histoire:
Le responsable des travaux pratiques d'Informatique en a assez des programmes qui calculent indéfiniment écrits par des élèves peu expérimentés. Cela l'oblige à chaque fois à des manipulations compliquées pour stopper ces programmes. Il voit alors dans un journal spécialisé une publicité:
<BLOCKQUOTE>Ne laissez plus boucler vos programmes! Utilisez notre fonction termine(o). Elle prend comme paramètre le nom d'un objet et répond true si la procédure f de cet objet ne boucle pas indéfiniment et false sinon. En n'utilisant que les procédures pour lesquelles termine répond true, vous évitez tous les problèmes de non terminaison. D'ailleurs, voici quelques exemples: </BLOCKQUOTE>class Turing {
static boolean termine (Object o) {
// détermine la terminaison de o.f()
boolean resultat;
// contenu breveté par le vendeur
return resultat;
}
}
class Facile {
void f () {
}
}
class Boucle {
void f () {
for (int i = 1; i > 0; ++i)
;
}
}
class Test {
public static void main (String args[]) {
Facile o1 = new Facile();
System.out.println (Turing.termine(o1));
Boucle o2 = new Boucle();
System.out.println (Turing.termine(o2));
}
}
<BLOCKQUOTE>pour lesquels termine(o) répond true puis false. </BLOCKQUOTE>Impressionné par la publicité, le responsable des travaux pratiques achète à prix d'or cette petite merveille et pense que sa vie d'enseignant va être enfin tranquille. Un élève lui fait toutefois remarquer qu'il ne comprend pas l'acquisition faite par le Maître avec la classe suivante:
class Absurde {
void f () {
while (Turing.termine(this))
;
}
class Test {
public static void main (String args[]) {
Absurde o3 = new Absurde();
System.out.println (Turing.termine(o3));
}
}
Si la procédure o3.f boucle indéfiniment, alors termine(o3) = false. Donc la boucle while de o3.f s'arrête et o3.f termine. Sinon, si la procédure o3.f ne boucle pas indéfiniment, alors termine(o3) = true. La boucle while précédente boucle indéfiniment, et la procédure o3.f boucle indéfiniment. Il y a donc une contradiction sur les valeurs possibles de termine(o3). Cette expression ne peut être définie. Ayant noté le mauvais esprit de l'Elève, le Maître conclut qu'on ne peut décidément pas faire confiance à la presse spécialisée!
L'histoire est presque vraie. Le Maître s'appelait David Hilbert et voulait montrer la validité de sa thèse par des moyens automatiques. L'Elève impertinent était Kurt Gödel. Le tout se passait vers 1930. Grâce à Gödel, on s'est rendu compte que toutes les fonctions mathématiques ne sont pas calculables par programme. Par exemple, il y a beaucoup plus de fonctions de N (entiers naturels) dans N que de programmes qui sont en quantité dénombrable. Gödel, Turing, Church et Kleene sont parmi les fondateurs de la théorie de la calculabilité.
Pour être plus précis, on peut remarquer que nous demandons beaucoup à notre fonction termine, puisqu'elle prend en argument un objet (en fait une ``adresse mémoire''), désassemble peut-être la procédure correspondante, et décide de sa terminaison. Sinon, elle ne peut que lancer l'exécution de son argument et ne peut donc tester sa terminaison (quand il ne termine pas). Un résultat plus fort peut être montré: il n'existe pas de fonction prenant en argument le source de toute procédure (en tant que chaîne de caractères) et décidant de sa terminaison. C'est ce résultat qui est couramment appelé l'indécidabilité de l'arrêt. Mais montrer la contradiction en Java est alors beaucoup plus dur.
2.3 Procédures récursives
<BLOCKQUOTE>
1- on amène les n-1 rondelles du haut de i sur le troisième piquet k = 6 - i - j,
2- on prend la grande rondelle en bas de i et on la met toute seule en j,
3- on amène les n-1 rondelles de k en j.
Ceci s'écrit
static void hanoi(int n, int i, int j) {
if (n > 0) {
hanoi (n-1, i, 6-(i+j));
System.out.println (i + " -> " + j);
hanoi (n-1, 6-(i+j), j);
}
}
Ces quelques lignes de programme montrent bien comment en généralisant le problème, c'est-à-dire aller de tout piquet i à tout autre j, un programme récursif de quelques lignes peut résoudre un problème a priori compliqué. C'est la force de la récursion et du raisonnement par récurrence. Il y a bien d'autres exemples de programmation récursive, et la puissance de cette méthode de programmation a été étudiée dans la théorie dite de la récursivité qui s'est développée bien avant l'apparition de l'informatique (Kleene [25], Rogers [45]). Le mot récursivité n'a qu'un lointain rapport avec celui qui est employé ici, car il s'agissait d'établir une théorie abstraite de la calculabilité, c'est à dire de définir mathématiquement les objets qu'on sait calculer, et surtout ceux qu'on ne sait pas calculer. Mais l'idée initiale de la récursivité est certainement à attribuer à Kleene (1935).
Le responsable des travaux pratiques d'Informatique en a assez des programmes qui calculent indéfiniment écrits par des élèves peu expérimentés. Cela l'oblige à chaque fois à des manipulations compliquées pour stopper ces programmes. Il voit alors dans un journal spécialisé une publicité:
<BLOCKQUOTE>Ne laissez plus boucler vos programmes! Utilisez notre fonction termine(o). Elle prend comme paramètre le nom d'un objet et répond true si la procédure f de cet objet ne boucle pas indéfiniment et false sinon. En n'utilisant que les procédures pour lesquelles termine répond true, vous évitez tous les problèmes de non terminaison. D'ailleurs, voici quelques exemples: </BLOCKQUOTE>class Turing {
static boolean termine (Object o) {
// détermine la terminaison de o.f()
boolean resultat;
// contenu breveté par le vendeur
return resultat;
}
}
class Facile {
void f () {
}
}
class Boucle {
void f () {
for (int i = 1; i > 0; ++i)
;
}
}
class Test {
public static void main (String args[]) {
Facile o1 = new Facile();
System.out.println (Turing.termine(o1));
Boucle o2 = new Boucle();
System.out.println (Turing.termine(o2));
}
}
<BLOCKQUOTE>pour lesquels termine(o) répond true puis false. </BLOCKQUOTE>Impressionné par la publicité, le responsable des travaux pratiques achète à prix d'or cette petite merveille et pense que sa vie d'enseignant va être enfin tranquille. Un élève lui fait toutefois remarquer qu'il ne comprend pas l'acquisition faite par le Maître avec la classe suivante:
class Absurde {
void f () {
while (Turing.termine(this))
;
}
class Test {
public static void main (String args[]) {
Absurde o3 = new Absurde();
System.out.println (Turing.termine(o3));
}
}
Si la procédure o3.f boucle indéfiniment, alors termine(o3) = false. Donc la boucle while de o3.f s'arrête et o3.f termine. Sinon, si la procédure o3.f ne boucle pas indéfiniment, alors termine(o3) = true. La boucle while précédente boucle indéfiniment, et la procédure o3.f boucle indéfiniment. Il y a donc une contradiction sur les valeurs possibles de termine(o3). Cette expression ne peut être définie. Ayant noté le mauvais esprit de l'Elève, le Maître conclut qu'on ne peut décidément pas faire confiance à la presse spécialisée!
L'histoire est presque vraie. Le Maître s'appelait David Hilbert et voulait montrer la validité de sa thèse par des moyens automatiques. L'Elève impertinent était Kurt Gödel. Le tout se passait vers 1930. Grâce à Gödel, on s'est rendu compte que toutes les fonctions mathématiques ne sont pas calculables par programme. Par exemple, il y a beaucoup plus de fonctions de N (entiers naturels) dans N que de programmes qui sont en quantité dénombrable. Gödel, Turing, Church et Kleene sont parmi les fondateurs de la théorie de la calculabilité.
Pour être plus précis, on peut remarquer que nous demandons beaucoup à notre fonction termine, puisqu'elle prend en argument un objet (en fait une ``adresse mémoire''), désassemble peut-être la procédure correspondante, et décide de sa terminaison. Sinon, elle ne peut que lancer l'exécution de son argument et ne peut donc tester sa terminaison (quand il ne termine pas). Un résultat plus fort peut être montré: il n'existe pas de fonction prenant en argument le source de toute procédure (en tant que chaîne de caractères) et décidant de sa terminaison. C'est ce résultat qui est couramment appelé l'indécidabilité de l'arrêt. Mais montrer la contradiction en Java est alors beaucoup plus dur.
2.3 Procédures récursives
<BLOCKQUOTE>
Figure 2.2 : Les tours de Hanoi
</BLOCKQUOTE>Les procédures, comme les fonctions, peuvent être récursives, et comporter un appel récursif. L'exemple le plus classique est celui des tours de Hanoi. On a 3 piquets en face de soi, numérotés 1, 2 et 3 de la gauche vers la droite, et n rondelles de tailles toutes différentes entourant le piquet 1, formant un cône avec la plus grosse en bas et la plus petite en haut. On veut amener toutes les rondelles du piquet 1 au piquet 3 en ne prenant qu'une seule rondelle à la fois, et en s'arrangeant pour qu'à tout moment il n'y ait jamais une rondelle sous une plus grosse. La légende dit que les bonzes passaient leur vie à Hanoi à résoudre ce problème pour n=64, ce qui leur permettait d'attendre l'écroulement du temple de Brahma, et donc la fin du monde (cette légende fut inventée par le mathématicien français E. Lucas en 1883). Un raisonnement par récurrence permet de trouver la solution en quelques lignes. Si n £ 1, le problème est trivial. Supposons maintenant le problème résolu pour n-1 rondelles pour aller du piquet i au piquet j. Alors, il y a une solution très facile pour transférer n rondelles de i en j:1- on amène les n-1 rondelles du haut de i sur le troisième piquet k = 6 - i - j,
2- on prend la grande rondelle en bas de i et on la met toute seule en j,
3- on amène les n-1 rondelles de k en j.
Ceci s'écrit
static void hanoi(int n, int i, int j) {
if (n > 0) {
hanoi (n-1, i, 6-(i+j));
System.out.println (i + " -> " + j);
hanoi (n-1, 6-(i+j), j);
}
}
Ces quelques lignes de programme montrent bien comment en généralisant le problème, c'est-à-dire aller de tout piquet i à tout autre j, un programme récursif de quelques lignes peut résoudre un problème a priori compliqué. C'est la force de la récursion et du raisonnement par récurrence. Il y a bien d'autres exemples de programmation récursive, et la puissance de cette méthode de programmation a été étudiée dans la théorie dite de la récursivité qui s'est développée bien avant l'apparition de l'informatique (Kleene [25], Rogers [45]). Le mot récursivité n'a qu'un lointain rapport avec celui qui est employé ici, car il s'agissait d'établir une théorie abstraite de la calculabilité, c'est à dire de définir mathématiquement les objets qu'on sait calculer, et surtout ceux qu'on ne sait pas calculer. Mais l'idée initiale de la récursivité est certainement à attribuer à Kleene (1935).
