diff options
Diffstat (limited to 'notes-inf105.tex')
| -rw-r--r-- | notes-inf105.tex | 6 |
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} : |