Fix various small mistakes or unclear points.

1 files changed, 8 insertions, 9 deletions

diff --git a/exercices-inf110.tex b/exercices-inf110.tex
index d43d56f..4613d8b 100644
--- a/exercices-inf110.tex
+++ b/exercices-inf110.tex
@@ -274,7 +274,7 @@ décidable.
 \textbf{(2)} Soit $H := \{d \in \mathbb{N} :
 \varphi^{(1)}_d(0)\downarrow\}$ (variante du problème de l'arrêt).
 Rappeler brièvement pourquoi $H$ est semi-décidable mais non
-décidable, et pourquoi son complémentair $\complement H$ n'est pas
+décidable, et pourquoi son complémentaire $\complement H$ n'est pas
 semi-décidable.
 
 \textbf{(3)} Montrer qu'il existe une fonction $\rho \colon \mathbb{N}
@@ -512,8 +512,8 @@ dont l'\emph{extension} est primitive récursive ; \textit{grosso
 Manifestement, $M \subseteq N$, car si $\psi^{(1)}_e$ est définie, on
 a $\varphi^{(1)}_e = \psi^{(1)}_e$ (la définition des fonctions
 générales récursives \emph{étend} celle des fonctions p.r.).
-L'inclusion dans l'autre sens ne vaut pas : on peut calculer la
-fonction constante nulle en faisant une boucle infinie, ce qui fournit
+L'inclusion dans l'autre sens ne vaut pas : on peut calculer une
+fonction non p.r., jeter le résultat, et renvoyer $0$, ce qui fournit
 un code $e$ tel que $\varphi^{(1)}_e$ est primitive récursive (donc
 $e\in N$) et pourtant $\psi^{(1)}_e$ n'est pas définie (donc $e\not\in
 M$).
@@ -773,7 +773,7 @@ donnée d'un état parmi au plus $m$, d'une position de la tête parmi au
 plus $p(n)$ (puisque la tête visite au plus ce nombre de cellules), et
 de la valeur de chaque cellule du ruban ; or au plus $p(n)+n$ cellules
 peuvent contenir un $1$ (à n'importe quel moment de l'exécution), car
-la tête n'en viiste qu'au plus $p(n)$ et au plus $n$ portent un $1$
+la tête n'en visite qu'au plus $p(n)$ et au plus $n$ portent un $1$
 initialement : il y a donc au plus $2^{p(n)+n}$ configurations
 possibles du ruban, et au plus $m\times p(n)\times 2^{p(n)+n}$
 configurations de l'ensemble de la machine.
@@ -787,11 +787,10 @@ distinctes, donc termine en au plus $m\times p(n)\times 2^{p(n)+n}$
 étapes.
 
 \textbf{(3)} On vient de montrer que le calcul de $f$ par
-$\mathscr{M}$ es fait en temps au plus $m\times p(n)\times
-2^{p(n)+n}$.  Mais ceci est une fonction p.r. de $n$ (car $p$ l'est,
-et que $k \mapsto 2^k$ l'est, et que $m$ est une constante ici).  Donc
-$f$ est calculée en complexité en temps p.r., donc elle est elle-même
-p.r.
+$\mathscr{M}$ fait en temps au plus $m\times p(n)\times 2^{p(n)+n}$.
+Mais ceci est une fonction p.r. de $n$ (car $p$ l'est, et que $k
+\mapsto 2^k$ l'est, et que $m$ est une constante ici).  Donc $f$ est
+calculée en complexité en temps p.r., donc elle est elle-même p.r.
 \end{corrige}
 
 %