diff options
| -rw-r--r-- | transp-inf110-01-calc.tex | 263 |
1 files changed, 166 insertions, 97 deletions
diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex index 66a9d84..ce1033f 100644 --- a/transp-inf110-01-calc.tex +++ b/transp-inf110-01-calc.tex @@ -116,6 +116,8 @@ $\rightsquigarrow$automates \itempoint Kurt Gödel (1906–1978) : incomplétude en logique +\itempoint Haskell Curry (1900–1982) : logique combinatoire, lien preuves-typage + \itempoint Alonzo Church (1903–1995) : $\lambda$-calcul \itempoint Alan M. Turing (1912–1954) : machine de Turing, problème de l'arrêt @@ -142,7 +144,7 @@ quand il existe un algorithme qui Difficultés : \begin{itemize} \item Comment définir ce qu'est un algorithme ? -\item Quel type de valeurs ? +\item Quel type de valeurs (acceptées et renvoyées) ? \item Et si l'algorithme ne termine pas ? \item Distinction entre intention (l'algorithme) et extension (la fonction). \end{itemize} @@ -160,7 +162,7 @@ des algorithmes qu'elle étudie, uniquement leur \textbf{terminaison en P.ex. : pour savoir si $n$ est premier, on peut tester si $i\times j=n$ pour tout $i$ et $j$ allant de $2$ à $n-1$. (Hyper inefficace ? -On s'en fout.) +On s'en fiche.) \bigskip @@ -324,7 +326,7 @@ Deux approches opposées : \bigskip Le typage est plus élégant, plus satisfaisant, plus proche de -l'informatique réelle. +l'informatique réelle, on en reparlera. \smallskip @@ -368,8 +370,8 @@ définit une bijection calculable $\{\text{suites finies dans $\mathbb{N}$}\} \t \bigskip -\itempoint Il sera aussi utile de représenter les \alert{programmes} par des -entiers. +\itempoint Il sera aussi utile de représenter même les +\alert{programmes} par des entiers. \bigskip @@ -411,8 +413,8 @@ une fonction $D \to \mathbb{N}$ définie sur une partie $D \subseteq « $f(n)\downarrow$ et $g(m)\downarrow$ et $f(n) = g(m)$ ». \itempoint Convention : $f(n) = g(m)$ signifie « $f(n)\downarrow$ ssi -$g(m)\downarrow$, et $f(n) = g(m)$ si $f(n)\downarrow$ ». (Certains -préfèrent écrire $f(n) \simeq g(m)$ pour ça.) +$g(m)\downarrow$, et $f(n) = g(m)$ si $f(n)\downarrow$ ». +{\footnotesize (Certains préfèrent écrire $f(n) \simeq g(m)$ pour ça.)} \medskip @@ -615,8 +617,9 @@ f(x,y,z+1) &= y \medskip -\itempoint $(u,v) \mapsto \max(u-v,0)$ est p.r. (exercice !) -ou même $u\% v$. +\itempoint $u \mapsto \max(u-1,0)$ est p.r. (exercice !), comme $(u,v) +\mapsto \max(u-v,0)$ ou $(u,v) \mapsto u\% v$ ou $(u,v) \mapsto +\lfloor u/v\rfloor$. \end{frame} % @@ -714,7 +717,7 @@ devrait être calculable. Mais cette définition \alert{n'est pas une \bigskip \itempoint On peut montrer que : si $f \colon \mathbb{N}^k \to -\mathbb{N}$ est p.r., il existe $r$ tel que +\mathbb{N}$ est p.r., il existe $r$ ($=r(f)$) tel que \[ f(x_1,\ldots,x_k) \leq A(2,\, (x_1+\cdots+x_k+3),\, r) \] @@ -742,7 +745,7 @@ terminant clairement). \itempoint Pour (certains) entiers $e \in \mathbb{N}$, on va définir $\psi_e^{(k)}\colon \mathbb{N}^k \to \mathbb{N}$ primitive récursive, la fonction p.r. \alert{codée} par $e$ ou ayant $e$ comme -\textbf{code} (source). +\textbf{code} (source) / « programme ». \bigskip @@ -810,7 +813,8 @@ induction suivant la déf\textsuperscript{n} de $\mathbf{PR}$ \bigskip \itempoint Alors $f\colon \mathbb{N}^k \dasharrow \mathbb{N}$ est -p.r. \alert{ssi} $\exists e \in\mathbb{N}.\,(f = \psi_e^{(k)})$. +p.r. \alert{ssi} $\exists e \in\mathbb{N}.\,(f = \psi_e^{(k)})$ +par définition. {\tiny P.ex., $e = \dbllangle 4,1,\dbllangle 3,3,\dbllangle 2\dblrangle,\dbllangle 0,3,2\dblrangle\dblrangle,\dbllangle @@ -833,7 +837,7 @@ en « langage p.r. ». \medskip -\itempoint Une fonction p.r. a généralement \alert{beaucoup d'indices} : +\itempoint Une fonction p.r. donnée a \alert{beaucoup d'indices} : $\psi_{e_1}^{(k)} = \psi_{e_2}^{(k)} = \cdots$ (programmes équivalents). \medskip @@ -930,17 +934,16 @@ Version formelle de l'astuce de Quine (\forall\underline{x})\quad \psi^{(k)}_e(\underline{x}) = h(e,\underline{x}) \] Plus précisément, il existe $b \colon \mathbb{N}^2 \to \mathbb{N}$ -p.r. telle que +p.r. telle que $e := b(k,d)$ vérifie \[ -(\forall\underline{x})\quad \psi^{(k)}_e(\underline{x}) = \psi^{(k+1)}_d(e,\underline{x}) -\text{~si~}e := b(k,d) +(\forall d)\,(\forall\underline{x})\quad \psi^{(k)}_e(\underline{x}) = \psi^{(k+1)}_d(e,\underline{x}) \] \bigskip -\underline{Preuve :} soit $s := s_{m,1}$ donné par le théorème s-m-n. +\underline{Preuve :} soit $s := s_{1,k}$ donné par le théorème s-m-n. La fonction $(t,\underline{x}) \mapsto h(s(t,t),\underline{x})$ est -p.r., disons $= \psi_c^{(k+1)}(\underline{x})$. Alors +p.r., disons $= \psi_c^{(k+1)}(t,\underline{x})$. Alors \[ \psi_{s(c,c)}^{(k)}(\underline{x}) = \psi_{c}^{(k+1)}(c, \underline{x}) @@ -1072,9 +1075,10 @@ non-terminaisons, donc on doit passer par des \alert{fonctions \begin{frame} \frametitle{L'opérateur $\mu$ de Kleene} -\textbf{Définition :} $\mu g(\underline{x})$ est le plus petit $z$ tel -que $g(z,\underline{x}) = 0$ et $g(i,\underline{x})\downarrow$ pour -$0\leq i<z$, s'il existe. +\textbf{Définition :} si $g\colon \mathbb{N}^{k+1} \dasharrow +\mathbb{N}$ et $\underline{x} \in \mathbb{N}^k$, alors $\mu +g(\underline{x})$ est le plus petit $z$ tel que $g(z,\underline{x}) = +0$ et $g(i,\underline{x})\downarrow$ pour $0\leq i<z$, s'il existe. \bigskip @@ -1095,6 +1099,12 @@ Concrètement, penser à $\mu g$ comme la fonction \itempoint Ceci permet toute sorte de \alert{recherche non bornée}. +\bigskip + +\itempoint L'opérateur $\mu$ associe à une fonction $g\colon +\mathbb{N}^{k+1} \dasharrow \mathbb{N}$ une fonction $\mu g\colon +\mathbb{N}^k \dasharrow \mathbb{N}$. + \end{frame} % \begin{frame} @@ -1125,7 +1135,7 @@ f(\underline{x},z+1) &= h(\underline{x},f(\underline{x},z),z) \item est stable par l'opérateur $\mu$ : si $g\colon \mathbb{N}^{k+1} \dasharrow \mathbb{N}$ est récursive, alors $\mu g\colon \mathbb{N}^k \dasharrow \mathbb{N}$ est récursive - (\alert{$\leftarrow$ nouveau !}). + \textcolor{teal}{($\leftarrow$ nouveau !)}. \end{itemize} \medskip @@ -1149,8 +1159,8 @@ Cette fois le langage \alert{permet les boucles non bornées} ! \itempoint Pour (certains) entiers $e \in \mathbb{N}$, on va définir $\varphi_e^{(k)}\colon \mathbb{N}^k \dasharrow \mathbb{N}$ générale -récursive, la fonction récursive \alert{codée} par $e$ ou ayant $e$ -comme \textbf{code} (source). +récursive, celle \alert{codée} par $e$ ou ayant $e$ comme +\textbf{code} (source) / « programme ». \bigskip @@ -1182,7 +1192,7 @@ sens informatique). \itempoint On va ensuite se demander si $(e,\underline{x}) \mapsto \varphi_e^{(k)}(\underline{x})$ est \alert{elle-même récursive} -(divulgâchis : \alert{oui}, contrairement au cas p.r.). +(divulgâchis : \alert{oui}, \alert{contrairement} au cas p.r.). \par} @@ -1221,7 +1231,8 @@ induction suivant la déf\textsuperscript{n} de $\mathbf{R}$ \bigskip \itempoint Alors $f\colon \mathbb{N}^k \dasharrow \mathbb{N}$ est -récursive \alert{ssi} $\exists e \in\mathbb{N}.\,(f = \varphi_e^{(k)})$. +récursive \alert{ssi} $\exists e \in\mathbb{N}.\,(f = \varphi_e^{(k)})$ +par définition. \end{frame} % @@ -1282,7 +1293,7 @@ entiers naturels) qui « atteste » que $\varphi_e^{(k)}(\underline{x}) \begin{itemize} \item La racine est étiquetée « $\varphi_e^{(k)}(\underline{x}) = y$ » - ou plutôt « $\dbllangle e, \dbllangle \underline{x}\dblrangle, + codé disons « $\dbllangle e, \dbllangle \underline{x}\dblrangle, y\dblrangle$ ». \item Le sous-arbre porté par chaque fils de la racine est lui-même un arbre de calcul pour une sous-expression utilisée dans le calcul de @@ -1293,14 +1304,14 @@ entiers naturels) qui « atteste » que $\varphi_e^{(k)}(\underline{x}) $h(g_1(\underline{x}),\ldots,g_\ell(\underline{x}))$, les fils portent des arbres de calcul attestant $g_1(\underline{x})=v_1,\ldots,g_\ell(\underline{x})=v_\ell$ et - $h(\underline{v})=y$. + $h(\underline{v})=y$ (donc $\ell+1$ fils). \item Pour la récursion primitive $f(\underline{x},z)$, on a soit un - seul fils arbre de calcul attestant $g(\underline{x})=y$ lorsque - $z=0$ soit deux fils arbres de calcul attestant - $f(\underline{x},z')=v$ et $h(\underline{x},v,z')=y$ lorsque - $z=z'+1$. + seul fils attestant $g(\underline{x})=y$ lorsque $z=0$ soit deux + fils attestant $f(\underline{x},z')=v$ et $h(\underline{x},v,z')=y$ + lorsque $z=z'+1$ (donc $1$ ou $2$ fils). \item Pour $f = \mu g$, on a des fils attestant - $g(0,\underline{x})=v_0,\ldots,g(y,\underline{x})=v_y$ où $v_y=0$. + $g(0,\underline{x})=v_0,\ldots,g(y,\underline{x})=v_y$ où $v_i>0$ si + $0\leq i<y$ et $v_y=0$ (donc $y+1$ fils). \end{itemize} \medskip @@ -1323,7 +1334,7 @@ Formellement : c\dblrangle$ ou $\dbllangle 2\dblrangle$, elle n'a pas de fils, et $y$ vaut resp\textsuperscript{t} $x_i$, $c$ ou $x+1$, \item soit $e = \dbllangle 3, k, d, c_1,\ldots,c_\ell\dblrangle$ et - les fils portent des arbres de calculs attestant + les $\ell+1$ fils portent des arbres de calculs attestant $\varphi_{c_1}^{(k)}(\underline{x})=v_1$, ..., $\varphi_{c_\ell}^{(k)}(\underline{x})=v_\ell$ et $\varphi_d^{(\ell)}(\underline{v})=y$. @@ -1331,11 +1342,11 @@ Formellement : \begin{itemize}\footnotesize \item soit $x_k = 0$ et l'unique fils porte arbre de calcul attestant $\varphi_{c}^{(k')}(x_1,\ldots,x_{k'})=y$, -\item soit $x_k = z+1$ et les deus fils portent arbres de calcul +\item soit $x_k = z+1$ et les deux fils portent arbres de calcul attestant $\varphi_{e}^{(k'+1)}(x_1,\ldots,x_{k'},z)=v$ et $\varphi_{d}^{(k'+2)}(x_1,\ldots,x_{k'},v,z)=y$. \end{itemize} -\item soit $e = \dbllangle 5, k, c\dblrangle$ et les fils portent des +\item soit $e = \dbllangle 5, k, c\dblrangle$ et les $y+1$ fils portent des arbres de calcul attestant $\varphi_{c}^{(k+1)}(0,x_1,\ldots,x_k)=v_0$, ..., $\varphi_{c}^{(k+1)}(y,x_1,\ldots,x_k)=v_y$ où $v_y=0$ et $v_0,\ldots,v_{y-1} > 0$. @@ -1347,7 +1358,7 @@ $\operatorname{code}(\mathscr{T}) := \dbllangle n, \operatorname{code}(\mathscr{T}_1), \ldots, \operatorname{code}(\mathscr{T}_s)\dblrangle$ où $n$ est l'étiquette de la racine et $\mathscr{T}_1,\ldots,\mathscr{T}_s$ les codes des -sous-arbres portés par les fils de celle-ci. +sous-arbres portés par les $s$ fils de celle-ci. \end{frame} % @@ -1380,7 +1391,8 @@ $\varphi_e^{(k)}(\underline{x})$ en fonction de $e,\underline{x}$ : La boucle non-bornée est précisément ce que permet $\mu$. Tout le reste est p.r. -$\Rightarrow$ Ceci montre l'existence de $u$. +$\Rightarrow$ Ceci montre l'existence de $u$ (code de l'algorithme +décrit ci-dessus). \bigskip @@ -1447,13 +1459,14 @@ Exactement comme la version p.r. : \bigskip -Noter que $s_{m,n}$ est \alert{p.r.} même si on s'intéresse ici aux -fonctions générales récursives. +Noter que $s_{m,n}$ est \alert{primitive récursive} même si on +s'intéresse ici aux fonctions générales récursives. \medskip -Les manipulations de programmes sont typiquement p.r. (même si les -programmes manipulés sont des fonctions générales récursives). +Les manipulations de programmes sont \textcolor{blue}{typiquement + p.r.} (même si les programmes manipulés sont des fonctions générales +récursives). \end{frame} % @@ -1525,18 +1538,17 @@ Exactement comme la version p.r. : h(e,\underline{x}) \] Plus précisément, il existe $b \colon \mathbb{N}^2 \to \mathbb{N}$ -p.r. telle que +p.r. telle que $e := b(k,d)$ vérifie \[ -(\forall\underline{x})\quad \varphi^{(k)}_e(\underline{x}) = \varphi^{(k+1)}_d(e,\underline{x}) -\text{~si~}e := b(k,d) +(\forall d)\,(\forall\underline{x})\quad \varphi^{(k)}_e(\underline{x}) = \varphi^{(k+1)}_d(e,\underline{x}) \] \bigskip -\underline{Même preuve :} soit $s := s_{m,1}$ donné par le théorème +\underline{Même preuve :} soit $s := s_{1,k}$ donné par le théorème s-m-n. La fonction $(t,\underline{x}) \mapsto h(s(t,t),\underline{x})$ est p.r., disons $= -\varphi_c^{(k+1)}(\underline{x})$. Alors +\varphi_c^{(k+1)}(t,\underline{x})$. Alors \[ \varphi_{s(c,c)}^{(k)}(\underline{x}) = \varphi_{c}^{(k+1)}(c, \underline{x}) @@ -1560,8 +1572,8 @@ Reformulation du théorème de récursion utilisant l'universalité : \smallskip \itempoint\textbf{Théorème} (Kleene-Rogers) : si $F \colon \mathbb{N} -\to \mathbb{N}$ est récursive \emph{totale} et $k\in\mathbb{N}$, il -existe $e$ tel que +\dasharrow \mathbb{N}$ est récursive et $k\in\mathbb{N}$, il existe +$e$ tel que \[ \varphi_e^{(k)} = \varphi_{F(e)}^{(k)} \] @@ -1576,6 +1588,13 @@ théorème de récursion, il existe $e$ tel que $\varphi^{(k)}_e(\underline{x}) = h(e,\underline{x}) = \varphi_{F(e)}^{(k)}(\underline{x})$.\qed +\bigskip + +\textcolor{blue}{\textbf{Moralité :}} quelle que soit la +transformation $F$ calculable effectuée sur le source d'un programme, +il y a un programme $e$ qui fait la même chose que son +transformé $F(e)$. + \end{frame} % \begin{frame} @@ -1642,6 +1661,11 @@ return interpret(self, n-1) + interpret(self, n-2);\\ \textbf{Défi :} trouver explicitement un $e$ tel que $\varphi^{(3)}_e$ soit la fonction d'Ackermann. +\smallskip + +(La fonction d'Ackermann a été définie par des appels récursifs donc +elle est bien censée être calculable.) + \end{frame} % \begin{frame} @@ -1665,6 +1689,13 @@ Cette question est-elle \alert{algorithmique} ? \textbf{Réponse} de Turing : \alert{non}. +\bigskip + +\itempoint \textcolor{blue}{Intuition de la preuve :} supposons que +j'aie un moyen algorithmique pour savoir si un algorithme termine ou +pas, je peux lui demander ce que « je » vais faire (astuce de +Quine !), et faire le contraire, ce qui conduit à un paradoxe. + \end{frame} % \begin{frame} @@ -1691,22 +1722,20 @@ v\colon (e,x) \mapsto \left\{ est générale récursive (tester is $h(e,x)=0$, si oui renvoyer $42$, sinon faire une boucle infinie, p.ex. $\mu(x\mapsto 1)$). +\medskip + Par le théorème de récursion de Kleene, il existe $e$ tel que $\varphi^{(1)}_e(x) = v(e,x)$. +\medskip + Si $\varphi^{(1)}_e(x)\downarrow$ alors $h(e,x) = 1$ donc -$v(e,x)\uparrow$ donc $\varphi^{(1)}_e(x)\uparrow$, une contradiction. +$v(e,x)\uparrow$ donc $\varphi^{(1)}_e(x)\uparrow$, contradiction. + Si $\varphi^{(1)}_e(x)\uparrow$ alors $h(e,x) = 0$ donc -$v(e,x)\downarrow$ donc $\varphi^{(1)}_e(x)\downarrow$, une +$v(e,x)\downarrow$ donc $\varphi^{(1)}_e(x)\downarrow$, contradiction.\qed -\bigskip - -\itempoint Intuition de la preuve : supposons que j'aie un moyen -algorithmique $h$ pour savoir si un algorithme termine ou pas, je peux -lui demander ce que « je » vais faire (astuce de Quine), et faire le -contraire, ce qui conduit à un paradoxe. - \end{frame} % \begin{frame} @@ -1744,9 +1773,9 @@ une fonction qui diffère en tout point de la diagonale $c \mapsto \medskip -Pour les fonctions p.r. (terminent toujours !), le même argument -diagonal donnait l'inexistence d'un programme universel -(transp. \ref{primitive-recursive-no-universality}). +{\footnotesize Pour les fonctions p.r. (qui terminent toujours !), le + même argument diagonal donnait l'inexistence d'un programme + universel (transp. \ref{primitive-recursive-no-universality}).\par} \end{frame} % @@ -1892,7 +1921,7 @@ finie ou infinie $C^{(0)},C^{(1)},C^{(2)},\ldots$, où s'arrête}, que $C^{(n)}$ est la \textbf{configuration finale}, et que l'exécution a duré $n$ \textbf{étapes}, \item sinon, $C^{(n+1)}$ est la configuration suivante (définie - avant). + transp. précédent). \end{itemize} \bigskip @@ -1904,6 +1933,7 @@ tombe dans l'état $0$. \end{frame} % \begin{frame} +\label{simulation-of-turing-machines-by-recursive-functions} \frametitle{Simulation des machines de Turing par les fonctions récursives} \itempoint On peut coder un programme et/ou une configuration sous @@ -1962,8 +1992,9 @@ j\leq 1+x_1+x_2$, etc., \item si $f(x_1,\ldots,x_k){\downarrow} = y$, la machine s'arrête avec la tête à l'emplacement $0$ (le même qu'au départ), le ruban $\beta(j)$ non modifié pour $j<0$, et -\item les symboles $\beta(j)$ pour $j\geq 0$ du ruban final forment - le mot $0 1^y 0$ (suivi d'une inifinité de $0$). +\item les symboles $\beta(j)$ pour $j\geq 0$ du ruban final forment le + mot $0 1^y 0$ (suivi d'une infinité de $0$) {\footnotesize (« codage + unaire » de $y$)}. \end{itemize} \end{frame} @@ -1987,8 +2018,8 @@ primitive, $\mu$-récursion). \bigskip \itempoint Les conventions faites, notamment le fait d'ignorer et de -ne pas modifier $\beta(j)$ pour $j<0$, permettent à l'induction de -fonctionner. +ne pas modifier $\beta(j)$ pour $j<0$, permettent à l'induction dans +la preuve de fonctionner. \smallskip @@ -2007,7 +2038,7 @@ fonctionner. \itempoint Toute fonction générale récursive $\mathbb{N}^k \dasharrow \mathbb{N}$ est calculable par machine de Turing (sous les conventions -données). +données) : transp. précédent. \bigskip @@ -2015,7 +2046,8 @@ données). \mathbb{N}$ calculable par machine de Turing sous ces conventions est générale récursive, car les fonctions récursives peuvent simuler les machines de Turing, calculer une configuration initiale convenable, et -décoder la configuration finale. +décoder la configuration finale +(cf. transp. \ref{simulation-of-turing-machines-by-recursive-functions}). \bigskip @@ -2110,11 +2142,53 @@ jour ». \end{frame} % \begin{frame} +\label{undecidability-halting-problem-turing-machines-pristine-start} +\frametitle{Indécidabilité du problème de l'arrêt (départ bande vierge)} + +On ne peut même pas tester algorithmiquement si une machine de Turing +s'arrête à partir d'une bande vierge : + +\smallskip + +\itempoint\textbf{Indécidabilité du problème de l'arrêt :} la fonction +qui à $M$ associe $1$ si la machine de Turing s'arrête en partant de +la configuration vierge $C_0$ (c'est-à-dire celle où $\beta = 0$, état +initial $1$), et $0$ sinon, \alert{n'est pas calculable}. + +\medskip + +\underline{Preuve :} Supposons par l'absurde qu'on puisse tester +algorithmiquement si une machine de Turing s'arrête à partir d'une +configuration vierge. On va montrer qu'on peut tester si une machine +de Turing $M$ s'arrête à partir de $C$ quelconque. + +\smallskip + +Données $M$ et $C$, on peut algorithmiquement calculer une machine $N$ +qui « prépare » $C$ à partir de la configuration vierge $C_0$, donc +une machine $M^*$ qui exécute successivement $N$ puis $M$ +\textcolor{teal}{($\leftarrow$ ceci est un théorème s-m-n)}. + +\smallskip + +Ainsi $M^*$ (calculé algorithmiquement) termine sur $C_0$ ssi $M$ +termine sur $C$. + +\smallskip + +Donc tester la terminaison de $M^*$ permettrait de tester celle de +$M$ sur $C$, ce qui n'est pas possible +\textcolor{teal}{($\leftarrow$ ceci est une preuve « par + réduction »)}.\qed + +\end{frame} +% +\begin{frame} \frametitle{Le castor affairé} \itempoint La fonction \textbf{castor affairé} associe à $m$ le nombre maximal $B(m)$ d'étapes d'exécution d'une machine de Turing à $\leq m$ -états \alert{qui termine} (à partir d'une bande vierge : $\beta = 0$). +états \alert{qui termine} (à partir de la configuration vierge $C_0$). \medskip @@ -2128,28 +2202,20 @@ maximal $B(m)$ d'étapes d'exécution d'une machine de Turing à $\leq m$ \medskip -{\footnotesize - \underline{Preuve :} supposons au contraire $\forall m\in\mathbb{N}.\; (B(m) \leq f(m))$ avec $f\colon\mathbb{N}\to\mathbb{N}$ calculable. -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$ \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), -\item si elle a terminé, $M^*$ termine sur $C_0$, donc $M$ sur $C$, et - on renvoie « oui » ; sinon, elle ne termine jamais par définition de +Donnée une machine de Turing $M$, on peut alors algorithmiquement +décider si $M$ s'arrête à partir de $C_0$ : +\begin{itemize} +\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), +\item si elle a terminé en temps imparti, $M$ termine sur $C_0$, et on + renvoie « oui » ; sinon, elle ne termine jamais par définition de $B(m)$, on renvoie « non ». \end{itemize} Ceci est impossible donc $f$ n'est pas calculable.\qed -\par} - \end{frame} % \begin{frame} @@ -2176,19 +2242,20 @@ calculable : \underline{Preuve :} soit $f\colon\mathbb{N}\to\mathbb{N}$ calculable. 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 +$\gamma$ croissante). Pour $r \in \mathbb{N}$, on considère la +machine de Turing $M_r$ qui \begin{itemize} -\item calcule $\gamma(r+1)$ puis $f(0) + f(1) + \cdots + +\item prépare $r$, calcule $\gamma(r+1)$ puis $f(0) + f(1) + \cdots + f(\gamma(r+1)) + 1$, \item attend ce nombre-là d'étapes, et termine. \end{itemize} -Par le théorème s-m-n, le nombre d'états de $M_r$ est une fonction -p.r. $b(r)$ de $r$ (même $b(r) = r + \mathrm{const}$ convient). Pour -$r\geq r_0$ on a $b(r) \leq \gamma(r)$. Soit $m_0 = \gamma(r_0)$. Si -$m \geq m_0$, soit $r\geq r_0$ tel que $\gamma(r) \leq m \leq -\gamma(r+1)$. Alors $M_r$ calcule $\cdots+f(m)+\cdots+1$, donc attend -$>f(m)$ étapes. Donc $B(b(r)) > f(m)$. Mais $b(r) \leq \gamma(r) -\leq m$ donc $B(m) > f(m)$.\qed +Le nombre d'états de $M_r$ est une fonction p.r. $b(r)$ de $r$ (même +$b(r) = r + \mathrm{const}$ convient). Pour $r\geq r_0$ on a $b(r) +\leq \gamma(r)$. Soit $m_0 = \gamma(r_0)$. Si $m \geq m_0$, soit +$r\geq r_0$ tel que $\gamma(r) \leq m \leq \gamma(r+1)$. Alors $M_r$ +calcule $\cdots+f(m)+\cdots+1$, donc attend $>f(m)$ étapes. Donc +$B(b(r)) > f(m)$. Mais $b(r) \leq \gamma(r) \leq m$ donc $B(m) > +f(m)$.\qed \par} @@ -2430,7 +2497,9 @@ $(e,x)$, on peut exécuter $\varphi_e(x)$, et, s'il termine, renvoyer \item $\{e\in \mathbb{N} : \varphi_e(e)\downarrow$ n'est pas décidable (preuve dans transp. \ref{undecidability-halting-problem-redux}) \item $\{e\in \mathbb{N} : \varphi_e(0)\downarrow$ n'est pas décidable - (théorème s-m-n : $\varphi_e(x) = \varphi_{s(e,x)}(0)$ avec $s$ p.r.) + (théorème s-m-n : $\varphi_e(x) = \varphi_{s(e,x)}(0)$ avec $s$ + p.r. ; + cf. transp. \ref{undecidability-halting-problem-turing-machines-pristine-start}) \end{itemize} \par} @@ -2588,7 +2657,7 @@ Alors $h \colon \mathbb{N}^2 \dasharrow \mathbb{N}$ est calculable par hypothèse (on peut décider si $e\in \Phi^{-1}(F)$). Par le théorème de récursion de Kleene (transp. \ref{kleene-recursion-theorem}), il existe $e$ tel que -\[\Phi(e) := \varphi^{(1)}_e(x) = h(e,x)\] +\[\varphi^{(1)}_e(x) = h(e,x)\] Si $e \in \Phi^{-1}(F)$ alors $h(e,x) = g(x)$ pour tout $x$, donc $\Phi(e) = g$ donc $e \not\in \Phi^{-1}(F)$, une contradiction. Si $e @@ -2630,7 +2699,7 @@ intuitivement, \centerline{« $A$ se réduit à $B$ »} -\centerline{$\Longleftrightarrow$} +\centerline{signifie} \centerline{« si $B$ est décidable alors $A$ est décidable »} |