path: root/notes-calculabilite.tex

\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}