Diaporama

Il s'agit d'une conjecture mathématique qui va nous servir d'exemple pour comprendre ce qu'est la décidabilité.

Exemples : $126 = 113 + 13$, $128 = 109 + 19 = 31 + 97$… Il peut y avoir plusieurs solutions, l'important est qu'il y en ait au moins une.

Cette conjecture a été vérifiée pour tous les nombres pairs jusqu'à $4\times 10^{18}$. La plupart des mathématiciens pensent qu'elle est vraie. Mais elle n'a pas encore été démontrée.

Se peut-il qu'elle soit toujours vraie mais qu'il soit impossible de le démontrer ?

La conjecture de Golbach est peut-être indécidable ou peut-être qu'il existe une démonstration mais qu'on ne l'a pas trouvée. Il est difficile de de démontrer qu'une démonstration n'existe pas…

L'un des objectifs de ce cours est de prouver qu'il existe des propositions indécidables.

David Hilbert est considéré comme un des plus grands mathématiciens du XXe siècle. En 1920, il propose un programme de recherche visant à bâtir les mathématiques sur des bases plus rigoureuses.

Il propose que les mathématiques soient fondées sur des axiomes – vérités premières admises – correctement choisis, en nombre le plus petit possible.

David Hilbert se demande : toute propriété pouvant être énoncée – sans ambiguïté, dans le langage mathématique – est-elle décidable. Dit autrement : existe-t-il des propriété indécidables.

En 1929, le logicien Kurt Gödel prouve que la réponse est oui, il existe des propriétés indécidables, dans certain cas. Voici – en gros traits – ce que dit Gödel :

Dans une théorie mathématique contenant $\mathbb{N}$ – donc une théorie permettant de décrire les entiers naturels – on a deux possibilités, selon le choix des axiomes de départ :

• soit certaines vérités sont indémontrables – indécidables,
• soit on aboutit à des contradictions.

Pour que la théorie reste cohérente – pas de contradiction – il faut donc accepter l'idée que certaines vérités restent indécidables.

Nous avons dit : Propriété décidable = Il existe une démonstration permettant de dire si la propriété est vraie ou non.

En informatique, on donne au mot un sens légèrement différent :

1. Le problème de savoir si 442 est pair est-il décidable ?
2. Le problème de savoir si 443 est premier est-il décidable ?

1. L'ensemble des nombres pairs est-il décidable ?
2. L'ensemble des nombres premiers est-il décidable ?

• Les données à traiter sont écrites sur une bande magnétique qui peut avancer ou reculer.
• Quand la machine s'arrête sur un symbole elle peut lire le symbole et écrire un autre symbole.
• La machine est fabriquée pour faire un travail bien défini. Par exemple, multiplier par 2. Alors on écrit les symboles 345 sur la bande, et la machine, à la fin de son traitement, aura remplacé 345 par 690, c'est à dire le double.

On se pose des questions comme “Y a-t-il des problèmes indécidables ? Lesquels ?”

Si on veut justifier qu'un problème est indécidable, il faut montrer qu'aucun algorithme d'aucune sorte ne permettra la décision, même avec des technologies que l'on ne connaît pas encore.

La machine de Turing fait penser à un ordinateur primitif. Mais elle ne sert pas à fabriquer un ordinateur. La machine de Turing est une machine abstraite que l'on n'essaie même pas de fabriquer. Elle sert seulement à réfléchir sur les algorithmes, à dire ce qui est possible et ce qui ne l'est pas.

• La machine utilise un ruban découpé en cases. Dans les cases ont peut trouver des symboles : 0, 1, A, #, etc.
• Pour une case vide, on convient que le symbole est _
• La machine étant théorique, on peut dire que la bande est infinie dans les deux sens. Par contre, au démarrage, il y a un nombre fini de symboles sur la bande.
• La machine possède une tête de lecture / écriture lui permettant de lire le symbole écrit et d'en écrire un. Écrire _ revient à effacer le contenu.
• On peut déplacer la bande d'un côté ou de l'autre ce qui revient à déplacer la tête de lecture / écriture.
• La machine possède des états de fonctionnement. Il s'agit d'une simple variable disant par exemple “je suis dans l'état 0”, “je suis dans l'état 1” et qui fonctionne comme une simple étiquette.
• Au démarrage la machine est dans l'état initial. Au gré de son fonctionnement elle passe d'un état à l'autre. Quand elle arrive dans l'état final, elle s'arrête, elle a terminé.
• La machine a une table de fonctionnement. C'est en quelque sorte son programme.

