Minor clarifications about computability and universality.

1 files changed, 38 insertions, 27 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 0e3b388..1ac129e 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -6456,7 +6456,8 @@ d'un tel $k$).
   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}
+  grande que toutes les précédentes).
+  Cf. exercice \ref{decidable-iff-image-of-computable-increasing}.\par}
 
 \subsection{Machine universelle, et problème de l'arrêt}
 
@@ -6478,36 +6479,46 @@ sont pas importants\footnote{Par exemple, ceux qui aiment le langage
   ce programme est valable (remplacer Java par tout autre langage
   préféré).}.
 
+On aura tendance, dans la suite, à écrire « le $e$-ième algorithme »,
+voire « l'algorithme $e$ » (ou « le programme $e$ »), pour désigner
+l'algorithme codé par l'entier naturel $e$ (c'est-à-dire qu'on
+identifie librement un programme et son codage de Gödel) : on peut
+donc écrire que $\varphi_e(n)$ est le résultat de l'exécution du
+programme $e$ quand on lui fournit $n$ en entrée (ou non défini si
+cette exécution ne termine pas).
+
 \medskip
 
-Un point crucial dans cette numérotation des algorithmes est
-l'existence d'une \defin[universelle (machine)]{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$
-si et seulement si $T$ termine sur l'entrée $n$, et, dans ce cas,
-renvoie la même valeur).
+Un point crucial dans cette numérotation des algorithmes par des
+entiers naturels $e$ est l'existence d'une \defin[universelle
+  (machine)]{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$ si et seulement si $T$ termine
+sur l'entrée $n$, et, dans ce cas, renvoie la même valeur).  Autrement
+dit, le calcul de $\varphi_e(n)$ en fonction de $e$ et $n$ est
+lui-même algorithmique.
 
 \smallskip
 
-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.
+\underline{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} $U$ 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$).
+
+\underline{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.
+
+\underline{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.
 
 \smallskip
 
@@ -9054,7 +9065,7 @@ prouve (1).
 
 %
 
-\exercice
+\exercice\label{decidable-iff-image-of-computable-increasing}
 
 Soit $A \subseteq \mathbb{N}$ un ensemble infini.  Montrer qu'il y a
 équivalence entre :