\chapterimage{turing}
\chaptertext{En informatique,  tout a commencé avant  la construction du
  premier ordinateur, dans le cerveau fécond de quelques mathématiciens...}
\chapter{Machines de \textsc{Turing}}



%\section{Systèmes formels}

\section{Approche historique}

\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=3cm]{turing}
\caption{A.\bsc{Turing (1912-1954)}}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-4.6cm}
\begin{minipage}[t]{\linewidth}
Les essais de formalisation de la pensée ont commencé bien avant l'apparition des
ordinateurs  (notamment avec  \bsc{Leibniz} au  XVII\ieme siècle)  mais ont
réellement  pris leur essor avec  les travaux de  \bsc{Boole} (fin du
XIX\ieme).

La période qui va surtout influencer le monde informatique se situe pendant
l'entre-deux-guerres marquée par les travaux d'Alonzo \bsc{Church}, Alan
\bsc{Turing}, Stephen \bsc{Kleene}, Haskell \bsc{Curry} entre autres car
elle marque  les prémisses de l'informatique avant  même la construction
du  premier   ordinateur:  $\lambda$-calcul,  calculabilité,  complexité
algorithmique, équivalence entre  fonctions mécaniquement calculables et
définitions formelles des fonctions récursives.

Nous n'allons pas  voguer dans les hautes sphères de la logique
mathématique et  de l'informatique théorique mais il  est important pour
un(e)  informaticien(ne) d'aborder  ces  notions de  mécanisation de  la
pensée qui sont l'essence de sa discipline.

Nous aborderons la logique
comme un exemple de système formel  que nous étudierons plus en détail à
travers la  théorie des  langages, des grammaires  et des  automates qui
sont à la base de la construction des compilateurs.  Mais pour commencer par
le commencement, nous étudierons  brièvement l'ordinateur le plus simple
qu'on puisse imaginer:  la machine de \bsc{Turing}. Nous  ferons le lien
entre  calculabilité   et  récursivité.  
\end{minipage}

\section{Les machines de \bsc{Turing}}

\subsection{Description sommaire}


\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=3cm]{snowwhite}
%\caption{A.\bsc{Turing (1912-1954)}}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-3cm}
\begin{minipage}[t]{\linewidth}
Alan \bsc{Turing} est  le véritable homme à la pomme  (dont il a utilisé
un exemplaire pour s'empoisonner) de l'informatique
car  il en  a posé  les  fondements et  non pas  exploité les  capacités
commerciales. 

En 1936,  il présente sa \og  machine\fg{} théorique afin  de donner une
définition précise du concept d'algorithme.

Il s'agit  d'un ruban ayant un  commencement mais une  longueur infinie et
qui représente la mémoire d'un ordinateur (qui, elle, est finie...).

Le ruban  est constituée  de cases pouvant  contenir un symbole.  À tout
moment, seul un nombre fini de  cases ne sont pas blanches (ou plutôt ne
contenant pas le symbole \og  blanc\fg{}). Un pointeur identifie la case
sur laquelle la machine \og travaille\fg{} à un instant donné.

Ce  que nous  appelons un  programme est  une fonction  qui  prend comme
argument le symbole pointé et le degré d'avancement du pointeur.
\end{minipage}

Commençons par un problème simple.


\subsection{Un exemple pour découvrir}


Il faut s'imaginer une machine de \bsc{Turing} comme ceci par exemple:

\begin{center}
\begin{tikzpicture}[
      start chain=1 going right,start chain=2 going below,node distance=-0.15mm
    ]
    \node [on chain=2] {Ruban};
    \node [on chain=1] at (-1.5,-.4) {};
     \node [draw,on chain=1,scale=1.18]{\footnotesize$ \varepsilon$} ;
     \node [draw,on chain=1,scale=1.05]{\footnotesize$1$} ;
     \node [draw,on chain=1,scale=1.05]{\footnotesize$0$} ;
      \node [draw,on chain=1,scale=1.05]{\footnotesize$0$} ;
     \node [draw,on chain=1,scale=1.05]{\footnotesize$1$} ;
     \node [draw,on chain=1,scale=1.05]{\footnotesize$1$} ;
     \node [draw,on chain=1,scale=1.18]{\footnotesize$ \varepsilon$} ;
    \foreach \x in {2,...,11} {
        \x, \node [draw,on chain=1,scale=1.95] {};
    } 
    \node [name=r,on chain=1] {\ldots}; 
    \node [name=k, arrow box, draw,on chain=2,
        arrow box arrows={east:.25cm, west:0.25cm}] at (-0.15,-0.8) {};    
    \node at (2,-0.9) {Tête de lecture/écriture};
    \node [on chain=2] {};
    \node [draw,on chain=2] {État $q_i$};
    \chainin (k) [join]; % Verbindung vom Programm zum Leseschreibkopf
\end{tikzpicture}
\end{center}


Un symbole  $\varepsilon$ symbolise une case \og  blanche\fg{} et occupe
la première  case. Il est  suivi par des  0 et des  1 et une  autre case
blanche marque la fin de la chaîne.

L'ensemble des symboles $\bigl\{0,1,\varepsilon\bigr\}$ forme un \textbf{alphabet}.


Le pointeur indique la première case. Nous voudrions par exemple changer
les 0 en 1 et vice-versa puis 
remettre le pointeur dans sa position initiale.

Il est  possible d'effectuer  trois actions qui  dépendent de  l'état du
pointeur et du caractère pointé:

\begin{itemize}
\item changer l'état du pointeur;
\item changer le caractère pointé sur le ruban;
\item déplacer le pointeur d'une case vers la gauche ou vers la droite.
\end{itemize}

L'algorithme est donc:

\begin{itemize}
\item lorsque le pointeur rencontre le premier blanc, il se déplace vers
  la droite;
\item chaque fois que  le pointeur rencontre un 0 ou un  1, il le change
  en son complémentaire et se déplace vers la droite;
\item lorsqu'il rencontre  le deuxième blanc, il recule  d'une case vers
  la gauche jusqu'à ce qu'il rencontre le premier blanc.
\end{itemize}

Ceci  constitue   un  algorithme   que  nous  prendrons   l'habitude  de
représenter par \textbf{l'automate} suivant:


\begin{center}\label{autoturing}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,semithick]
\tikzstyle{every state}=[fill=white,draw=black,text=black]
\tikzstyle{accepting}=[fill=blue!20,draw=black,text=blue,accepting by arrow,double]
\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial by arrow,initial text=]
 

 \node[state,initial] (A)                    {$q_0$};
  \node[state]         (B) [ right of=A] {$q_1$};
  \node[state,accepting]         (C) [ right of=B] {$q_2$};
 
  \path (A) edge              node {$ \varepsilon$/$ \varepsilon$,D} (B)
        (B) edge [loop above] node {1/0,D} (B)
            edge [loop below] node {0/1,D} (B)
            edge              node {$ \varepsilon$/$ \varepsilon$,G} (C)
        (C) edge [loop below] node {0/0,G} (C)
            edge [loop above] node {1/1,G} (C);
