Calculabilité, décidabilité et programme en tant que donnée

Les notions à connaître

Programme en tant que donnée

Le code d'un programme est une suite de caractères (ou d'octets) qu'un autre programme peut manipuler : l'interpréteur Python lit ton fichier .py, un compilateur le traduit en langage machine, le système d'exploitation charge un exécutable en mémoire, un navigateur télécharge un logiciel comme n'importe quel fichier.

Interpréteur et compilateur

Deux programmes qui prennent un programme comme donnée : l'interpréteur l'exécute instruction par instruction (Python), le compilateur le traduit en un autre programme, souvent en langage machine (C), qu'on exécutera ensuite.

Fonction calculable

Fonction pour laquelle il existe un algorithme (un programme) qui, pour chaque entrée, calcule le résultat en un nombre fini d'étapes. Toutes les fonctions ne sont pas calculables.

Problème de décision

Question à laquelle on répond par OUI ou par NON pour chaque entrée : « n est-il premier ? », « cette liste est-elle triée ? », « ce programme s'arrête-t-il sur cette donnée ? ».

Problème décidable, problème indécidable

Décidable : un algorithme répond correctement OUI ou NON, en un temps fini, pour chaque entrée (la primalité d'un entier est décidable). Indécidable : aucun algorithme ne le peut, quel que soit le langage ou la puissance de la machine.

Problème de l'arrêt

Étant donnés un programme et une donnée, savoir si l'exécution du programme sur cette donnée finit par s'arrêter. Il est indécidable : aucun programme arret(programme, donnee) ne peut répondre correctement pour tous les programmes et toutes les données.

Raisonnement par l'absurde

On suppose le contraire de ce qu'on veut montrer (ici : « arret existe ») et on en déduit une contradiction (paradoxe(paradoxe) ne peut ni s'arrêter ni boucler). L'hypothèse est donc fausse.

Machine de Turing

Modèle de calcul décrit par Alan Turing en 1936 : un ruban de cases, une tête qui lit et écrit un symbole, un état, et une table qui dit quoi écrire, où se déplacer et dans quel état passer. Le formalisme n'est pas exigible : retiens que ce modèle très simple calcule tout ce qu'un ordinateur calcule.

Les erreurs à éviter en nsi

• ✗ Croire qu'« indécidable » signifie « on n'a pas encore trouvé l'algorithme »

  ✓ C'est une impossibilité démontrée : aucun algorithme, dans aucun langage, sur aucune machine, ne décidera l'arrêt de tous les programmes.

• ✗ Croire qu'on ne peut jamais savoir si un programme donné s'arrête

  ✓ Pour un programme particulier, on peut souvent le prouver (une boucle for, un compteur qui diminue jusqu'à 0). L'indécidabilité interdit seulement une méthode unique qui réponde pour TOUS les programmes.

• ✗ Penser qu'il suffit d'exécuter le programme et d'attendre

  ✓ S'il s'arrête, tu le sais. S'il tourne encore au bout d'une heure, tu ne peux rien conclure : il s'arrêtera peut-être plus tard, ou jamais.

• ✗ Croire qu'un langage « plus puissant » calcule plus de choses

  ✓ Python, C, Java (et une machine de Turing) calculent exactement les mêmes fonctions. Un langage peut être plus rapide ou plus commode, pas plus puissant au sens de la calculabilité.

• ✗ Confondre calculable et calculable rapidement

  ✓ La calculabilité demande seulement qu'un algorithme existe et termine. La complexité (le coût en temps ou en mémoire) est une autre question.

Sais-tu répondre à ces questions ?

Les corrigés détaillés sont dans le quiz du chapitre.

1. Pourquoi dit-on qu'un programme est aussi une donnée ?
2. Que signifie « le problème de l'arrêt est indécidable » ?
3. Qui a décrit en 1936 la machine qui sert de modèle à la calculabilité, ainsi que la machine universelle ?
4. Un problème se résout par un programme Python. Que peut-on dire de ce même problème en langage C ?
5. On considère la fonction suivante : tant que n est différent de 0, elle retire 2 à n, puis elle renvoie n. ```python def f(n): while n != 0: n = n - 2 return n ``` Pour quels entiers n l'appel f(n) s'arrête-t-il ?