From 6cfbd59408a18b2a42374dec35ff109f916b4e76 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Wed, 16 Jan 2019 10:12:15 +0100 Subject: =?UTF-8?q?Fix=20bijection=20between=20=E2=84=95=C2=B2=20and=20?= =?UTF-8?q?=E2=84=95.?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- notes-inf105.tex | 6 +++--- 1 file 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} : -- cgit v1.2.3