diff options
| -rw-r--r-- | transp-inf110-01-calc.tex | 22 |
1 files changed, 13 insertions, 9 deletions
diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex index 82f2f47..7bc8ed5 100644 --- a/transp-inf110-01-calc.tex +++ b/transp-inf110-01-calc.tex @@ -413,7 +413,7 @@ $h(g_1(\underline{x}),\ldots,g_k(\underline{x}))\uparrow$. \medskip \itempoint Terminologie : une fonction $f\colon \mathbb{N} \to -\mathbb{N}$ est dite \textbf{totale}. +\mathbb{N}$ définie sur $\mathbb{N}$ est dite \textbf{totale}. {\footnotesize Une fonction totale est un \alert{cas particulier} de fonction partielle !\par} @@ -706,12 +706,12 @@ devrait être calculable. Mais cette définition \alert{n'est pas une \itempoint On peut montrer que : si $f \colon \mathbb{N}^k \to \mathbb{N}$ est p.r., il existe $r$ tel que \[ -f(x_1,\ldots,x_k) \leq A(2,\, (x_1+\cdots+x_k+2),\, r) +f(x_1,\ldots,x_k) \leq A(2,\, (x_1+\cdots+x_k+3),\, r) \] \medskip -\itempoint Notamment, $r \mapsto A(2, 2, r)$ \textbf{n'est pas p.r.} +\itempoint Notamment, $r \mapsto A(2, r, r)$ \textbf{n'est pas p.r.} \medskip @@ -755,6 +755,8 @@ sens informatique). \itempoint Il n'est \alert{pas du tout unique} : $f = \psi_{e_1}^{(k)} = \psi_{e_2}^{(k)} = \cdots$ +{\footnotesize ($e$ = « intention » / $f$ = « extension »)} + \bigskip {\footnotesize @@ -1161,6 +1163,8 @@ sens informatique). \itempoint Il n'est \alert{pas du tout unique} : $f = \varphi_{e_1}^{(k)} = \varphi_{e_2}^{(k)} = \cdots$ +{\footnotesize ($e$ = « intention » / $f$ = « extension »)} + \bigskip {\footnotesize @@ -1285,7 +1289,7 @@ entiers naturels) qui « atteste » que $\varphi_e^{(k)}(\underline{x}) $f(\underline{x},z')=v$ et $h(\underline{x},v,z')=y$ lorsque $z=z'+1$. \item Pour $f = \mu g$, on a des fils attestant - $g(0,\underline{x})=v_0,\ldots,g(y,\underline{x})=v_y$. + $g(0,\underline{x})=v_0,\ldots,g(y,\underline{x})=v_y$ où $v_y=0$. \end{itemize} \medskip @@ -2087,7 +2091,7 @@ de la configuration initiale $C$, et $0$ sinon, \alert{n'est pas \smallskip -$\Rightarrow$ On ne peut tester algorithmiquement si une machine de +$\Rightarrow$ On ne peut pas tester algorithmiquement si une machine de Turing donnée, depuis une configuration initiale donnée, s'arrête « un jour ». @@ -2120,9 +2124,9 @@ Donnée une machine de Turing $M$ et une configuration initiale $C$, on peut alors algorithmiquement décider si $M$ s'arrête à partir de $C$ : \begin{itemize} \item fabriquer une machine $M^*$ qui réalise $C$ à partir de la - configuration vierge $C_0$, puis fait ce que fait $M$ - \textcolor{teal}{($\leftarrow$ théorème s-m-n ici)}, - donc $M^*$ termine sur $C_0$ ssi $M$ termine sur $C$, + configuration vierge $C_0$ \textcolor{teal}{($\leftarrow$ thm + s-m-n ici)}, puis fait ce que fait $M$, donc $M^*$ termine sur + $C_0$ ssi $M$ termine sur $C$, \item calculer $f(m)$ où $m$ est le nombre d'états de $M^*$, \item exécuter $M^*$ à partir de $C_0$ pendant $f(m)$ étapes (ce nombre est $\geq B(m)$ par hypothèse), @@ -2159,7 +2163,7 @@ calculable : {\footnotesize \underline{Preuve :} soit $f\colon\mathbb{N}\to\mathbb{N}$ calculable. -Soit $\gamma(r) = A(2,2,r)$ (en fait, $2^r$ doit suffire ; noter +Soit $\gamma(r) = A(2,r,r)$ (en fait, $2^r$ doit suffire ; noter $\gamma$ croissante). On considère la machine de Turing $M_r$ qui \begin{itemize} \item calcule $\gamma(r+1)$ puis $f(0) + f(1) + \cdots + |