Slightly more about Turing machines.

1 files changed, 107 insertions, 0 deletions

diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex
index 7113309..922c76a 100644
--- a/transp-inf110-01-calc.tex
+++ b/transp-inf110-01-calc.tex
@@ -1528,6 +1528,39 @@ diagonal donnait l'inexistence d'un programme universel
 
 \end{frame}
 %
+\begin{frame}
+\frametitle{Comparaison fonctions primitives récursives et générales récursives}
+
+\textcolor{purple}{Récapitulation :}
+
+\medskip
+
+\itempoint Les fonctions p.r. sont totales ; les générales récursives
+sont possiblement partielles.
+
+\medskip
+
+\itempoint Les fonctions p.r. sont un langage limité (pas de boucle
+non bornées a priori) ; les générales récursives coïncideront avec les
+fonctions « calculables » (équivalence avec machines de Turing et
+$\lambda$-calcul à voir).
+
+\medskip
+
+\itempoint Les fonctions p.r. ne permettent pas d'interpréter les
+fonctions p.r. ; les générales récursives peuvent s'interpréter
+elles-mêmes (universalité) et donc réaliser n'importe quelle sorte
+d'appels récursifs.
+
+\medskip
+
+\itempoint Le problème de l'arrêt pour les fonctions p.r. est trivial
+(elles sont totales !) ; pour les fonctions générales récursives, il
+est indécidable (= pas calculable par une fonction générale
+récursive).
+
+\end{frame}
+%
 \section{Machines de Turing}
 \begin{frame}
 \frametitle{Machines de Turing : explication informelle}
@@ -1784,4 +1817,78 @@ existe des fonctions p.r. :
 
 \end{frame}
 %
+\begin{frame}
+\frametitle{Machines de Turing : variations}
+
+On a choisi ici une notion de machine de Turing assez restreinte
+($1$ bande, $2$ symboles de bande).  Il existe toutes sortes de
+variations :
+\begin{itemize}
+\item machines à plusieurs bandes (mais en onmbre fini ; le programme
+  choisit en fonction du symbole lu sur chaque bande, et écrit et
+  déplace chaque tête indépendamment), voire à plusieurs têtes par
+  bande, parfois avec des bandes en lecture seule (pour les entrées),
+  ou en écriture seule (pour les sorties),
+\item autres symboles que $0$ et $1$ (mais en nombre fini),
+\item machine non-déterministe (plusieurs instructions possibles dans
+  une configuration donnée ; la machine termine si au moins l'un des
+  chemins d'exécution termine).
+\end{itemize}
+
+\bigskip
+
+Du point de vue \alert{calculabilité}, ces modifications ne rendent
+pas la machine plus puissante, et, sauf, cas dégénérés (p.ex., un seul
+symbole sur le ruban !) elles ne la rendent pas moins puissante non
+plus.  Ceci confirme la robustesse du modèle de Church-Turing.
+
+\smallskip
+
+{\footnotesize Pour la \alert{complexité}, en revanche, c'est une
+  autre affaire.\par}
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Machines de Turing : reprise de résultats déjà vus}
+
+\itempoint\textbf{Universalité :} pour un codage raisonnable, il
+existe une machine de Turing « universelle » qui prend en entrée sur
+sa bande le programme d'une autre machine de Turing $M$, et une
+configuration initiale $C$ pour celle-ci, et qui simule l'exécution de
+$M$ sur $C$ (notamment, elle s'arrête ssi $M$ s'arrête).
+
+\bigskip
+
+\itempoint\textbf{Forme normale :} 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 après $n$ étapes
+d'exécution, est p.r., et en particulier, calculable par une machine
+de Turing.
+
+\smallskip
+
+$\Rightarrow$ En particulier, on peut tester algorithmiquement si une
+machine de Turing donnée, depuis une configuration initiale donnée,
+s'arrête \emph{en moins de $n$ étapes}.
+
+\bigskip
+
+\itempoint\textbf{Indécidabilité du problème de l'arrêt :} la fonction
+qui à $(M,C)$ associe $1$ si la machine de Turing s'arrête en partant
+de la configuration initiale $C$, et $0$ sinon, \alert{n'est pas
+  calculable}.
+
+\smallskip
+
+$\Rightarrow$ On ne peut tester algorithmiquement si une machine de
+Turing donnée, depuis une configuration initiale donnée, s'arrête « un
+jour ».
+
+\end{frame}
+%
+% Add somewhere:
+% - busy beaver
+% - "Turing tarpit"
+%
 \end{document}