\end{tikzpicture}
\end{center}


Les cercles correspondent aux différents états  de la machine: il y en a
trois.  Les  flèches  décrivent,  elles,  les actions  accomplies  par  la
machine.

La flèche entrante en $ q_0$  indique qu'il s'agit de l'état initial. Le
double cercle autour de $ q_2$ indique qu'il s'agit de l'état final.

Une  flèche allant  de $q_i$  à $  q_j$ surmontée  d'un couple  $a/b, c$
signifie que si la machine est  dans l'état $ q_i$ et qu'elle pointe sur
une case contenant $ a$ alors elle remplace $ a$ par $ b$ et bouge d'une
case  vers la direction  indiquée par  $ c$:  Gauche, Droite,  Reste sur
place.



On voit qu'un nombre fini d'instructions permet de traiter une chaîne de
longueur aussi longue que l'on veut.

\begin{recherche}
  Testez cette machine sur la chaîne $ \varepsilon 10011\varepsilon$.
\end{recherche}





\subsection{Définitions}



\begin{definition}[Machine de \bsc{Turing}]
Une  machine de  \bsc{Turing} standard  (il en  existe d'autres)  est un
triplet:

$$M=(Q,X,\f)$$

où 
\begin{itemize}

\item Q est un ensemble fini appelé \textit{alphabet d'état};
\item  X  est un
autre ensemble fini appelé \textit{alphabet de ruban};
\item  $\f$ est  une fonction  de domaine  $D\subseteq Q\times  X$  et à
  valeurs dans $Q\times X\times  \bigl\{G,R,D\bigr\}$ avec $G$, $R$, $D$
  les options du mouvement du pointeur (gauche, reste immobile, droite).
\end{itemize}

On choisira en général Q et  X de telle sorte que leur intersection soit
vide.
Quelques éléments particuliers:
\begin{itemize}
\item $q_o\in Q$ est l'\textit{état initial};
\item $Q_f\subseteq Q$ est l'\textit{ensemble des états finaux};
\item $\varepsilon\in X$ est le symbole blanc.
\end{itemize}
\end{definition}




Cela    donne,    avec    les    données   de    l'exemple    précédent,
$Q=\bigl\{q_0,q_1,q_2\bigr\}$,                  $X=\bigl\{\e,0,1\bigr\}$,
$Q_f=\bigl\{q_2\bigr\}$ et  la fonction  $ \f$ est  définie à  l'aide du
tableau suivant:


\begin{center}
             \begin{tabularx}{0.5\linewidth}{Y{2}}
	     \whline
             $ \f(q_i,x)$& $ q_0$& $ q_1$ & $ q_2$\\
             \whline
             $ \e$& $ (q_1,\e,D)$& $ (q_2,\e,G)$& \\
             \hline
             0 & & $ (q_1,1,D)$& $ (q_2,0,G)$\\
             \hline
             1 & & $ (q_1,0,D)$& $ (q_2,1,G)$\\

             \whline
             \end{tabularx}
             \end{center}


En  fait,  une  machine  de  \bsc{Turing}  agit  sur  des  \textit{mots}
construits à partir  d'un \textit{alphabet}. Un alphabet est  en fait un
ensemble fini. Définissons un peu mieux ce que peut être un mot:


\begin{definition}
Soit  X  un  alphabet.  Soit  $  \lambda$ le  mot  ne  comportant  aucun
caractère. L'ensemble $  X^*$ des mots construits avec  l'alphabet X est
défini par:
\begin{enumerate}
\item $ \lambda \in X^*$;
\item si $  a\in X$ et $ m\in  X^*$, alors le mot construit  à partir de
  $m$ en ajoutant $a$ à droite est un mot de $ X^*$;
\item $\mu$  est un élément de  $X^*$ seulement s'il peut  être obtenu à
  partir de $\lambda$ par application de l'étape 2 un nombre fini de fois.
\end{enumerate}
\end{definition}







On peut donc à l'aide de  cette définition construire un mot en ajoutant
un  par  un des  éléments  de l'alphabet.  Nous  devons  donc créer  une
fonction plus rapide pour créer des mots:

\begin{definition}[Concaténation]
Soient $m_1$ et  $m_2$ deux mots de $X^*$.  La \textbf{concaténation} de
ces deux mots est le mot $  m_1m_2\in X^*$ obtenu en écrivant $m_2$ à la
suite de $ m_1$.
\end{definition}


\subsection{Fonctions MT-calculables}


La notion  de fonction calculable  par une fonction de  \bsc{Turing} est
primordiale en informatique. Une telle fonction sera dite \textbf{MT-calculable}.


Cette notion peut  paraître assez abstraite alors mieux  vaut étudier un
exemple avant de l'affronter.

Par  exemple, nous  allons construire  une machine  de  \bsc{Turing} qui
calcule le successeur de la représentation unaire d'un entier.

\begin{definition}[Représentation unaire d'un entier]
Un nombre  entier $n\in  \bbn$ a pour  représentation unaire  $ 1^{n+1}$
c'est-à-dire  la  concaténation  de   $n+1$  symboles  de  l'alphabet  $
X=\bigl\{1\bigr\}$.

Ainsi, la représentation de  0 est 1, celle de 1 est  11, celle de 2 est
111, etc.

On notera $ \overline{n}$ la représentation de l'entier $n$.
\end{definition}


Ainsi, le successeur  de $n$ est obtenu en ajoutant un  1 à son écriture
unaire.

Décrivons une machine de \bsc{Turing} qui calcule cette fonction:
\begin{itemize}
\item la fonction successeur  $s$ est définie sur $D=\bigl\{\lambda,\e 1
  \e, \e 11 \e, \e 111\e,...\bigr\}$:  l'entrée sur le ruban est donc la
  représentation unaire du
  nombre $n$  précédée du symbole $  \e$, toutes les  autres cases étant
  occupées par des $ \e$;
\item l'alphabet de ruban est $ X=\bigl\{1,\e\bigr\}$;
\item l'alphabet d'état est $ \bigl\{q_0,q_1,q_2\bigr\}$;
\item $Q_f=\bigl\{q_2\bigr\}$;
\item la fonction $\f$ est décrite par l'automate suivant:
\end{itemize}




\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,semithick]
\tikzstyle{every state}=[fill=white,draw=black,text=black]
\tikzstyle{accepting}=[fill=blue!20,draw=black,text=blue,accepting by arrow,double]
\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial by arrow,initial text=]
 

 \node[state,initial] (A)                    {$q_0$};
  \node[state]         (B) [ right of=A] {$q_1$};
  \node[state,accepting]         (C) [ right of=B] {$q_2$};
 
  \path (A) edge              node {$ \varepsilon$/$ \varepsilon$,D} (B)
        (B) edge [loop above] node {1/1,D} (B)
            edge              node {$ \varepsilon$/1,G} (C)
        (C)  edge [loop above] node {1/1,G} (C);
\end{tikzpicture}
\end{center}


La configuration initiale est le mot $ q_0\e \overline{n}\e$.

Le  pointeur rencontre  le premier  blanc et  change donc  d'état  et se
dirige vers la droite jusqu'à rencontrer un deuxième blanc qui est alors
remplacé  par un  1. Le  pointeur change  d'état et  se déplace  vers la
gauche tant qu'il pointe sur un 1. 

La  machine s'arrête  lorsqu'elle rencontre  à  nouveau un  blanc car  $
\f(q_2,\e)$ n'est pas définie.



La configuration finale est $ q_2\e \overline{n}1\e$.

Cela  vous  aidera alors  peut-être  à  comprendre  la définition  d'une
fonction MT-calculable:

\begin{definition}[Fonction MT-calculable]
Soit  $f~: D\subseteq  X^* \to  X^*$  une fonction  et $M=(Q,X,\f)$  une
machine de \bsc{Turing}. M calcule $f$ si:
\begin{itemize}
\item  il existe  une unique  transition de  $q_0$ et  que sa  forme est
  $\f(q_0,\e)=(q_i,\e,D)$  avec $q_i\neq  q_0$ (\textit{il  faut quitter
    l'état initial à partir de $ \e$});
\item il n'existe pas de  transition de la forme $ \f(q_i,x)=(q_0,x',m)$
  avec  $i\neq   0$,  $(x,x')\in  X^2$   et  $m\in  \bigl\{G,R,D\bigr\}$
  (\textit{il ne faut pas revenir à l'état initial});
\item  il  n'existe pas  de  transition de  la  forme  $ \f(q_f,\e)$  où
  $q_f\in Q_f$ (\textit{il ne faut pas que la machine continue à
    fonctionner dans son  état final en présence d'un blanc  car il y en
    a une infinité et la machine ne s'arrêterait jamais});
\item pour tout $\mu in  D$, notons $\nu=f(\mu)$. Le calcul effectué par
  la machine M  en partant de la configuration initiale  $ q_0\e \mu \e$
  s'arrête après un nombre fini  d'étapes dans la configuration finale $
  q_f\e \nu \e$ (\textit{la machine doit calculer $ f(\mu)$});
\item  le  calcul  ne  s'arrête  jamais si  $\mu\not\in  D$  (\textit{la
    machine ne calcule $ f(\mu)$ que si ce nombre est défini}).
\end{itemize}
  
\end{definition}


Nous définirons en TD:

\begin{itemize}
\item la fonction identiquement nulle;
\item la fonction addition;
\item les fonctions projections:
$$\pi_i^{(n)}(x_1,x_2,...,x_n)=x_i,\quad 1 \leqslant i \leqslant n$$
\end{itemize}


\subsection{Fonctions récursives}


Nous avons découvert des  fonctions MT-calculables. Pour arriver jusqu'à
la thèse de \bsc{Church-Turing}, il faudrait déterminer quelles sont les
fonctions qui sont MT-calculables.

Nous allons  montrer qu'il s'agit des fonctions  récursives dont l'étude
est donc indispensable pour étudier l'algorithmique...

\subsubsection{Fonctions primitives récursives}

Les  fonctions de  base  des fonctions  primitives  récursives sont  les
fonctions précédemment étudiées:

\begin{itemize}
\item la fonction successeur $s$: $ s(x)=x+1$;
\item la fonction identiquement nulle $z$: $ z(x)=0$;
\item les fonctions projection $ \pi_i^{(n)}$.
\end{itemize}


Nous appellerons \textbf{fonction arithmétique} une fonction de $\bbn^k$
dans $\bbn$.

Les  fonctions de  base  sont MT-calculables.  Nous  admettrons que  les
fonctions arithmétiques  obtenues par composition et  récurrence le sont
aussi, en définissant ces opérations ainsi:

\begin{definition}[Composition de fonctions arithmétiques]
Soient $ g_1,g_2,...,g_k$ $k$  fonctions arithmétiques de $k$ variables
et $h$ une fonction arithmétique  de $k$ variables. Soit $f$ la fonction
définie par:

$$f(x_1,x_2,...,x_n)=h(g_1(x_1,...,x_n),...,g_k(x_1,...,x_n))$$
alors   $f$  est   appelée  la   \textbf{composition}  de   $h$   et  de
$g_1,g_2,...,g_n$ et se note:

$$f=h\circ (g_1,g_2,...,g_n)$$

\end{definition}


Par    exemple,    si    $h(x_1,x_2)=s(x_1)+s(x_2)$,   $g_1(x)=2x$    et
$g_2(x)=x^2+37$ alors:

$$f(x)=$$




\begin{definition}[Récurrence]
  Soient $g$ et $h$ des  fonctions arithmétiques totales de $n$ et $n+2$
  variables respectivement.  La fonction $f$ de  $n+1$ variables définie
  par:

  \begin{itemize}
  \item $ f(x_1,...,x_n,0)=g(x_1,...,x_n)$;
\item $ f(x_1,x_n,y+1)=h(x_1,...,x_n,y,f(x_1,x_2,...,x_n,y))$,
  \end{itemize}
 est   appelée  \textbf{récurrence   de  base   \textit{g}  et   de  pas
   \textit{h}}.

On conviendra qu'une fonction de zéro variable est constante.
\end{definition}




On peut alors définir les fonctions récursives primitives:

\begin{definition}[Fonctions récursives primitives]
Une fonction est \textbf{primitive  récursive} si elle peut être obtenue
à   partir   des   fonctions   \textit{successeur},   \textit{zéro}   et
\textit{projection} par  l'application d'un nombre  fini de compositions
et de récurrences.
\end{definition}



Par exemple, il est possible de définir l'addition de deux entiers à partir de la
fonction $s$, des projections $  \pi_1^{(1)}$ et $ \pi_3^{(3)}$ et d'une
récurrence   de   base  $g(x)=\pi_1^{(1)}(x)$   et   de  pas   $h=s\circ
\pi_3^{(3)}$:

$$
\begin{cases}
  \add(m,0)=g(m)=m\\
\add(m,n+1)=h(m,n,add(m,n))=s(add(m,n))
\end{cases}
$$


Nous  verrons  en exercice  quelques  exemples  de fonctions  primitives
récursives.

Cependant,  certaines fonctions  ne le  sont  pas comme  par exemple  la
fonction d'\textsc{Ackermann}:

$$
\begin{cases}
  A(0,y)=y+1\\
A(x+1,0)=A(x,1)\\
A(x+1,y+1)=A(x,A(x+1,y))
\end{cases}
$$

qui est cependant MT-calculable mais la preuve est hors de notre portée.



\subsubsection{La thèse de \bsc{Church-Turing}}


Si  nous  avions  un peu  plus  de  temps,  nous pourrions  définir  les
fonctions  récursives  (comme   par  exemple  les  fonctions  primitives
récursives et  la fonction d'\bsc{Ackermann}) et montrer  que toutes les
fonctions récursives sont MT-calculables.

% Mais ce qui  est plus fort c'est que  la condition nécessaire précédente
% est aussi suffisante.

% Ainsi,  une   fonction  est  calculable  s'il  existe   une  machine  de
% \textsc{Turing} pour la calculer.

% Le problème,  c'est qu'on ne sait toujours  pas définir mathématiquement
% ce qu'est la calculabilité et donc la notion d'algorithme.


Ainsi les travaux de \textsc{Turing} tendant à définir un critère de \og
calculabilité\fg{} par une machine (ou  un être humain muni d'une feuille
et d'un  crayon) rejoignent  ceux de \textsc{Church}  et \textsc{Kleene}
sur le $\lambda$-calcul ou, ce qui revient au même, les fonctions récursives
(notion introduite par \textsc{Gödel} au même moment).

C'est  un  domaine d'étude  fort  paradoxal:  techniquement réduit  (les
machines de \textsc{Turing} sont simples à décrire!), il entraîne depuis
80 ans des recherches fort ardues.


Il faut  cependant garder  en tête que  les machines  de \textsc{Turing}
sont des \og humains qui calculent\fg{} comme le formulera le philosophe
\textsc{Wittgenstein}  et évidemment  \textsc{Turing}  lui-même: \og  un
être humain  muni d'un papier, d'un  crayon, d'un ruban et  soumis à une
stricte discipline est en fait une machine universelle\fg{}.

Comme  tous  nos ordinateurs  \textit{actuels}  sont  équivalents à  des
machines de \textsc{Turing}, ils sont donc également des modèles d'êtres
humains en train d'effectuer des calculs de manière disciplinée mais non
intelligente.

Cette  notion est  fondamentale également  du côté  matériel et  du côté
logiciel. Un  ordinateur est une machine de  \textsc{Turing} car, pourvu
qu'on lui donne un bon code, il effectuera ce que vous voulez.

Le programmeur est lui-même une  machine de \textsc{Turing} s'il a écrit
son programme (et prouvé qu'il fonctionne...).

Un langage est une machine de \textsc{Turing}.

L'architecture  même  de  l'ordinateur  fonctionne  selon  ce  principe:
données  et  instructions  sont  de  même  nature  dans  la  mémoire  de
l'ordinateur   comme   nombres  et   fonctions   dans   la  machine   de
\textsc{Turing}.

Cependant, les  machines de \textsc{Turing} sont  des modèles théoriques
(ruban  infini) et  donc éloignés  du quotidien  du  programmeur. Savoir
qu'il  existe un  algorithme qui  résout notre  problème est  une chose,
connaître sa complexité en est  une autre...L'étude de la complexité des
algorithmes est un domaine de recherche en soi.

Mais  \textsc{Turing} aura  surtout  lancé le  débat sur  l'intelligence
artificielle: est-ce  qu'une machine sera  un jour capable  de raisonner
comme un cerveau humain? Il avait proposé un test: entamer un dialogue à
distance avec  une \og entité\fg{} qui  peut être un être  humain ou une
machine.  Lorsque le comportement  de la  machine sera  indiscernable de
celui de l'être humain par ce test, alors on pourra considérer la machine
aussi intelligente que l'être humain.


Cette  évolution   passera  peut-être  par   une  remise  en   cause  de
l'ordinateur électronique:  des essais d'ordinateur à ADN  sont en cours
depuis une quinzaine  d'années par exemple mais leur  base théorique est
toujours la machine de \textsc{Turing}...








Pour finir, une nouvelle citation de Donald E. \textsc{Knuth}:

\begin{quote}
  {\itshape 
Science is what we understand well  enough to explain to a computer. Art
is everything else we do.  
}
\end{quote}










%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\modeexercice % entre en mode exercice
\section{EXERCICES}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\small
\begin{listeexercices}


\subsection{Machines de \bsc{Turing}}






\begin{exercice}
  On  considère la  machine  de \bsc{Turing}  représentée par  l'automate
    ci-dessous   qui   est   dans   l'état  initial   $   q_0\varepsilon
    1111\varepsilon   111111    \varepsilon   111111   \varepsilon   111
    \varepsilon 1111 \varepsilon 111011 \varepsilon$:



{\small


\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2cm,semithick]
\tikzstyle{every state}=[fill=white,draw=black,text=black]
\tikzstyle{accepting}=[fill=blue!20,draw=black,text=blue,accepting by arrow,double]
\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial by arrow,initial text=]
 

 \node[state,initial] (A)                    {$q_0$};
  \node[state] (B) [ right of=A] {$q_1$};
\node[state] (C) [ right of=B] {$q_2$};
  \node[state,accepting]         (D) [ right of=C] {$q_3$};
 
  \path (A) edge              node {$ \varepsilon$/$ \varepsilon$,D} (B)
        (B) edge [loop above] node {1/1,D} (B)
            edge node {$ \varepsilon$/$ \varepsilon$,D} (C)
(C) edge [loop above] node {1/1,D} (B)
            edge node {$ \varepsilon$/$ \varepsilon$,D} (D)
        (D)  edge [loop above] node {1/1,D} (D);
\end{tikzpicture}
\end{center}


}

Quelle est la configuration finale de la machine?
\end{exercice}











\begin{exercice}
Quelle est la configuration finale de la machine de \bsc{Turing} décrite
par l'automate 
suivant  sachant   que  la  configuration   initiale  du  ruban   est  $
q_0\varepsilon    \overline{x}\varepsilon$   (on    rappelle    que   la
représentation unaire d'un nombre $x$ est noté $ \overline{x}$):





{\footnotesize
\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=1.6cm,semithick]
\tikzstyle{every state}=[fill=white,draw=black,text=black]
\tikzstyle{accepting}=[fill=blue!20,draw=black,text=blue,accepting by arrow,double]
\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial by arrow,initial text=]
 

 \node[state,initial] (A)                    {$q_0$};
  \node[state] (B) [ right of=A] {$q_1$};
\node[state] (C) [ right of=B] {$q_2$};
\node[state]         (E) [ right of=C] {$q_3$};
  \node[state,accepting]         (F) [ right of=E] {$q_4$};
 
  \path (A) edge              node {$ \varepsilon$/$ \varepsilon$,D} (B)
        (B) %edge [loop above] node {1/0,D} (B)
            %edge [loop below] node {0/1,D} (B)
            edge              node {$1$/$1$,D} (C)
        (C) %edge [loop below] node {0/0,G} (C)
            edge [loop above] node {1/$ \varepsilon$,D} (C)
            edge node {$ \varepsilon$/$ \varepsilon$,G} (E)
         (E)  edge [loop above] node {$ \varepsilon$/$ \varepsilon$,G} (E)
            edge node {1/1,G} (F);
\end{tikzpicture}
\end{center}
}
\end{exercice}











% \begin{exercice}
%   Construire une machine de \bsc{Turing}  qui recopie un nombre unaire à
%   sa  suite en  laissant  un blanc  entre  les deux  et  en ramenant  le
%   pointeur avant le premier nombre.
% \end{exercice}

\begin{exercice}
  Construire une machine de \bsc{Turing} qui calcule la fonction prédécesseur.
\end{exercice}

\begin{exercice}
Comment  s'écrit  0  en   système  unaire?  Construire  une  machine  de
\bsc{Turing}   qui   calcule  la   fonction   identiquement  nulle:   la
configuration  initiale est $q_0\varepsilon  \overline{x}\varepsilon$ et
la configuration finale est $q_f\varepsilon 1 \varepsilon$
\end{exercice}


\begin{exercice}
  Nous allons  construire une  machine à additionner.  En base  1, c'est
  assez simple: écrivez l'addition en base 1 de 4 et 1 puis de 4 et 0.

On    suppose    qu'on    a    marqué   en    entrée    $    \varepsilon
\overline{x}\varepsilon\overline{y}\varepsilon$ avec $x$ et $y$ les deux
nombres à additionner.

La     configuration     finale     attendue     est     $q_f\varepsilon
\overline{x+y}\varepsilon$.


\end{exercice}






\begin{exercice}
  
Voici les codes ASCII décimaux de quelques caractères affichables:


\begin{center}
%\begin{table}[h!]
{\scriptsize



\begin{tabularx}{\linewidth}{Il*{10}{|X}I}
\hline
Caractère& A & B & C & D & E &F & G & H & I & J\\
\hline
Code & 65 & 66 & 67 & 68 & 69&70 & 71 & 72 & 73 & 74\\
\hline
\end{tabularx}






\begin{tabularx}{\linewidth}{Il*{10}{|X}I}
\hline
Caractère&  a & b & c & d & e & f & g & h & i & j \\
\hline
Code & 97 & 98 & 99 & 100 & 101 & 102 & 103 & 104 & 105 & 106  \\
\hline
\end{tabularx}


}
%\caption{Table des caractères ASCII affichables}
%\end{table}

\end{center}

\begin{enumerate}
\item Écrire les valeurs  en base 2 des codes de A, B et  C puis a, b et
  c.
\item Déterminer un automate décrivant une machine de \textsc{Turing} la
  plus simple possible 
  qui transforme le code ASCII (en binaire) d'une lettre minuscule en le
  code ASCII (en binaire toujours) de la majuscule correspondante.
\end{enumerate}


\end{exercice}





\subsection{Fonctions récursives}

\sage

\begin{exercice}

Soit $g$ la fonction  projection $\pi_1^{(1)}$ et $h=s\circ \pi_3^{(3)}$
avec $s$ la fonction successeur.

  Soit $f$ la récurrence de base $g$ et de pas $h$ définie sur $\bbn^2$.

Calculer  $f(0,0)$, $f(0,1)$,  $f(1,1)$,  $f(2,1)$, $f(1,2)$,  $f(4,2)$,
$f(2,4)$.

A-t-on $f(x,y)=f(y,x)$ pour tout couple $(x,y)$ d'entiers?
\end{exercice}



\begin{exercice}\label{exo::pyt_1}
Voici quelques fonctions écrites sous Python:

\begin{lstlisting}[caption={}]
def succ(x):
    return x+1

def pred(x):
    if x == 0:
        return 0
    else:
        return x-1


def pi(k,T):
    return T[k-1]


def g(x):
    return x

def h(T):
    return succ(pi(3,T))


def A(x1,x2):
    if x2 == 0:
        return g(x1)
    else:
        return h([x1,x2,A(x1,pred(x2))])
\end{lstlisting}


Que va retourner \lstinline+A(2,3)+? 

De quels types sont les arguments \verb+x+, \verb+T+, \verb+x1+ dans les
différentes fonctions ci-dessus?


\end{exercice}



\begin{exercice}
Soit   $g$  la  fonction   identiquement  nulle   et  $h$   définie  par
$h(x,y,z)=add(\pi_1^{(3)}(x,y,z),\pi_3^{(3)}(x,y,z))$    avec   add   la
fonction d'addition définie en cours.

  Soit $f$ la fonction définie sur $\bbn^2$ par:

$$
\begin{cases}
  f(x,0)=0\\
f(x,y+1)={\rm add}(x,f(x,y))
\end{cases}
$$


Montrer que $f$ peut être définie  comme la récurrence de base $g$ et de
pas $h$ avec  $g$ et $h$ des fonctions  primitives récursives définies à
partir des fonctions de base. 




Calculer  $f(0,0)$, $f(0,1)$,  $f(1,1)$,  $f(2,1)$, $f(1,2)$,  $f(4,2)$,
$f(2,4)$.

Que pensez-vous de $f$?

\end{exercice}



\begin{exercice}
  On définit sur Python une  nouvelle fonction à partir de la définition
  vue  à l'exercice  précédent  et  de la  fonction  \verb+A+ définie  à
  l'exercice \vref{exo::pyt_1}:

  \begin{lstlisting}[caption={}]
def M(x1,x2):
    if x2 == 0:
        return 0
    else:
        return A(x1,M(x1,pred(x2)))
  \end{lstlisting}


Que pensez-vous de la fonction suivante:


\begin{lstlisting}[caption={}]
def E(x1,x2):
    if x2 == 0:
        return 1
    else:
        return M(x1,E(x1,pred(x2)))
\end{lstlisting}


On peut continuer ainsi:


\begin{lstlisting}[caption={}]
def T(x1,x2):
    if x2 == 0:
        return 1
    else:
        return E(x1,T(x1,pred(x2)))
\end{lstlisting}

Comment écririez-vous \verb+T(2,4)+? Quel nombre va renvoyer Python?



Remarque:{\itshape
quand on passe sur machine, on  atteint vite les limites de Python quant
au  nombre   de  récursions,  même  en  augmentant   cette  limite  avec
\verb+setrecursionlimit(10000)+ par exemple.

Pour travailler confortablement avec des fonctions récursives, on peut
employer  des  langages  pour  qui  ce mode  de  programmation  est  \og
naturel\fg{} comme Caml, Scheme, Haskell.

}
 
\medskip

\begin{minipage}[t]{0.25\linewidth}
   \includegraphics[width=2.5cm]{knuth}
\end{minipage}\hspace{0.5cm}
\begin{minipage}[t]{0.7\linewidth}\vspace{-3.8cm}
  \hspace{5.5cm} 
 % \begin{flushright}

   On  peut itérer ce  genre de  construction pour  obtenir la  famille des
puissances itérées  de \textsc{Knuth}, du nom du  célébrissime auteur de
\textit{The  Art of  computer programming}  et du  langage  \TeX{} entre
autres...

Quelques citations:

\textit{Computer programming  is an art, because  it applies accumulated
  know-}
\end{minipage}

 {\itshape ledge to the world, because it requires skill and ingenuity, and especially because it produces objects of beauty. A programmer who subconsciously views himself as an artist will enjoy what he does and will do it better. }

Ou encore:

\textit{The psychological profiling [of a programmer] is mostly the ability to shift levels of abstraction, from low level to high level. To see something in the small and to see something in the large.}

On utilise en général les notations suivantes:

$$    a\uparrow^n b= \left\{ \begin{matrix} a^b\qquad\qquad\qquad\qquad&&\mbox{si }n=1\quad\\ 1\qquad\qquad\qquad\qquad\ &&\mbox{si }b=0\quad\,\\ a\uparrow^{n-1}(a\uparrow^n(b-1))&&\mbox{sinon}\ \, \end{matrix} \right. 
$$

 %\end{flushright}






\end{exercice}



\begin{exercice}
Montrer   que   la  fonction   $f:   \bbn^2   \to   \bbn$  définie   par
$f(x,y)=xy+3x^2+1$ est primitive récursive.
\end{exercice}




\begin{exercice}
Définissez récursivement la fonction sgn  définie sur $\bbn$ et qui vaut
0 en 0 et 1 sinon.

Définissez récursivement la fonction cosgn  définie sur $\bbn$ et qui vaut
1 en 0 et 0 sinon.

Définissez récursivement la soustraction propre définie sur $\bbn$ par:

$$
\begin{cases}
  {\rm sous}(x,y)=x-y \quad \text{si } x \geqslant y\\
 {\rm sous}(x,y)=0 \quad \text{si } x < y
\end{cases}
$$

à l'aide de la fonction pred. 


Montrez alors que les tests $(x<y)$, $(x>y)$ et $x=y$ sont des fonctions
primitives récursives en utilisant sgn, cosgn, sous et add.
\end{exercice}


\begin{exercice}
  \begin{enumerate}
  \item Calculez quelques termes de la suite d'\textsc{Ackermann}.
\item   Proposez  une  fonction   Python  traduisant   littéralement  la
  définition récursive de  la fonction d'\textsc{Ackermann}. Placez-y un
  \og espion \fg{} qui compte  le nombre d'appels. Testez sur l'image de
  $(3,6)$.
\item Commentez le programme suivant:
  \begin{lstlisting}[caption={}]
def f(a,b):
    global espion
    espion += 1
    while a > 0:
        if b == 0:
            b = 1
        else:
            b = f(a, b - 1)
        a -= 1
    return b + 1
  \end{lstlisting}
\item Démontrer (éventuellement par récurrence) que:
  \begin{enumerate}
  \item $A(0,n)=n+1$
\item $A(1,n)=n+2$
\item $A(2,n)=2n+3$
\item $A(3,n) =2^{n+3}-3$
  \end{enumerate}
\item  Utilisez tous ces  résultats afin  d'obtenir une  fonction Python
   plus  efficace. Par exemple, calculez  $A(4,2)$. Comme Python
  va  calculer avec  des  grands entiers,  vous  utiliserez la  commande
  \verb+long+:

  \begin{lstlisting}[caption={}]
>>> A(long(4),long(2))
  \end{lstlisting}

Vous  vérifierez que  $A(4,2)$ est  un nombre  dont  l'écriture décimale
comporte $\numprint{19729}$ caractères...

Quel  est  le  lien   entre  la  fonction  d'\textsc{Ackermann}  et  les
puissances itérées  de \textsc{Knuth}? Comment  alors exprimer $A(4,n)$,
$A(5,n)$, etc. à l'aide des puissances itérées  de \textsc{Knuth}?

  \end{enumerate}
  
\end{exercice}











%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{listeexercices}
\modenormal % restaure les définitions de sections, sous-sections, etc.
%%% Local Variables: 
%%% TeX-master: "Poly_automates_info1"
%%% End: 
