summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2019-01-16 09:12:15 (GMT)
committerDavid A. Madore <david+git@madore.org>2019-01-16 09:12:15 (GMT)
commit6cfbd59408a18b2a42374dec35ff109f916b4e76 (patch)
treea47ccf4773799669cee5068f08c9f4654925b85f
parentc7ec3f78b0bd5d10f0e9bc517de0d8408dc0dfab (diff)
downloadinf105-6cfbd59408a18b2a42374dec35ff109f916b4e76.zip
inf105-6cfbd59408a18b2a42374dec35ff109f916b4e76.tar.gz
inf105-6cfbd59408a18b2a42374dec35ff109f916b4e76.tar.bz2
Fix bijection between ℕ² and ℕ.
-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} :