diff options
| -rw-r--r-- | transp-inf110-01-calc.tex | 18 |
1 files changed, 14 insertions, 4 deletions
diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex index 5609577..4935b36 100644 --- a/transp-inf110-01-calc.tex +++ b/transp-inf110-01-calc.tex @@ -356,6 +356,15 @@ définit une bijection calculable $\mathbb{N}^2 \to \mathbb{N}$ \] définit une bijection calculable $\{\text{suites finies dans $\mathbb{N}$}\} \to \mathbb{N}$ {\footnotesize (avec $\dbllangle\dblrangle := 0$)}. +%%% def encode(t): +%%% if isinstance(t, list): +%%% v=0 +%%% for x in t: +%%% m = encode(x) +%%% v = m+(m+v)*(m+v+1)/2 + 1 +%%% return v +%%% else: return t + \bigskip \itempoint Il sera aussi utile de représenter les \alert{programmes} par des @@ -781,7 +790,7 @@ induction suivant la déf\textsuperscript{n} de $\mathbf{PR}$ \item si $e = \dbllangle 1, k, c\dblrangle$ alors $\psi_e^{(k)}(x_1\ldots,x_k) = c$ (constantes) ; \item si $e = \dbllangle 2\dblrangle$ alors - $\psi_e^{(k)}(x) = x+1$ (successeur) ; + $\psi_e^{(1)}(x) = x+1$ (successeur) ; \item si $e = \dbllangle 3, k, d, c_1,\ldots,c_\ell\dblrangle$ et $g_i := \psi_{c_i}^{(k)}$ et $h := \psi_d^{(\ell)}$, alors $\psi_e^{(k)} \colon \underline{x} \mapsto @@ -804,8 +813,9 @@ p.r. \alert{ssi} $\exists e \in\mathbb{N}.\,(f = \psi_e^{(k)})$. {\tiny P.ex., $e = \dbllangle 4,1,\dbllangle 3,3,\dbllangle 2\dblrangle,\dbllangle 0,3,2\dblrangle\dblrangle,\dbllangle - 0,1,1\dblrangle\dblrangle$ définit $\psi^{(2)}_e(x,z) = x+z$ sauf - erreur (probable) de ma part.\par} + 0,1,1\dblrangle\dblrangle = + 4\,846\,099\,654\,111\,179\,369\,084\,625\,515$ définit + $\psi^{(2)}_e(x,z) = x+z$ sauf erreur (probable) de ma part.\par} \end{frame} % @@ -1189,7 +1199,7 @@ induction suivant la déf\textsuperscript{n} de $\mathbf{R}$ \item si $e = \dbllangle 1, k, c\dblrangle$ alors $\varphi_e^{(k)}(x_1\ldots,x_k) = c$ (constantes) ; \item si $e = \dbllangle 2\dblrangle$ alors - $\varphi_e^{(k)}(x) = x+1$ (successeur) ; + $\varphi_e^{(1)}(x) = x+1$ (successeur) ; \item si $e = \dbllangle 3, k, d, c_1,\ldots,c_\ell\dblrangle$ et $g_i := \varphi_{c_i}^{(k)}$ et $h := \varphi_d^{(\ell)}$, alors $\varphi_e^{(k)} \colon \underline{x} \mapsto |