\documentclass[twoside,a4paper]{article}


\usepackage{amsmath,amssymb,latexsym,epsfig,delarray,graphics,graphpap,alltt,graphicx}


\newtheorem {exercice} {Exercice \rm 10.\hspace {-.1cm}}
\newcommand{\sy}[1]{\mbox{\crr #1}}
\newfont{\crr}{pcrr at 11pt}
\newcommand{\tuple}[1]{{\langle{#1}\rangle}} % <.>

\begin{document}

\title{\textbf {El\'ements d' informatique th\'eorique} \\
                  S\'erie 10 \\
         \textsl {}}
\date {}
\vspace {-100 mm}
\maketitle



%\begin{exercice}
%  Montrer comment il est possible de coder toutes les machines de
%  Turing qui travaillent avec un alphabet fixé de symboles.
%\end{exercice}

%\begin{exercice}
%  Supposons des machines de Turing dont l'union des alphabets soit
%  infinie.  Montrer comment ces machines peuvent être codées par une
%  chaîne binaire.
%\end{exercice}

\begin{exercice}
  Montrer que l'ensemble des machines de Turing est dénombrable.
\end{exercice}

\begin{exercice}
  Montrez que le langage $\overline{L_d} = \{w \mid w=w_i\ \mbox{et}\ 
  M_i\ \mbox{accepte}\ w_i\}$ est récursivement énumérable\,!
\end{exercice}

\begin{exercice}
  Montrez que la réduction ``many-one'' est une relation réflexive et
  transitive\,!
\end{exercice}

\begin{exercice} Halting problem\\
  Montrez que le langage $L_h=\{\tuple{M,w} \mid M \;\mbox{s'arrête
    sur}\ w\}$ n'est pas récursif ($L_u \leq_M L_h$)\,!
\end{exercice}

\begin{exercice}
  Montrez que déterminer qu'un programme `C' (quelconque) s'arrête
  pour toutes les valeurs de ses paramètres est indécidable\,!
\end{exercice}

\begin{exercice}
  Montrez que le problème de déterminer si une machine de Turing
  s'arrête lorsque son mot d'entrée est le mot vide est indécidable\,!
\end{exercice}

\begin{exercice}
  Montrez que le problème de déterminer si une machine de Turing
  s'arrête sur au moins un mot d'entrée est indécidable\,!
\end{exercice}

\end{document}


% Local Variables: 
% mode: latex
% TeX-master: "main"
% End: 
