914.tex

\documentclass{agregfiche}

\title{Leçon 914 -- Décidabilité et indécidabilité. Exemples.}

% V1 par Gaetan Doueneau
% Relu par Gaetean Doueneau, Aliaume Lopez, Emilie Grienberger, Charlie Jacomme
% Relu par Jean Goubault

\begin{document}

\maketitle

\secrapports

\begin{rapport}{2017,2018,2019}
Le programme de l'option offre de très nombreuses possibilités d'exemples. Si les exemples classiques de problèmes sur les machines de Turing figurent naturellement dans la leçon, le jury apprécie des exemples issus d'autres parties du programme : théorie des langages, logique, \dots
Le jury portera une attention particulière à une formalisation propre des réductions, qui sont parfois très approximatives.
\end{rapport}

\secindispensables

\begin{itemize}
\item Définitions des langages et problèmes décidables/récursivement énumérables.
\item Problème de l'arrêt, problème de correspondance de Post.
\item Fonctions calculables, notions de réduction.
\end{itemize}

\secasavoir

\begin{itemize}
    \item Théorème de Rice. Bien savoir l'appliquer et le prouver.
    \item Plein d'exemples au choix, de problèmes et de réductions (logique du premier ordre, vacuité de l'intersection de grammaires, $\beta$-équivalence de lambda termes,\dots).
\end{itemize}


\secidees
% to complete
\begin{itemize}
\item Mettre en parallèle résultats positifs (décidabilité) et négatifs (indécidabilité).
\item Exemples choisis de décidabilité/indécidabilité en logique. Liens avec l'incomplétude.
\item Dixième problème de Hilbert.
\item (dur) Un peu de hiérarchie arithmétique.
\end{itemize}

\secpieges

\begin{itemize}
\item En une ligne, rappeler le modèle de calcul, les machines de Turing et leur codage.
\item Être très clair sur les définitions de départ et l'exigence de calculabilité dans les réductions.
\item Comprendre la différence récursivement énumérable/décidable/indécidable.
\item Énoncer Rice sans erreur.
\end{itemize}



\secquestionsclassiques
\begin{itemize}
\item Justifier la propriété des réductions.
  % on montre qu'un problème permet d'en résoudre un autre, i.e on
  % montre qu'un problème est au moins aussi difficile qu'un autre
\item Tel problème est-il décidable ? (savoir donner explicitement une machine de Turing pour un problème simple)
\item Tel problème est-il indécidable ? (savoir donner une réduction simple)
\item Expliquer ce que signifie Rice, et ses implications.
  % preuve de programme impossible
\item Décidable/indécidable dans l'arithmétique: Peano, Presburger, Skolem.
\item Décidable/indécidable pour les grammaires algébriques: vacuité,
  universalité, problème du mot et intersections, inclusion dans un
  rationnel\dots (Carton)
  % vide,ambiguité universalité indécidable,
\item Montrer qu'un ensemble indénombrable de langages contient au
  moins un langage indécidable.
  % ensemble des TM = énumérable
\end{itemize}

\secreferences
\begin{itemize}
\item \input{refs/carton}
\item \input{refs/sipser}
\end{itemize}

\secdev
%% sketchy, to complete
\begin{itemize}
    \item[++] \input{dev/arretTM}
\item[+] \input{dev/indegram}
\item[+] \input{dev/presburger}
%\item \input{dev/olin}
\item[+] \input{dev/peano}

\end{itemize}


\end{document}