summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--notes-inf105.tex14
1 files changed, 7 insertions, 7 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex
index 8401188..737ff57 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -6256,8 +6256,8 @@ 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$).
+« oui » ($1$) si $n\in A$, et « non » ($0$) si $n\not\in A$ (on dira
+que l'algorithme « décide » $A$).
\smallskip
@@ -6582,11 +6582,11 @@ 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,
-quel que soit $e$, la valeur $\varphi_p(e)$ est indéfinie si
+numéro $e$ en entrée, i.e., si $\varphi_e(e)\downarrow$, et ensuite
+(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, quel que 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