diff options
| -rw-r--r-- | transp-inf110-01-calc.tex | 266 |
1 files changed, 261 insertions, 5 deletions
diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex index a10d571..7113309 100644 --- a/transp-inf110-01-calc.tex +++ b/transp-inf110-01-calc.tex @@ -604,7 +604,7 @@ En anticipant sur la notion de machine de Turing : \itempoint La fonction $(M,C) \mapsto C'$ qui à une machine de Turing $M$ et une configuration (= ruban+état) $C$ de $M$ associe la -configuration atteinte après $1$ étape d'exécution, \textbf{est p.r.} +configuration suivante \textbf{est p.r.} \medskip @@ -802,7 +802,7 @@ avec le code source du programme \alert{tout entier}. \bigskip -\textbf{Moralité :} \alert{on peut toujours donner aux programmes +\textcolor{blue}{\textbf{Moralité :}} \alert{on peut toujours donner aux programmes accès à leur code source}, même si ce n'est pas prévu par le langage. @@ -842,7 +842,7 @@ sont p.r.\qed \bigskip -\textbf{Moralité :} \alert{on peut donner aux programmes accès à leur +\textcolor{blue}{\textbf{Moralité :}} \alert{on peut donner aux programmes accès à leur propre numéro} (= « code source »), cela ne change rien. \end{frame} @@ -868,7 +868,7 @@ contredit $u(e,x) = \psi^{(1)}_e(x)$.\qed \medskip -\textbf{Moralité :} \alert{un interpréteur du langage p.r. ne peut pas +\textcolor{blue}{\textbf{Moralité :}} \alert{un interpréteur du langage p.r. ne peut pas être p.r.} (preuve : on peut interpréter l'interpréteur s'interprétant lui-même, en ajoutant un au résultat, ce qui donne un paradoxe ; c'est un argument diagonal de Cantor). @@ -1328,7 +1328,7 @@ sont p.r.\qed \bigskip -\textbf{Moralité :} \alert{on peut donner aux programmes accès à leur +\textcolor{blue}{\textbf{Moralité :}} \alert{on peut donner aux programmes accès à leur propre numéro} (= « code source »), cela ne change rien. \end{frame} @@ -1528,4 +1528,260 @@ diagonal donnait l'inexistence d'un programme universel \end{frame} % +\section{Machines de Turing} +\begin{frame} +\frametitle{Machines de Turing : explication informelle} + +La \textbf{machine de Turing} est une modélisation d'un ordinateur +extrêmement simple, réalisant des calculs indiscutablement finitistes. + +\medskip + +C'est une sorte d'automate doté d'un \textbf{état} interne pouvant +prendre un nombre fini de valeurs, et d'une mémoire illimitée sous +forme de \textbf{bande} linéaire divisée en cellules (indéfiniment +réécrivibles), chaque cellule pouvant contenir un \textbf{symbole}. + +\medskip + +La machine peut observer, outre son état interne, une unique case de +la bande, là où se trouve sa \textbf{tête de lecture/écriture}. + +\medskip + +Le \textbf{programme} de la machine indique, pour chaque combinaison +de l'état internet et du symbole lu par la tête : +\begin{itemize} +\item dans quel état passer, +\item quel symbole écrire à la place de la tête, +\item la direction dans laquelle déplacer la tête (gauche ou droite). +\end{itemize} + +\medskip + +La machine suit son programme jusqu'à tomber dans un état spécial $0$ +(« arrêt »). + +\end{frame} +% +\begin{frame} +\frametitle{Machines de Turing : définition} + +Une \textbf{machine de Turing} (déterministe) à ($1$ bande, +$2$ symboles et) $m\geq 2$ états est la donnée de : +\begin{itemize} +\item un ensemble fini $Q$ de cardinal $m$ d'\textbf{états}, qu'on + identifiera à $\{0,\ldots,m-1\}$, +\item un ensemble $\Sigma$ de (ici) $2$ \textbf{symboles de bande} + qu'on identifiera à $\{0,1\}$, +\item une fonction +\[ +\delta \colon (Q\setminus\{0\}) \times \Sigma \to Q \times \Sigma \times \{\texttt{L},\texttt{R}\} +\] +appelé \textbf{programme} de la machine. +\end{itemize} + +{\footnotesize (Il y a donc $(4m)^{2(m-1)}$ machines à $m$ états.)\par} + +\bigskip + +Une \textbf{configuration} d'une telle machine est la donnée de : +\begin{itemize} +\item un élément $q \in Q$ appelé l'\textbf{état courant}, +\item une fonction $\beta\colon \mathbb{Z} \to \Sigma$ ne prenant + qu'\alert{un nombre fini} de valeurs $\neq 0$, appelée la + \textbf{bande}, +\item un entier $i \in \mathbb{Z}$ appelé la \textbf{position de la + tête} sur la bande. +\end{itemize} + +\end{frame} +% +\begin{frame} +\frametitle{Machines de Turing : exécution d'une étape} + +Si $(q,\beta,i)$ est une configuration de la machine de Turing où +$q\neq 0$, et $\delta$ le programme, la \textbf{configuration + suivante} est $(q',\beta',i')$ où : +\begin{itemize} +\item $(q',y,d) = \delta(q,\beta(i))$ est l'\textbf{instruction + exécutée}, +\item $q'$ est le \textbf{nouvel état}, +\item $i' = i-1$ si $d=\texttt{L}$ et $i' = i+1$ si $d=\texttt{R}$, +\item $\beta'(j) = \beta(j)$ pour $j\neq i$ tandis que $\beta'(i) = y$. +\end{itemize} + +\bigskip + +\emph{En clair :} le programme indique, pour chaque configuration d'un +état $\neq 0$ et d'un symbole $x = \beta(i)$ lu sur la bande : +\begin{itemize} +\item le nouvel état $q'$ dans lequel passer, +\item le symbole $y$ à écrire à la place de $x$ à l'emplacement $i$ de + la bande, +\item la direction dans laquelle déplacer la tête (gauche ou droite). +\end{itemize} + +\end{frame} +% +\begin{frame} +\frametitle{Machines de Turing : exécution complète} + +\itempoint Si $C = (q,\beta,i)$ est une configuration d'une machine de +Turing, la \textbf{trace d'exécution} à partir de $C$ est la suite +finie ou infinie $C^{(0)},C^{(1)},C^{(2)},\ldots$, où +\begin{itemize} +\item $C^{(0)} = C$ est la configuration donnée (configuration initiale), +\item si $C^{(n)} = (q^{(n)},\beta^{(n)},i^{(n)})$ avec $q^{(n)}=0$ + alors la suite s'arrête ici, on dit que \textbf{la machine + 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). +\end{itemize} + +\bigskip + +\emph{En clair :} la machine continue à exécuter des instructions tant +qu'elle n'est pas tombée dans l'état $0$. Elle s'arrête quand elle +tombe dans l'état $0$. + +\end{frame} +% +\begin{frame} +\frametitle{Simulation des machines de Turing par les fonctions récursives} + +\itempoint On peut coder un programme et/ou une configuration sous +forme d'entiers naturels. + +{\footnotesize Le ruban a un nombre \alert{fini} de symboles $\neq 0$, + donc on peut le coder par la liste de leurs positions comptées, + disons, à partir du symbole $\neq 0$ le plus à gauche.\par} + +\bigskip + +\itempoint La fonction $(M,C) \mapsto C'$ qui à une machine de Turing +$M$ et une configuration $C$ de $M$ associe la configuration suivante +\textbf{est p.r.} + +\medskip + +\itempoint Conséquence : la fonction $(n,M,C) \mapsto C^{(n)}$ qui à +$n\in\mathbb{N}$ et une machine de Turing $M$ et une configuration $C$ +de $M$ associe la configuration atteinte après $n$ étapes d'exécution, +\textbf{est p.r.} + +\medskip + +\itempoint La fonction qui à $(M,C)$ associe la configuration finale +(et/ou le nombre d'étapes d'exécution) \alert{si la machine s'arrête}, +et $\uparrow$ (non définie) si elle ne s'arrête pas, est +\textbf{générale récursive}. + +\bigskip + +\textcolor{blue}{\textbf{Moralité :}} les fonctions récursives peuvent +simuler les machines de Turing. + +\end{frame} +% +\begin{frame} +\frametitle{Calculs sur machines de Turing : une convention} + +On dira qu'une fonction $f\colon \mathbb{N}^k \dasharrow \mathbb{N}$ +est \textbf{calculable par machine de Turing} lorsqu'il existe une +machine de Turing qui, pour tous $x_1,\ldots,x_k$ : +\begin{itemize} +\item part de la configuration initiale suivante : l'état est $1$, les + symboles $\beta(j)$ du ruban pour $j<0$ sont arbitraires (tous $0$ + sauf un nombre fini), la tête est à l'emplacement $0$, +\item les symboles $\beta(j)$ pour $j\geq 0$ du ruban initial forment + le mot suivant : +\[ +0 1^{x_1} 0 1^{x_2} 0 \cdots 0 1^{x_k} 0 +\] +(suivi d'une infinité de $0$), c'est-à-dire $\beta(0)=0$, $\beta(j)=1$ +si $1\leq j\leq x_1$, $\beta(1+x_1)=0$, $\beta(j)=1$ si $2+x_1\leq +j\leq 1+x_1+x_2$, etc., +\item si $f(x_1,\ldots,f_k)\uparrow$, la machine ne s'arrête pas, +\item si $f(x_1,\ldots,f_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$). +\end{itemize} + +\end{frame} +% +\begin{frame} +\frametitle{Calculs par les machines de Turing des fonctions récursives} + +\itempoint On peut montrer par induction suivant la +déf\textsuperscript{n} de $\mathbf{R}$ que \alert{toute fonction + générale récursive est calculable par machine de Turing} avec les +conventions du transp. précédent. + +\bigskip + +\itempoint La démonstration est fastidieuse mais pas difficile : il +s'agit essentiellement de programmer en machine de Turing chacune des +formes de construction des fonctions générales récursives +(projections, constantes, successeur, composition, récursion +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. + +\smallskip + +{\footnotesize Par exemple, pour la composition, on va utiliser cette + propriété pour « sauvegarder » les $x_1,\ldots,x_k$ initiaux, ainsi + que les valeurs de $g_j(\underline{x})$ calculées, lorsqu'on appelle + chacune des fonctions $g_1,\ldots,g_\ell$ (à chaque fois, on les + recopie $x_1,\ldots,x_k$ à droite des valeurs à ne pas toucher, et + on appelle la machine calculant $g_j$ sur ces valeurs + recopiées).\par} + +\end{frame} +% +\begin{frame} +\frametitle{Équivalence entre machines de Turing et fonctions récursives} + +\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). + +\bigskip + +\itempoint Réciproquement, toute fonction $\mathbb{N}^k \dasharrow +\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. + +\bigskip + +\itempoint Bref, $f\colon \mathbb{N}^k \dasharrow \mathbb{N}$ est +calculable par machine de Turing \alert{ssi} elle est générale +récursive. + +\bigskip + +\itempoint De plus, cette équivalence est \alert{constructive} : il +existe des fonctions p.r. : +\begin{itemize} +\item l'une prend en entrée le numéro $e$ d'une fonction générale + récursive (et l'arité $k$) et renvoie le code d'une machine de + Turing qui calcule cette $\varphi_e^{(k)}$, +\item l'autre prend en entrée le code d'une machine de Turing qui + calcule une fonction $f$ et son arité $k$, et renvoie un numéro $e$ + de $f$ dans les fonctions générales récursives $f = + \varphi_e^{(k)}$. +\end{itemize} + +\end{frame} +% \end{document} |