diff options
author | David A. Madore <david+git@madore.org> | 2023-10-18 19:32:33 +0200 |
---|---|---|
committer | David A. Madore <david+git@madore.org> | 2023-10-18 19:32:33 +0200 |
commit | 801188fd18f5c06eb0c44f887d15e3eb8e860369 (patch) | |
tree | c93cef3e8dfd5b9c4cd755399eda7a3728a905ec | |
parent | b888ffb8f30b03b93763ba8490d27dac09a13e44 (diff) | |
download | inf110-lfi-801188fd18f5c06eb0c44f887d15e3eb8e860369.tar.gz inf110-lfi-801188fd18f5c06eb0c44f887d15e3eb8e860369.tar.bz2 inf110-lfi-801188fd18f5c06eb0c44f887d15e3eb8e860369.zip |
Slightly more about Turing machines.
-rw-r--r-- | transp-inf110-01-calc.tex | 107 |
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} |