diff options
| -rw-r--r-- | transp-inf110-01-calc.tex | 13 |
1 files changed, 8 insertions, 5 deletions
diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex index de79253..25c78e1 100644 --- a/transp-inf110-01-calc.tex +++ b/transp-inf110-01-calc.tex @@ -336,6 +336,7 @@ Le codage de Gödel simplifie l'approche/définition de la calculabilité \end{frame} % \begin{frame} +\label{codage-de-goedel} \frametitle{Codage de Gödel (« tout est un entier »)} \itempoint Représenter \textbf{n'importe quelle donnée finie par un @@ -359,12 +360,13 @@ 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_pair(m,n): return m+(m+n)*(m+n+1)/2 %%% def encode(t): %%% if isinstance(t, list): %%% v=0 -%%% for x in t: +%%% for x in reversed(t): %%% m = encode(x) -%%% v = m+(m+v)*(m+v+1)/2 + 1 +%%% v = encode_pair(m,v) + 1 %%% return v %%% else: return t @@ -804,7 +806,7 @@ induction suivant la déf\textsuperscript{n} de $\mathbf{PR}$ \[ \begin{aligned} \psi_e^{(k+1)}(\underline{x},0) &= g(\underline{x})\\ -\psi_e^{(k+1)}(\underline{x},z+1) &= h(\underline{x},f(\underline{x},z),z) +\psi_e^{(k+1)}(\underline{x},z+1) &= h(\underline{x}, \psi_e^{(k+1)}(\underline{x},z),z) \end{aligned} \] \end{itemize} @@ -819,8 +821,9 @@ par définition. {\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 = - 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} + 1\,459\,411\,784\,487\,\ldots\,780\,615\,609\,825 \approx + 1.459\times 10^{357}$ définit $\psi^{(2)}_e(x,z) = x+z$ avec les + conventions de codage du transp. \ref{codage-de-goedel}.\par} \end{frame} % |