1. Lecture du symbole sous la tête de lecture / écriture.
2. Dans la table, recherche de la ligne correspondant à l'état en cours et au symbole lu. Soit (L) cette ligne.
3. (L) indique quel symbole il faut écrire → Écriture de ce symbole sur la bande.
4. (L) indique si la tête doit se décaler d'une case à gauche, une case à droite, ou ne pas bouger → Exécution du mouvement.
5. (L) indique dans quel état la machine doit passer → Actualisation de l'état.
6. Si l'état courant est l'état final, arrêt. Sinon la machine recommence en 1.

Les machines de Turing ont toutes ce fonctionnement. Les différentes machines se caractérisent par :

• la site des symboles autorisés,
• la table de transition.

Soit une machine acceptant les symboles 0 et 1 (le symbole _ est toujours possible)

Voici sa table de transition :

Supposons qu'au démarrage il est écrit [1]10010010 sur la bande.

Décrire le déroulement du fonctionnement de la machine.

Utiliser le site http://morphett.info/turing/ pour simuler la machine précédente.

Les symboles écrits sur la bande forment un mot. Ce mot peut être compris comme un nombre. Par exemple, le mot 110010 est l'écriture binaire de 50.

1. Concevez la machine qui, partant de l'écriture binaire d'un nombre $n$, termine avec l'écriture binaire de $2\cdot n$.
2. Concevez la machine qui, partant de l'écriture binaire d'un nombre $n$, termine avec l'écriture binaire de $2n+1$.
3. Concevez la machine qui, partant de l'écriture binaire d'un nombre $n$, termine avec l'écriture binaire de $n+1$. C'est plus difficile !

Nos exemples sont des machines utilisant les symboles 0 et 1. Les mot initial et le mot final ne doivent contenir que les symboles 0 et 1.

Mais parfois, le bon déroulement du programme peut nécessiter d'ajouter d'autres symboles. On est autorisé à ajouter ces symboles en les choisissant pour qu'ils ne créent pas de confusion. On utilise souvent #.

Concevez un programme qui partant d'un mot $u$ écrit avec des 0 et des 1, termine avec l'écriture inversée de $u$. Par exemple 11000 doit devenir 00011.

Vous aurez besoin d'utiliser un symbole supplémentaire.

On appelle $\Sigma$ l'ensemble des symboles sur lesquels la machine doit pouvoir calculer. On raisonne souvent en ne considérant que les symboles 0 et 1. $\Sigma$ ne contient pas _. $\Sigma$ est appelé un alphabet. On parle aussi de langage pour l'ensemble des mots sur laquelle la machine est susceptible de fonctionner.

Dans les années 1930, Alonzo Church (1903 - 1995) invente le $\lambda$-calcul. C'est un langage informatique théorique ou tout est fonction. Les travaux de Church précèdent de peu ceux de Turing mais ils finiront par travailler ensemble.

Les langages de programmation Lisp, Haskell, oCaml sont influencés par le $\lambda$-calcul.

Nous allons poursuivre avec les machines de Turing bien que historiquement, les résultats qui nous intéressent ont d'abord été formulés dans le cadre du $\lambda$-calcul de Church. Les deux approches sont équivalentes.

On place un mot sur le ruban. Comme le raisonnement est très général et abstrait, on peut imaginer une machine qui fonctionne avec n'importe quel type de symbole (du moment qu'ils sont en nombre fini)

Pour simplifier, on ne va envisager que les symboles de $\Sigma = \lbrace 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\rbrace$, de sorte que le mot écrit sur le ruban représente un nombre entier.

