Numbering of recursive functions (compute explicit code for sum function).

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