From 4eec2f1af437e7136d81ce6cb724afcf5d758fbe Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Fri, 4 Nov 2016 17:05:21 +0100
Subject: Notes on computability.

---
 notes-calculabilite.tex | 605 ++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 605 insertions(+)
 create mode 100644 notes-calculabilite.tex

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}
-- 
cgit v1.2.3