Donc la machine commence avec un nombre $u$ sur le ruban et termine (si elle termine) avec un nombre $v$. On pourra noter comme en mathématiques : $M: u \mapsto v$.

Exemples : On a vu plus haut que l'on pouvait réaliser une machine $M: n \mapsto n+1$ ou encore $M : n \mapsto 2\cdot n$.

Intuitivement, une fonction $f$ est une fonction calculable s'il existe une méthode précise qui, étant donné l'antécédent $x$, permet de calculer en un temps fini l'image $f(x)$ en un nombre fini d'étapes.

La thèse de Church -- Turing nous dit qu'une fonction est calculable si et seulement on peut concevoir une machine de Turing réalisant cette fonction.

1. Les fonctions $n \mapsto n+1$, $n\mapsto 2\cdot n$ sont-elles calculable ?
2. La fonction $n \mapsto n^2 + 3 n + 17$ est-elle calculable ?
3. La fonction $n \mapsto 12$ est-t-elle calculable ?
4. La fonction dont le tableau de valeur est le suivant est-elle calculable ?

On retrouve un problème semblable à celui de la décidabilité : Existe-t-il des fonctions non calculables ? Comment prouvera-t-on qu'il existe des fonctions pour lesquels aucune méthode fini ne permet d'aboutir au résultat ?

Cette preuve peut sembler surprenante car le nombre de machines possibles est infini – je rappelle qu'en gros, deux machines diffèrent par leur table de transition et rien ne nous empêche d'écrire toutes sortes de tables de transitions. Comment le nombre de fonctions pourrait-il être plus grand encore ?

Le nombre de fonctions est infini lui aussi mais d'un infini d'un ordre plus grand.

Voyons comment se faire une idée de ce que pourrait-être une fonction non calculable. Les fonctions calculables sont des fonctions qui une forme de régularité. Elles sont tellement régulières que parfois on peu énoncé une formule de type $f(x)$ qui s'applique à tous les $x$. Mais une fonction est d'abord une association $f:x\mapsto y$ et rien n'oblige qu'il existe une quelconque forme de régularité dans l'association des $x$ et des $y$. On pourrait imaginer une fonction $f$ dont le tableau de valeur, infini, ne présente aucune forme de régularité. Il faudrait alors une machine dont l'écriture de la table de transition serait infinie ce qui n'est pas possible.

Vous pouvez comparer cette idée avec la différence entre $\mathbb{Q}$ et $\mathbb{R}$. Les nombres de $\mathbb{Q}$ peuvent être des nombres dont l'écriture décimale est infinie, comme :

$$\frac{3}{17} = 0,1764705882352941\,1764705882352941\,1764705882352941\,\cdots$$

L'écriture est infinie, mais elle se répète suivant un schéma. En revanche, on sait que $\mathbb{R}$ contient des nombres, comme $\pi$, dont l'écriture décimale est infini et ne présente aucun schéma.

Nous avons dit : Problème décidable = Il existe un algorithme de longueur finie et de temps d'exécution fini qui répond oui ou non à la question posée.

Nous pourrions chercher une fonction $D(x)$ qui reçoit comme antécédent $x$ une certaine question et qui renvoie en sortie oui ou non. Si une telle fonction était calculable, alors on pourrait écrire un algorithme qui calcul $D(x)$ et alors $x$ serait décidable.

Mais nous avons dit que certains problèmes ne sont pas décidables… Donc on ne peut pas réaliser $D$ sur une machine et elle n'est pas calculable.

La calculabilité et la décidabilité sont donc deux notions liées.

Nous avons un argument qui justifie qu'il doit exister des problèmes incalculables / indécidables. Mais nous voulons faire mieux : nous voulons en trouver un.

J'ai indiqué que dans la démonstration de Kurt Gödel, une astuce permet de considérer un énoncé mathématique soit en tant qu'énoncé, soit en tant que nombre.

Nous allons exploiter la machine de Turing avec une idée semblable : La machine va simultanément être machine et donnée.

