diff options
| -rw-r--r-- | notes-calculabilite.tex | 605 | ||||
| -rw-r--r-- | notes-inf105.tex | 573 |
2 files changed, 573 insertions, 605 deletions
diff --git a/notes-calculabilite.tex b/notes-calculabilite.tex deleted file mode 100644 index 835acea..0000000 --- a/notes-calculabilite.tex +++ /dev/null @@ -1,605 +0,0 @@ -\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} diff --git a/notes-inf105.tex b/notes-inf105.tex index 67cb074..2d7c3e8 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -3891,6 +3891,579 @@ mais leur écriture est plus difficile et les messages d'erreur qu'ils retournent sont plus difficiles à comprendre. +% +% +% + +\section{Introduction à la calculabilité} + +\setcounter{comcnt}{0} + +\thingy\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 + +\thingy 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 + +\thingy\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\thingy\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} + +\thingy\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\thingy\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\thingy\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 + +\thingy\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\thingy\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\thingy\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\thingy\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\thingy\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\thingy\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} + + + % |