diff options
| -rw-r--r-- | notes-calculabilite.tex | 605 |
1 files changed, 605 insertions, 0 deletions
diff --git a/notes-calculabilite.tex b/notes-calculabilite.tex new file mode 100644 index 0000000..835acea --- /dev/null +++ b/notes-calculabilite.tex @@ -0,0 +1,605 @@ +\documentclass[12pt,a4paper]{article} % -*- coding: utf-8 -*- +\usepackage[a4paper]{geometry} +\usepackage[francais]{babel} +\usepackage[utf8]{inputenc} +\usepackage[T1]{fontenc} +\usepackage{times} +\usepackage{amsmath} +\usepackage{amsfonts} +\usepackage{amssymb} +\usepackage{amsthm} +\usepackage{mathrsfs} +%\usepackage{bm} +\usepackage{stmaryrd} +\usepackage{wasysym} +\usepackage{url} +\usepackage{graphicx} +\usepackage[usenames,dvipsnames]{xcolor} +%\usepackage{tikz} +%\usetikzlibrary{matrix,arrows,decorations.markings} +\usepackage{hyperref} +% +% +% +\theoremstyle{definition} +\newtheorem*{defn}{Définition} +\newtheorem*{prop}{Proposition} +\newtheorem*{lem}{Lemme} +\newtheorem*{thm}{Théorème} +\newtheorem*{cor}{Corollaire} +\renewcommand{\qedsymbol}{\smiley} +% +\mathchardef\emdash="07C\relax +\mathchardef\hyphen="02D\relax +\DeclareUnicodeCharacter{00A0}{~} +% +% +% +\begin{document} +\pretolerance=8000 +\tolerance=50000 + +\textbf{Discussion préalable.} On s'intéresse ici à la question de +savoir ce qu'un \textbf{algorithme} peut ou ne peut pas faire. Pour +procéder de façon rigoureuse, il faudrait formaliser la notion +d'algorithme (par exemple à travers le concept de machine de Turing) : +on a préféré rester informel sur cette définition — par exemple « un + algorithme est une série d'instruction précises indiquant des + calculs à effectuer étape par étape et qui ne manipulent, à tout + moment, que des données finies » ou « un algorithme est quelque + chose qu'on pourrait, en principe, implémenter sur un ordinateur » — +étant entendu que cette notion est déjà bien connue et comprise, au +moins dans la pratique. Les démonstrations du fait que tel ou tel +problème est décidable par un algorithme ou que telle ou telle +fonction est calculable par un algorithme deviennent beaucoup moins +lisibles quand on les formalise avec une définition rigoureuse +d'algorithme (notamment, programmer une machine de Turing est encore +plus fastidieux que programmer en assembleur un ordinateur, donc +s'il s'agit d'exhiber un algorithme, c'est probablement une mauvaise +idée de l'écrire sous forme de machine de Turing). + +Néanmoins, il est essentiel de savoir que ces formalisations +existent : on peut par exemple évoquer le paradigme du +$\lambda$-calcul de Church (la première formalisation rigoureuse de la +calculabilité), les fonctions générales récursives (=$\mu$-récursives) +à la Herbrand-Gödel-Kleene, les machines de Turing (des machines à +états finis capables de lire, d'écrire et de se déplacer sur un ruban +infini contenant des symboles d'un alphabet fini dont à chaque instant +tous sauf un nombre fini sont des blancs), les machines à registres, +le langage « FlooP » de Hofstadter, etc. Toutes ces formalisations +sont équivalentes (au sens où, par exemple, elles conduisent à la même +notion de fonction calculable ou calculable partielle, définie +ci-dessous). La \textbf{thèse de Church-Turing} affirme, au moins +informellement, que tout ce qui est effectivement calculable par un +algorithme\footnote{Voire, dans certaines variantes, physiquement + calculable dans notre Univers.} est calculable par n'importe +laquelle de ces notions formelles d'algorithmes, qu'on peut rassembler +sous le nom commun de \textbf{calculabilité au sens de Church-Turing}, +ou « calculabilité » tout court. + +Notamment, quasiment tous les langages de programmation +informatique\footnote{C, C++, Java, Python, JavaScript, Lisp, OCaml, + Haskell, Prolog, etc. Certains langages se sont même révélés + Turing-complets alors que ce n'était peut-être pas voulu : par + exemple, HTML+CSS.}, au moins si on ignore les limites des +implémentations et qu'on les suppose capables de manipuler des +entiers, chaînes de caractère, tableaux, etc., de taille arbitraire +(mais toujours finie)\footnote{Autre condition : ne pas utiliser de + générateur aléatoire matériel.}, sont « Turing-complets », +c'est-à-dire équivalents dans leur pouvoir de calcul à la +calculabilité de Church-Turing. Pour imaginer intuitivement la +calculabilité, on peut donc choisir le langage qu'on préfère et +imaginer qu'on programme dedans. Essentiellement, pour qu'un langage +soit Turing-complet, il lui suffit d'être capable de manipuler des +entiers de taille arbitraire, de les comparer et de calculer les +opérations arithmétiques dessus, et d'effectuer des tests et des +boucles. + +\medbreak + +Il faut souligner qu'on s'intéresse uniquement à la question de savoir +ce qu'un algorithme peut ou ne peut pas faire (calculabilité), pas au +temps ou aux autres ressources qu'il peut prendre pour le faire +(complexité), et on ne cherche donc pas à rendre les algorithmes +efficaces en quelque sens que ce soit. Par exemple, pour arguër qu'il +existe un algorithme qui décide si un entier naturel $n$ est premier +ou non, il suffit de dire qu'on peut calculer tous les produits $pq$ +avec $2\leq p,q\leq n-1$ et tester si l'un d'eux est égal à $n$, peu +importe que cet algorithme soit absurdement inefficace. De même, nos +algorithmes sont capables de manipuler des entiers arbitrairement +grands : ceci permet de dire, par exemple, que toute chaîne binaire +peut être considérée comme un entier, peu importe le fait que cet +entier ait peut-être des milliards de chiffres (dans les langages +informatiques réels, on a rarement envie de considérer toute donnée +comme un entier, mais en calculabilité on peut se permettre de le +faire). + +Notamment, plutôt que de considérer des « mots » (éléments +de $\Sigma^*$ avec $\Sigma$ un alphabet fini) et « langages » (parties +de $\Sigma^*$), il sera plus pratique de remplacer l'ensemble +$\Sigma^*$ des mots par l'ensemble des entiers naturels, quitte à +choisir un codage (calculable !) des mots par des entiers. (À titre +d'exemple, on obtient une bijection de l'ensemble $\{0,1\}^*$ des mots +sur l'alphabet à deux lettres avec $\mathbb{N}$ de la façon suivante : +ajouter un $1$ au début du mot, lire celui-ci comme un nombre binaire, +et soustraire $1$. Plus généralement, une fois choisi un ordre total +sur l'alphabet fini $\Sigma$, on peut trier les mots par ordre de +taille, et, à taille donnée, par ordre lexicographique, et leur +associer les entiers naturels dans le même ordre : il n'est pas +difficile de montrer que cela donne bien une bijection calculable +entre $\Sigma^*$ et $\mathbb{N}$.) + +\medbreak + +\textbf{Terminaison des algorithmes.} Un algorithme qui effectue un +calcul utile doit certainement terminer en temps fini. Néanmoins, +même si on voudrait ne s'intéresser qu'à ceux-ci, il n'est pas +possible d'ignorer le « problème » des algorithmes qui ne terminent +jamais (et ne fournissent donc aucun résultat). C'est le point +central de la calculabilité (et du théorème de Turing ci-dessous) +qu'on ne peut pas se débarrasser des algorithmes qui ne terminent +pas : on ne peut pas, par exemple, formaliser une notion +suffisante\footnote{Tout dépend, évidemment, de ce qu'on appelle + « suffisant » : il existe bien des notions de calculabilité, plus + faibles que celle de Church-Turing, où tout calcul termine, voir par + exemple la notion de fonction « primitive récursive » ou le langage + « BlooP » de Hofstadter ; mais de telles notions ne peuvent pas + disposer d'une machine universelle comme expliqué plus loin (en + raison d'un argument diagonal), donc elles sont nécessairement + incomplètes en un certain sens.} de calculabilité dans laquelle tout +algorithme termine toujours ; ni développer un langage de +programmation suffisamment général dans lequel il est impossible qu'un +programme « plante » indéfiniment ou parte en boucle infinie. (Cette +subtilité est d'ailleurs sans doute en partie responsable de la +difficulté historique à dégager la bonne notion d'« algorithme » : on +a commencé par développer des notions d'algorithmes terminant +forcément, comme les fonctions primitives récursives, et on se rendait +bien compte que ces notions étaient forcément toujours incomplètes.) + +\bigbreak + +\begin{defn} +On dit qu'une fonction $f\colon\mathbb{N}\to\mathbb{N}$ est +\textbf{calculable} (ou « récursive ») lorsqu'il existe un algorithme +qui prend en entrée $n\in\mathbb{N}$, termine toujours en temps fini, +et calcule (renvoie) $f(n)$. + +On dit qu'un ensemble $A \subseteq \mathbb{N}$ (« langage ») est +\textbf{décidable} (ou « calculable » ou « récursif ») lorsque sa +fonction indicatrice $\mathbf{1}_A \colon \mathbb{N} \to \mathbb{N}$ +(valant $1$ sur $A$ et $0$ sur son complémentaire) est calculable. +Autrement dit : lorsqu'il existe un algorithme qui prend en entrée +$n\in\mathbb{N}$, termine toujours en temps fini, et renvoie +« oui » ($1$) si $n\in A$, « non » ($0$) si $n\not\in A$ (on dira que +l'algorithme « décide » $A$). + +On dit qu'une fonction partielle +$f\colon\mathbb{N}\dasharrow\mathbb{N}$ (c'est-à-dire une fonction +définie sur une partie de $\mathbb{N}$, appelé ensemble de définition +de $f$) est \textbf{calculable partielle} (ou « récursive partielle ») +lorsqu'il existe un algorithme qui prend en entrée $n\in\mathbb{N}$, +termine en temps fini ssi $f(n)$ est définie, et dans ce cas calcule +(renvoie) $f(n)$. (Une fonction calculable est donc simplement une +fonction calculable partielle qui est toujours définie : on dira +parfois « calculable totale » pour souligner ce fait.) + +On dit qu'un ensemble $A \subseteq \mathbb{N}$ est +\textbf{semi-décidable} (ou « semi-calculable » ou « semi-récursif ») +lorsque la fonction partielle $\mathbb{N}\dasharrow\mathbb{N}$ définie +exactement sur $A$ et y valant $1$, est calculable partielle. +Autrement dit : lorsqu'il existe un algorithme qui prend en entrée +$n\in\mathbb{N}$, termine en temps fini ssi $n \in A$, et renvoie +« oui » ($1$) dans ce cas\footnote{En fait, la valeur renvoyée n'a pas + d'importance ; on peut aussi définir un ensemble semi-décidable + comme l'ensemble de définition d'une fonction calculable partielle.} +(on dira que l'algorithme « semi-décide » $A$). +\end{defn} + +On s'est limité ici à des fonctions d'une seule variable (entière), +mais il n'y a pas de difficulté à étendre ces notions à plusieurs +variables, et de parler de fonction calculable $\mathbb{N}^k \to +\mathbb{N}$ (voire $\mathbb{N}^* \to \mathbb{N}$ avec $\mathbb{N}^*$ +l'ensemble des suites finies d'entiers naturels) ou de fonction +calculable partielle de même type : de toute manière, on peut « coder » +un couple d'entiers naturels comme un seul entier naturel (par exemple +par $(m,n) \mapsto 2^m(2n+1)$, qui définit une bijection calculable +$\mathbb{N}^2 \to \mathbb{N}$), ou bien sûr un nombre fini quelconque +(même variable), ce qui permet de faire « comme si » on avait toujours +affaire à un seul paramètre entier. + +{\footnotesize \textbf{Complément :} Comme on n'a pas défini + formellement la notion d'algorithme, il peut être utile de signaler + explicitement les faits suivants (qui devraient être évidents sur + toute notion raisonnable d'algorithme) : les fonctions constantes + sont calculables ; les opérations arithmétiques usuelles sont + calculables ; les projections $(n_1,\ldots,n_k) \mapsto n_i$ sont + calculables, ainsi que la fonction qui à $(m,n,p,q)$ associe $p$ si + $m=n$ et $q$ sinon ; toute composée de fonctions calculables + (partielle ou totale) est calculable idem ; si $\underline{m} + \mapsto g(\underline{m})$ est calculable (partielle ou totale) et + que $(\underline{m}, n, v) \mapsto h(\underline{m}, n, v)$ l'est, + alors la fonction $f$ définie par récurrence par $f(\underline{m},0) + = g(\underline{m})$ et $f(\underline{m},n+1) = h(\underline{m}, n, + f(\underline{m},n))$ est encore calculable idem (algorithmiquement, + il s'agit juste de boucler $n$ fois) ; et enfin, si $(\underline{m}, + n) \mapsto g(\underline{m},n)$ est calculable partielle, alors la + fonction $f$ (aussi notée $\mu_n g$) définie par $f(\underline{m}) = + \min\{n : g(\underline{m},n) = 0 \land \forall n'<n + (g(\underline{m},n')\downarrow)\}$ (et non définie si ce $\min$ + n'existe pas) est calculable partielle (algorithmiquement, on teste + $g(\underline{m},0),g(\underline{m},1),g(\underline{m},2)\ldots$ + jusqu'à tomber sur $0$). Ces propriétés peuvent d'ailleurs servir à + \emph{définir} rigoureusement la notion de fonction calculable, + c'est le modèle des fonctions « générales récursives ». (Dans ce + qui précède, la notation $\underline{m}$ signifie + $m_1,\ldots,m_k$.)\par} + +\textbf{Exemples :} L'ensemble des nombres pairs, des carrés parfaits, +des nombres premiers, sont décidables, c'est-à-dire qu'il est +algorithmique de savoir si un nombre est pair, parfait, ou premier. +Quitte éventuellement à coder les mots d'un alphabet fini comme des +entiers naturels (cf. plus haut), tout langage rationnel, et même tout +langage défini par une grammaire hors-contexte, est décidable. On +verra plus bas des exemples d'ensembles qui ne le sont pas, et qui +sont ou ne sont pas semi-décidables. + +\medbreak + +Les deux propositions suivantes, outre leur intérêt intrinsèque, +servent à donner des exemples du genre de manipulation qu'on peut +faire avec la notion de calculabilité et d'algorithme : + +\begin{prop} +Un ensemble $A \subseteq \mathbb{N}$ est décidable ssi $A$ et +$\mathbb{N}\setminus A$ sont tous les deux semi-décidables. +\end{prop} +\begin{proof} +Il est évident qu'un ensemble décidable est semi-décidable (si un +algorithme décide $A$, on peut l'exécuter puis effectuer une boucle +infinie si la réponse est « non » pour obtenir un algorithme qui +semi-décide $A$) ; il est également évident que le complémentaire d'un +ensemble décidable est décidable (quitte à échanger les réponses +« oui » et « non » dans un algorithme qui le décide). Ceci montre +qu'un ensemble décidable est semi-décidable de complémentaire +semi-décidable, i.e., la partie « seulement si ». Montrons maintenant +le « si » : si on dispose d'algorithmes $T_1$ et $T_2$ qui +semi-décident respectivement $A$ et son complémentaire, on peut lancer +leur exécution en parallèle sur $n \in \mathbb{N}$ (c'est-à-dire +exécuter une étape de $T_1$ puis une étape de $T_2$, puis de $T_1$, et +ainsi de suite jusqu'à ce que l'un des deux termine) : comme il y en a +toujours (exactement) un qui termine, selon lequel c'est, ceci permet +de décider algorithmiquement si $n \in A$ ou $n \not\in A$. +\end{proof} + +\begin{prop} +Un ensemble $A \subseteq \mathbb{N}$ non vide est semi-décidable ssi +il existe une fonction calculable $f \colon \mathbb{N} \to \mathbb{N}$ +dont l'image ($f(\mathbb{N})$) vaut $A$ (on dit aussi que $A$ est +« calculablement énumérable » ou « récursivement énumérable »). +\end{prop} +\begin{proof} +Montrons qu'un ensemble semi-décidable non vide est calculablement +énumérable. Fixons $n_0 \in A$ une fois pour toutes. Soit $T$ un +algorithme qui semi-décide $A$. On définit une fonction $f \colon +\mathbb{N}^2 \to \mathbb{N}$ de la façon suivante : $f(m,n) = n$ +lorsque l'algorithme $T$, exécuté sur l'entrée $n$, termine au +plus $m$ étapes ; sinon, $f(m,n) = n_0$. On a bien sûr $f(m,n) \in A$ +dans tous les cas ; par ailleurs, si $n \in A$, comme l'algorithme $T$ +appliqué à $n$ doit terminer, on voit que pour $m$ assez grand on a +$f(m,n) = n$, donc $n$ est bien dans l'image de $f$. Ceci montre que +$f(\mathbb{N}^2) = A$. Passer à $f\colon \mathbb{N} \to\mathbb{N}$ +est alors facile en composant par une bijection calculable $\mathbb{N} +\to \mathbb{N}^2$ (par exemple la réciproque de $(m,n) \mapsto +2^m(2n+1)$). + +Réciproquement, si $A$ est calculablement énumérable, disons $A = +f(\mathbb{N})$ avec $f$ calculable, on obtient un algorithme qui +semi-décide $A$ en calculant successivement $f(0)$, $f(1)$, $f(2)$, +etc., jusqu'à trouver un $k$ tel que $f(k)=n$ (où $n$ est l'entrée +proposée), auquel cas l'algorithme renvoie « oui » (et sinon, il ne +termine jamais puisqu'il effectue une boucle infinie à la recherche +d'un tel $k$). +\end{proof} + +{\footnotesize \textbf{Clarification :} Les deux démonstrations + ci-dessus font appel à la notion intuitive d'« étape » de + l'exécution d'un algorithme. Un peu plus précisément, pour chaque + entier $m$ et chaque algorithme $T$, il est possible d'« exécuter au + plus $m$ étapes » de l'algorithme $T$, c'est-à-dire commencer + l'exécution de celui-ci, et si elle n'est pas finie au bout de $m$ + étapes, s'arrêter (on n'aura pas le résultat de l'exécution de $T$, + juste l'information « ce n'est pas encore fini » et d'éventuels + résultats intermédiaires, mais on peut décider de faire autre chose, + y compris reprendre l'exécution plus tard). La longueur d'une + « étape » n'est pas spécifiée et n'a pas d'importance, les choses + qui importent sont que (A) le fait d'exécuter les $m$ premières + étapes de $T$ termine toujours (c'est bien l'intérêt), et (B) si + l'algorithme $T$ termine effectivement, alors pour $m$ suffisamment + grand, exécuter au plus $m$ étapes donne bien le résultat final + de $T$ résultat.\par} + +{\footnotesize \textbf{Complément/exercice :} Un ensemble $A \subseteq + \mathbb{N}$ infini est décidable ssi il existe une fonction + calculable $f \colon \mathbb{N} \to \mathbb{N}$ + \underline{strictement croissante} dont l'image vaut $A$. + (Esquisse : si $A$ est décidable, on peut trouver son $n$-ième + élément par ordre croissant en testant l'appartenance à $A$ de tous + les entiers naturels dans l'ordre jusqu'à trouver le $n$-ième qui + appartienne ; réciproquement, si on a une telle fonction, on peut + tester l'appartenance à $A$ en calculant les valeurs de la fonction + jusqu'à tomber sur l'entier à tester ou le dépasser.) En mettant + ensemble ce fait et la proposition, on peut en déduire le fait + suivant : tout ensemble semi-décidable infini a un sous-ensemble + décidable infini (indication : prendre une fonction qui énumère + l'ensemble et jeter toute valeur qui n'est pas strictement plus + grande que toutes les précédentes).\par} + +\bigbreak + +\textbf{Codage et machine universelle.} Les algorithmes sont +eux-mêmes représentables par des mots sur un alphabet fini donc, si on +préfère, par des entiers naturels : on parle aussi de \textbf{codage + de Gödel} des algorithmes/programmes par des entiers. On obtient +donc une énumération $\varphi_0, \varphi_1, \varphi_2, +\varphi_3\ldots$ de toutes les fonctions calculables partielles (la +fonction $\varphi_e$ étant la fonction que calcule l'algorithme [codé + par l'entier] $e$, avec la convention que si cet algorithme est +syntaxiquement invalide ou erroné pour une raison quelconque, la +fonction $\varphi_e$ est simplement non-définie partout). Les détails +de cette énumération dépendent de la formalisation utilisée pour la +calculabilité. + +Un point crucial dans cette numérotation des algorithmes est +l'existence d'une \textbf{machine universelle}, c'est-à-dire d'un +algorithme $U$ qui prend en entrée un entier $e$ (codant un +algorithme $T$) et un entier $n$, et effectue la même chose que $T$ +sur l'entrée $n$ (i.e., $U$ termine sur les entrées $e$ et $n$ ssi $T$ +termine sur l'entrée $n$, et, dans ce cas, renvoie la même valeur). + +Informatiquement, ceci représente le fait que les programmes +informatiques sont eux-mêmes représentables informatiquement : dans un +langage de programmation Turing-complet, on peut écrire un +\emph{interpréteur} pour le langage lui-même (ou pour un autre langage +Turing-complet), c'est-à-dire un programme qui prend en entrée la +représentation $e$ d'un autre programme et qui exécute ce programme +(sur une entrée $n$). + +Mathématiquement, on peut le formuler comme le fait que la fonction +(partielle) $(e,n) \mapsto \varphi_e(n)$ (= résultat du $e$-ième +algorithme appliqué sur l'entrée $n$) est elle-même calculable +partielle. + +Philosophiquement, cela signifie que la notion d'exécution d'un +algorithme est elle-même algorithmique : on peut écrire un algorithme +qui, donnée une description (formelle !) d'un algorithme et une entrée +à laquelle l'appliquer, effectue l'exécution de l'algorithme fourni +sur l'entrée fournie. + +On ne peut pas démontrer ce résultat ici faute d'une description +rigoureuse d'un modèle de calcul précis, mais il n'a rien de +conceptuellement difficile (même s'il peut être fastidieux à écrire +dans les détails : écrire un interpréteur d'un langage de +programmation demande un minimum d'efforts). + +{\footnotesize \textbf{Compléments :} Les deux résultats classiques + suivants sont pertinents en lien avec la numérotation des fonctions + calculables partielles. $\bullet$ Le \emph{théorème de la forme + normale de Kleene} assure qu'il existe un ensemble + \underline{décidable} $\mathscr{T} \subseteq \mathbb{N}^4$ tel que + $\varphi_e(n)$ soit défini ssi il existe $m,v$ tels que $(e,n,m,v) + \in \mathscr{T}$, et dans ce cas $\varphi_e(n) = v$ (pour s'en + convaincre, il suffit de définir $\mathscr{T}$ comme l'ensemble des + $(e,n,m,v)$ tels que le $e$-ième algorithme exécuté sur l'entrée $n$ + termine en au plus $m$ étapes et renvoie le résultat $v$ : le fait + qu'on dispose d'une machine universelle et qu'on puisse exécuter $m$ + étapes d'un algorithme assure que cet ensemble est bien décidable — + il est même « primitif récursif »). $\bullet$ Le \emph{théorème + s-m-n} assure qu'il existe une fonction calculable $s$ telle que + $\varphi_{s(e,\underline{m})}(\underline{n}) = + \varphi_e(\underline{m},\underline{n})$ (intuitivement, donné un + algorithme qui prend plusieurs entrées et des valeurs + $\underline{m}$ de certaines de ces entrées, on peut fabriquer un + nouvel algorithme dans lequel ces valeurs ont été fixées — c'est à + peu près trivial — mais de plus, cette transformation est + \emph{elle-même algorithmique}, i.e., on peut algorithmiquement + substituer des valeurs $\underline{m}$ dans un programme [codé par + l'entier] $e$ : c'est intuitivement clair, mais cela ne peut pas + se démontrer avec les seules explications données ci-dessus sur + l'énumération des fonctions calculables partielles, il faut regarder + précisément comment le codage standard est fait pour une + formalisation de la calculabilité).\par} + +La machine universelle n'a rien de « magique » : elle se contente de +suivre les instructions de l'algorithme $T$ qu'on lui fournit, et +termine ssi $T$ termine. Peut-on savoir à l'avance si $T$ terminera ? +C'est le fameux « problème de l'arrêt ». + +\smallbreak + +Intuitivement, le « problème de l'arrêt » est la question +« l'algorithme suivant termine-t-il sur l'entrée suivante » ? + +\begin{defn} +On appelle \textbf{problème de l'arrêt} l'ensemble des couples $(e,n)$ +tels que le $e$-ième algorithme termine sur l'entrée $n$, i.e., +$\{(e,n) \in \mathbb{N}^2 : \varphi_e(n)\downarrow\}$ (où la notation +« $\varphi_e(n)\downarrow$ » signifie que $\varphi_e(n)$ est défini, +i.e., l'algorithme termine). Quitte à coder les couples d'entiers +naturels par des entiers naturels (par exemple par $(e,n) \mapsto +2^e(2n+1)$), on peut voir le problème de l'arrêt comme une partie +de $\mathbb{N}$. On peut aussi préférer\footnote{Même si au final + c'est équivalent, c'est \textit{a priori} plus fort de dire que $\{e + \in \mathbb{N} : \varphi_e(e)\downarrow\}$ n'est pas décidable que + de dire que $\{(e,n) \in \mathbb{N}^2 : \varphi_e(n)\downarrow\}$ ne + l'est pas.} définir le problème de l'arrêt comme $\{e \in \mathbb{N} +: \varphi_e(e)\downarrow\}$, on va voir dans la démonstration +ci-dessous que c'est cet ensemble-là qui la fait fonctionner. +\end{defn} + +{\footnotesize (On pourrait aussi définir le problème de l'arrêt comme + $\{e \in \mathbb{N} : \varphi_e(0)\downarrow\}$ si on voulait, ce + serait moins pratique pour la démonstration, mais cela ne changerait + rien au résultat comme on peut le voir en appliquant le théorème + s-m-n.)\par} + +\begin{thm}[Turing] +Le problème de l'arrêt est semi-décidable mais non décidable. +\end{thm} +\begin{proof} +Le problème de l'arrêt est semi-décidable en vertu de l'existence +d'une machine universelle : donnés $e$ et $n$, on exécute le $e$-ième +algorithme sur l'entrée $n$ (c'est ce que fait la machine +universelle), et s'il termine on renvoie « oui » (et s'il ne termine +pas, bien sûr, on n'a pas de choix que de ne pas terminer). + +Montrons par l'absurde que le problème de l'arrêt n'est pas décidable. +S'il l'était, on pourrait définir un algorithme qui, donné un entier +$e$, effectue les calculs suivants : (1º) utiliser le problème de +l'arrêt (supposé décidable !) pour savoir, algorithmiquement en temps +fini, si le $e$-ième algorithme termine quand on lui passe son propre +numéro $e$ en entrée, i.e., si $\varphi_e(e)\downarrow$, (2º) si oui, +effectuer une boucle infinie, et si non, terminer, en renvoyant, +disons, $42$. L'algorithme qui vient d'être décrit aurait un certain +numéro, disons, $p$, et la description de l'algorithme fait que, +quelque soit $e$, la valeur $\varphi_p(e)$ est indéfinie si +$\varphi_e(e)$ est définie tandis que $\varphi_p(e)$ est définie (de +valeur $42$) si $\varphi_e(e)$ est indéfinie. En particulier, en +prenant $e=p$, on voit que $\varphi_p(p)$ devrait être défini si et +seulement si $\varphi_p(p)$ n'est pas défini, ce qui est une +contradiction. +\end{proof} + +La démonstration ci-dessus est une instance de l'« argument diagonal » +de Cantor, qui apparaît souvent en mathématiques. (La « diagonale » +en question étant le fait qu'on considère $\varphi_e(e)$, i.e., on +passe le numéro $e$ d'un algorithme en argument à cet algorithme +lui-même, donc on regarde la diagonale de la fonction de deux +variables $(e,n) \mapsto \varphi_e(n)$ ; en modifiant les valeurs sur +cette diagonale, on produit une fonction qui ne peut pas se trouver +dans une ligne $\varphi_p$.) Une variante facile du même argument +permet de fabriquer des ensembles non semi-décidables (voir le +« bonus » ci-dessous), ou bien on peut appliquer ce qui précède : + +\begin{cor} +Le complémentaire du problème de l'arrêt n'est pas semi-décidable. +\end{cor} +\begin{proof} +On a vu que le problème de l'arrêt n'est pas décidable, et qu'un +ensemble est décidable ssi il est semi-décidable et que son +complémentaire l'est aussi : comme le problème de l'arrêt est bien +semi-décidable, son complémentaire ne l'est pas. +\end{proof} + +{\footnotesize \textbf{Complément :} L'argument diagonal est aussi au + cœur du (voire, équivalent au) \emph{théorème de récursion de + Kleene}, qui affirme que pour toute fonction calculable partielle + $h\colon\mathbb{N}^2\dasharrow\mathbb{N}$, il existe $p$ tel que + $\varphi_p(n) = h(p,n)$ pour tout $n$ (la signification intuitive de + ce résultat est qu'on peut supposer qu'un programme a accès à son + propre code source $p$, i.e., on peut programmer comme s'il recevait + en entrée un entier $p$ codant ce code source ; ceci permet par + exemple — de façon anecdotique mais amusante — d'écrire des + programmes, parfois appelés « quines », qui affichent leur propre + code source sans aller le chercher sur disque ou autre tricherie). + \textit{Démonstration :} donné $e \in \mathbb{N}$, on considère + $s(e,m)$ tel que $\varphi_{s(e,m)}(n) = \varphi_e(m,n)$ : le + théorème s-m-n (cf. ci-dessus) assure qu'une telle fonction + calculable $(e,m) \mapsto s(e,m)$ existe, et $(e,n) \mapsto + h(s(e,e), n)$ est alors aussi calculable partielle ; il existe donc + $q$ tel que $\varphi_q(e,n) = h(s(e,e), n)$ : on pose $p = s(q,q)$, + et on a $\varphi_p(n) = \varphi_q(q,n) = h(s(q,q), n) = h(p, n)$, + comme annoncé. \smiley\ La non-décidabilité du problème de l'arrêt + s'obtient en appliquant (de nouveau par l'absurde) ce résultat à + $h(e, n)$ la fonction qui n'est pas définie si $\varphi_e(n)$ l'est + et qui vaut $42$ si $\varphi_e(n)$ n'est pas définie.\par} + +La non-décidabilité du problème de l'arrêt est un résultat +fondamental, car très souvent les résultats de non-décidabilité soit +sont démontrés sur un modèle semblable, soit s'y ramènent +directement : pour montrer qu'un certain ensemble $A$ (un +« problème ») n'est pas décidable, on cherche souvent à montrer que si +un algorithme décidant $A$ existait, on pourrait s'en servir pour +construire un algorithme résolvant le problème de l'arrêt. + +{\footnotesize \textbf{Bonus / exemple(s) :} L'ensemble des $e \in + \mathbb{N}$ tels que la fonction calculable partielle $\varphi_e$ + soit \underline{totale} (i.e., définie sur tout $\mathbb{N}$) n'est + pas semi-décidable. En effet, s'il l'était, d'après ce qu'on a vu, + il serait « calculablement énumérable », c'est-à-dire qu'il + existerait une fonction calculable $f\colon\mathbb{N}\to\mathbb{N}$ + dont l'image soit exactement l'ensemble des $e$ pour lesquels + $\varphi_e$ est totale, i.e., toute fonction calculable totale + s'écrirait sous la forme $\varphi_{f(k)}$ pour un certain $k$. Mais + la fonction $n \mapsto \varphi_{f(n)}(n) + 1$ est calculable totale, + donc il devrait exister un $m$ tel que cette fonction s'écrive + $\varphi_{f(m)}$, c'est-à-dire $\varphi_{f(m)}(n) = + \varphi_{f(n)}(n) + 1$, et on aurait alors en particulier + $\varphi_{f(m)}(m) = \varphi_{f(m)}(m) + 1$, une + contradiction. $\bullet$ Son complémentaire, c'est-à-dire + l'ensemble des $e \in \mathbb{N}$ tels que la fonction calculable + partielle $\varphi_e$ \underline{ne soit pas} totale, n'est pas non + plus semi-décidable. En effet, supposons qu'il existe un algorithme + qui, donné $e$, termine ssi $\varphi_e$ n'est pas totale. Donnés + $e$ et $m$, considérons l'algorithme qui prend une entrée $n$, + \emph{ignore} celle-ci, et effectue le calcul $\varphi_e(m)$ : ceci + définit une fonction calculable partielle (soit totale et constante, + soit définie nulle part !) $\varphi_{s(e,m)}$ où $s$ est calculable + (on applique ici le théorème s-m-n) — en appliquant à $s(e,m)$ + l'algorithme supposé semi-décider si une fonction récursive + partielle est non-totale, on voit qu'ici il semi-décide si + $\varphi_e(m)$ est non-défini, autrement dit on semi-décide le + complémentaire du problème de l'arrêt, et on a vu que ce n'était pas + possible !\par} + +{\footnotesize \textbf{Exercice :} Considérons une fonction $h$ qui à + $e$ associe un nombre au moins égal au nombre d'étapes + (cf. ci-dessus) du calcul de $\varphi_e(e)$, si celui-ci termine, et + une valeur quelconque si $\varphi_e(e)$ n'est pas défini. Alors $h$ + n'est pas calculable. (Indication : si elle l'était, on pourrait + décider si $\varphi_e(e)$ est défini en exécutant son calcul pendant + $h(e)$ étapes.) On peut même montrer que $H(n) := \max\{h(i) : + i\leq n\}$ domine asymptotiquement n'importe quelle fonction + calculable mais c'est un peu plus difficile.\par} + +\medbreak + +{\footnotesize \textbf{Application à la logique :} Sans rentrer dans + les détails de ce que signifie un « système formel », on peut + esquisser, au moins informellement, les arguments suivants. + Imaginons qu'on ait formalisé la notion de démonstration + mathématique (c'est-à-dire qu'on les écrit comme des mots dans un + alphabet indiquant quels axiomes et quelles règles logiques sont + utilisées) : même sans savoir quelle est exactement la logique + formelle, le fait de \emph{vérifier} qu'une démonstration est + correcte doit certainement être algorithmique (il s'agit simplement + de vérifier que chaque règle a été correctement appliquée), + autrement dit, l'ensemble des démonstrations est décidable. + L'ensemble des théorèmes, lui, est semi-décidable (on a un + algorithme qui semi-décide si un certain énoncé est un théorème en + énumérant toutes les chaînes de caractères possibles et en cherchant + s'il s'agit d'une démonstration valable dont la conclusion est + l'énoncé recherché). Or l'ensemble des théorèmes n'est pas + décidable : en effet, si on avait un algorithme qui permet de + décider si un énoncé mathématique est un théorème, on pourrait + appliquer cet algorithme à l'énoncé formel (*)« le $e$-ième + algorithme termine sur l'entrée $e$ », en observant qu'un tel + énoncé, s'il est vrai, est forcément démontrable (i.e., si + l'algorithme termine, on peut \emph{démontrer} ce fait en écrivant + étape par étape l'exécution de l'algorithme pour constituer une + démonstration qu'il a bien été appliqué jusqu'au bout et a terminé), + et en espérant que s'il est démontrable alors il est vrai : on + aurait alors une façon de décider le problème de l'arrêt, une + contradiction. Mais du coup, l'ensemble des non-théorèmes ne peut + pas être semi-décidable ; or comme l'ensemble des énoncés $P$ tels + que $\neg P$ (« non-$P$ », la négation logique de $P$) soit un + théorème est semi-décidable (puisque l'ensemble des théorèmes + l'est), ils ne peuvent pas coïncider. Ceci montre qu'il existe un + énoncé tel que ni $P$ ni $\neg P$ ne sont des théorèmes : c'est une + forme du \emph{théorème de Gödel} que Turing cherchait à démontrer ; + mieux : en appliquant aux énoncés du type (*), on montre ainsi qu'il + existe un algorithme qui \emph{ne termine pas} mais dont la + non-terminaison \emph{n'est pas démontrable}. (Modulo quelques + hypothèses qui n'ont pas été explicitées sur le système formel dans + lequel on travaille.)\par} + +\end{document} |