summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--notes-inf105.tex6
1 files changed, 3 insertions, 3 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex
index 8dd9af9..0e3b388 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -6319,7 +6319,7 @@ variables, et de parler de fonction calculable $\mathbb{N}^k \to
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
+par $(m,n) \mapsto 2^m(2n+1)-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.
@@ -6414,7 +6414,7 @@ $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)$).
+2^m(2n+1)-1$).
Réciproquement, si $A$ est calculablement énumérable, disons $A =
f(\mathbb{N})$ avec $f$ calculable, on obtient un algorithme qui
@@ -6567,7 +6567,7 @@ 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
+(par exemple par $(e,n) \mapsto 2^e(2n+1)-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} :