Turing machines and their equivalence with recursive functions.

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}