Là encore, j'utilise une écriture théorique qui dépasse le programme de NSI. Remarquez qu'il s'agit bien d'un théorème avec toute la rigueur mathématique nécessaire.

Il existe une machine $U$ telle que pour toute machine $M$ et tout entier $x$, on e peut trouver un mot $m$ tel que

• $U(m\#x) = 1\#y$ avec $y = M(x)$, si $M(x)$ existe
• $U(m\#x) = 0$ si $M(x)$ n'est pas défini.

Soit une fonction calculable $f: x \mapsto y$. Elle est calculable, donc on peut fabriquer machine $M$ qui calcule $f$.

C'est une machine spécifique, faite exprès pour calculer $f$, elle ne calcule rien d'autre. Elle est comme un circuit électronique qui, une fois soudé, ne saurait faire qu'un calcul.

Le théorème nous dit que l'on peut fabriquer une machine U et que sur cette machine U on pourra simuler le fonctionnement de n'importe quelle machine M. Il suffira pour cela de déterminer un certain mot m, correspondant à la machine M.

La machine $U$ peut simuler toutes les machines possibles. Elle est universelle.

On peut représenter cela de façon plus synthétique.

Il s'agit du problème incalculable que l'on veut énoncer.

Soit $M$ représentant une machine quelconque. $m$ est le nombre représentant $M$ sur la machine universelle. $x$ est une donnée.

On se demande si la fonction $A$ telle que $A(m,x) = \begin{cases}1\text{ si }M(x)\text{ termine}\\0\text{ sinon}\end{cases}$ est calculable.

Nous allons raisonner par l'absurde en supposant que la machine A existe. Cela signifie qu'il existe un programme $a$ que l'on pourrait énoncer ainsi :

FONCTION A(m,x)
  Entrées :
    m: programme correspondant à M
    x: entrée pour laquelle on veut M(x) = f(x)
  DÉBUT
    SI l'exécution de M(x) termine ALORS
      RENVOYER 1
    SINON
      RENVOYER 0
    FIN
  FIN

Nous allons prouver – c'est le principe d'un raisonnement par l'absurde – que l'existence de A aboutit à une contradiction. Pour énoncer cette contradiction, à partir de A, nous concevons une machine Q – ou un programme q ce qui revient au même.

FONCTION Q(m)
  Entrées :
    m: programme correspondant à M
  DÉBUT
    Soit x = m
    SI l'exécution de A(m,x) == 1 ALORS
      TANT QUE 1==1 RÉPÉTER
        # ceci est une boucle infinie
      FIN
    SINON
      RENVOYER 1
    FIN
  FIN

Donc si A(m,m) == 1, Q entre dans une boucle infinie et ne termine pas.

• Soit l'exécution de Q(q) termine Dans ce cas, A(q,q) == 1 et donc en ligne 6 de l'exécution de Q, on entre dans une boucle infinie ⇒ Q(q) ne termine pas.
• Soit l'exécution de Q(q) ne termine pas. Dans ce cas, A(q,q) == 0 et donc en ligne 6 de l'exécution de Q on oriente vers le SINON et Q(q) termine en renvoyant 1.

De façon équivalente, le problème de l'arrêt, est indécidable. C'est à dire qu'il n'existe pas d'algorithme universel qui pour tout algorithme $\alpha$ et toute entrée $x$, pourra conclure $\alpha(x)$ termine ou $\alpha(x)$ ne termine pas.

Comme annoncé, la démonstration repose sur une contradiction comme celle du menteur qui dit “je mens”.

La démonstration est compliquée parce qu'elle se veut très rigoureuse : Dans le paradoxe du menteur, on se dit qu'il y a juste un truc lié à l'ambiguïté des mots, que personne ne mens jamais tout le temps de façon systématique, que cela n'a aucun sens, c'est juste amusant.

La démonstration de Gödel et le problème de l'arrêt s'attache à reproduire la même idée d'une façon très rigoureuse en ne laissant aucune ambiguïté possible, par simple utilisation de la logique.