\documentclass[a4paper]{article}
\usepackage{entete}
\author{Référence~: Introduction à la calculabilité. Pierre \textsc{Wolper}}
\title{Théorème de Rice}
\date{2011-2012}

\begin{document}
\maketitle

On définit dans la suite deux langages~:
\begin{defi}
    On note $(w_i)$ et $(M_j)$ des énumérations des mots et des machines de Turing, et on pose
    \begin{itemize}
        \item $\displaystyle{L_0 := \{w~|~w=w_i \text{ et } M_i \text{ n'accepte pas } w_i\}}$.
        \item $\displaystyle{LU := \{<M,w>~|~M \text{ accepte } w\}}$
    \end{itemize}
    On note $\overline{L_0}$ et $\overline{LU}$ les complémentaires.
\end{defi}

\begin{thm}
    Tout propriété non triviale des langages récursivement énumérables est indécidable.
\end{thm}

\begin{proof}
    On va montrer que les langages $L_0$, $\overline{L_0}$ et $LU$ sont indécidables, puis, pour une propriété non triviale sur les langages récursivement énumérables $P$, on montrera que $P$ est indécidable par une réduction à partir de $LU$.

    \begin{lem}\label{lem:l0}
        $L_0$ est indécidable.
    \end{lem}
    \begin{prooflem}
       Supposons $L_0$ décidable~: il existe une machine de Turing qui l'accepte, soit $M_k$. On a alors~:
       \begin{itemize}
           \item si $M_k$ accepte $w_k$, alors $w_k \not \in L_0$ par définition de $L_0$ $\rightarrow$ contradiction.
           \item si $M_k$ n'accepte pas $w_k$, alors $w_k \in L_0$ $\rightarrow$ contradiction.
       \end{itemize}
    \end{prooflem}

    \begin{lem}\label{lem:l0bar}
        $\overline{L_0}$ est indécidable.
    \end{lem}
    \begin{prooflem}
        Si $\overline{L_0}$ était décidable, alors $L_0$ aussi.
    \end{prooflem}

    \begin{lem}\label{lu}
        $LU$ est indécidable.
    \end{lem}
    \begin{prooflem}
        On fait une réduction à partir de $\overline{L_0}$.

        Supposons donc $LU$ décidable. Considérons l'algorithme suivant, prenant en entrée un mot $w$~:
        \begin{itemize}
            \item on détermine $i$ tel que $w=w_i$ ;
            \item on détermine $M_i$ ;
            \item on applique la procédure de décision pour $LU$ à $<M_i,w_i>$~: si le résultat est positif, on accepte $w$, sinon on le rejette.
        \end{itemize}
        Alors cet algorithme décide $\overline{L_0}$ $\rightarrow$ contradiction.
    \end{prooflem}

    Soit maintenant $P$ une propriété non triviale sur les langages récursivement énumérables.

    On peut supposer que le langage vide ne vérifie pas $P$ (sinon, on considère $\overline P$).

    Comme $P$ est non triviale, il existe une machine de Turing $M_p$ qui accepte un langage vérifiant $P$.

    Pour une instance $<M,w>$ de $LU$, on construit une machine $M'$ qui a le comportement suivant~:
    \begin{itemize}
        \item $M'$ simule l'exécution de $M$ sur $w$, sans tenir compte du mot d'entrée $x$ ;
        \item si $M$ accepte $w$, elle simule $M_p$ sur $x$ ;
        \item si $M$ n'accepte pas $w$ (rejet ou exécution infinie), $M'$ n'accepte aucun mot.
    \end{itemize}

    On a alors~:
        $\mathcal L(M')$ vérifie $P$ si et seulement si $<M,w> \in LU$.
\end{proof}

\end{document}