From 06043c0f14dc6ddb1be75ff1247834cd23cb64f7 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Mon, 23 Jan 2017 17:15:53 +0100
Subject: Move notes on computability to main text.

---
 notes-calculabilite.tex | 605 ------------------------------------------------
 1 file changed, 605 deletions(-)
 delete mode 100644 notes-calculabilite.tex

(limited to 'notes-calculabilite.tex')

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