SyntheseCalculabilite.tex

\input{lib.tex}
\usepackage{pdfpages}
\usepackage{palatino}
\usepackage{enumitem}

\usepackage[bottom]{footmisc}
\usepackage{desclist}
\usepackage{tocloft}
\setlength\cftparskip{4pt}

\setlist[itemize]{topsep=3pt,after=\vspace{.5\baselineskip}}
\usepackage[left=3cm,right=3cm,top=3cm,bottom=3cm]{geometry}
\setlength{\parskip}{2mm}

\definecolor{mygreen}{rgb}{0,0.6,0}
\definecolor{mygray}{rgb}{0.5,0.5,0.5}
\definecolor{mymauve}{rgb}{0.58,0,0.82}

\newcommand{\stcomp}[1]{\overline{#1}} 
\newcommand{\N}{\mathbb{N}}

% Make the style indentedefinition use bold for the name of the theorem
\makeatletter
\def\th@indenteddefinition{%
  \thm@notefont{}% same as heading font
  \normalfont % body font
}
\makeatother

\lstset{language={Java}}

\def\blurb{\textsc{Université catholique de Louvain\\
  École polytechnique de Louvain}}
\def\clap#1{\hbox to 0pt{\hss #1\hss}}%
\def\ligne#1{%
  \hbox to \hsize{%
    \vbox{\centering #1}}}%
\def\haut#1#2#3{%
  \hbox to \hsize{%
    \rlap{\vtop{\raggedright #1}}%
    \hss
    \clap{\vbox{\vfill\centering #2\vfill}}%
    \hss
    \llap{\vtop{\raggedleft #3}}}}%
\begin{document}

\begin{titlepage}
\thispagestyle{empty}\vbox to 1\vsize{%
  \vss
  \vbox to 1\vsize{%
    \haut{\raisebox{-8mm}{\includegraphics[width=2cm]{logo_ucl.pdf}}}{\blurb}{\raisebox{-3mm}{\includegraphics[scale=0.35]{logo_epl.jpg}}}
    \vfill
    \ligne{\Huge \textbf{\textsc{Synthèse calculabilité}}}
    \vspace{5mm}
    \ligne{\large{-- juin 2014 --}}
    \vfill
    \vspace{5mm}
    \ligne{%
         \textsc{Hachez} Floran 
      }
    \ligne{%
    \vspace{5mm}
	\textbf{Contributeurs :}
      }
    \ligne{%
	\textsc{François} Robinet
      }
    \ligne{%
	\textsc{Lena} Peschke
      }
    \ligne{%
	\textsc{Lionel} Nobel
      }
    }%
  \vss
  }
\end{titlepage}

\tableofcontents
\newpage

La synthèse est assez longue et fortement inspirée du cours sur la calculabilité
de Yves Deville à l'UCL. Mais, elle reprend ce qui est selon moi intéressant à connaitre
pour l'examen et qui devrait suffire pour répondre et pour justifier les QCM.

Les sources sont sur github : https://github.com/FHachez/SyntheseQ6

\section{Introduction}
\label{sec:introduction}

\paragraph{}
La calculabilité c'est l'étude des limites de l'informatique. Il faut bien 
faire attention à faire la différence entre les limites théoriques et les limites
pratiques. Pour la calculabilité, on s'occupe des limites théoriques.
Alors que pour la complexité on s'occupe des limites pratiques. La complexité
détermine la frontière entre ce qui est faisable en pratique et infaisable en pratique.
La question principale de la calculabilité est: "quels sont les problèmes qui peuvent
être résolus par un programme?". La caractéristique de calculabilité ne donne aucune autre information sur le programme que son existence.

\paragraph{} Le but est donc de tracer des frontières entre les programmes calculables,
non calculables et non calculables en pratique.

\paragraph{}
Ça nous permet de savoir quand ça ne sert à rien de résoudre un problème.
De plus, on est conscient de sa complexité intrinsèque d'un
problème.
% paragraph  (end)

\subsection{Notion de problème}
\label{subsec:notion_de_probl_me}

\paragraph{}
Premièrement, on doit parler la notion de problème.
Attention, il ne faut pas confondre un problème avec un programme.
Les caractéristiques d'un problème sont:

\begin{itemize}
	\item un problème est générique : il s'applique à un ensemble de données.
	\item pour chaque donnée particulière, il existe une réponse.
\end{itemize}
On représente un problème dans le cours par une fonction. Donc dans le cours,
la description d'un problème est équivalente à la description d'une fonction.
% paragraph  (end)
% subsection notion_de_probl_me (end)

\subsection{Notion de programme}
\label{ssub:notion_de_programme}

Un programme est une "procédure effective", c'est-à-dire exécutable par une machine.
Il existe plein de formalismes permettant la description de "procédure effective".

% subsection notion_de_programme (end)

\subsection{Résultats principaux}
\label{sub:r_sultat_principaux}

\begin{itemize}
	\item Équivalence des langages de programmation (complets).
	\item Problème non calculable : il existe des problèmes qui ne peuvent 
		être résolus par un programme. Ex: détection de virus, équivalence
		de programme,...
	\item Problème intrinsèquement complexe. (Voir complexité) Les problèmes
		qui ont une complexité supérieure ou égale à l'exponentielle. Dans
		ce cas, même l'amélioration des ordinateurs n'influence presque pas
		la taille de l'entrée possible.
\end{itemize}

% subsection r_sultat_principaux (end)

\subsection{Détection de virus}
\label{sub:d_tection_de_virus}
On veut déterminer si un programme P avec une entrée D est nuisible.

Spécification du programme detecteur(P,D):\\
\textbf{Préconditions :} un programme P et une donnée D\\
\textbf{Postconditions :} "Mauvais" si P(D) est nuisible,
		"Bon" sinon

\paragraph{}On va créer un programme drole(P) et essayer de détecter s’ il est nuisible.

\begin{lstlisting}
drole(P) \\
if detecteur(P,P) = "Mauvais" 
	then stop
else infecter un autre programme en y inserant P
\end{lstlisting}

Testons drole(drole).
\begin{lstlisting}
drole(drole)
if detecteur(drole, drole) = "Mauvais" 
	then stop
else infecter un autre programme en y inserant drole

\end{lstlisting}

\begin{itemize}
	\item Si drole(drole) est nuisible alors le programme s'arrête or il
	       	n'est pas nuisible puisqu'il n'a infecté aucun programme.
	\item Si par contre il n'est pas nuisible alors il va infecter un 
		autre programme.
\end{itemize}
On a donc une contradiction ce qui implique que le programme drole ne peut 
exister, ce qui implique que  le programme detecteur non plus.
% paragraph  (end)
% subsection d_tection_de_virus (end)

% section introduction (end)Introduction

\section{Concepts}
\label{sec:concepts}

% Dans cette partie il y a pas moyen de synthétiser beaucoup.

\subsection{Ensembles, langages, relations et fonctions}
\label{sub:ensembles_langages_relations_et_fonctions}

\subsubsection{Ensembles}
\label{ssub:ensembles}
Un ensemble est une collection d'objets, sans répétition, appelés les éléments
de l'ensemble.\\

Notation : 
\begin{itemize}
	\item Ensemble fini : \{ 0, 1, 2\}
	\item Ensemble infini : \{ 0, 1, 2, ...\}
	\item Produit cartésien : $A \times B$
	\item Ensemble des ensembles : $2^A$ ou $\mathcal{P}(A)$
	\item Complément : $\stcomp{A}$
\end{itemize}

% subsubsection ensembles (end)

\subsubsection{Langages}
\label{ssub:Langages}
Notation : 
\begin{itemize}
	\item une chaîne de caractère ou un mot : séquence FINIE de symboles. 
		abceced, 010101101
	\item chaîne de caractères vide : $\epsilon$
	\item un alphabet $\Sigma$ est un ensemble de symboles. $\Sigma = \{1, 2\}$
	\item un langage est un ensemble de mots constitués de symboles d'un alphabet
		donné.
	\item ensemble de tous les mots possibles sur l'alphabet $\Sigma$ : $\Sigma ^*$
\end{itemize}

% subsubsection Langages (end)

\subsubsection{Relations}
\label{ssub:relations}
Soient $A$, $B$ des ensembles.
\begin{itemize}
	\item Une relation $R$ sur $A$, $B$ est un sous-ensemble de $A \times B$. C'est-à-dire
		un ensemble de paires $<a,b>$ avec $a\in A$, $b\in B$.
	\item On peut définir une relation par sa table
	\item On peut écrire $<a,b> \in R$ ou $aRb$ ou $R(a,b)$. 
\end{itemize}

% subsubsection relations (end)

\subsubsection{Fonctions}
\label{ssub:fonctions}
Soient $A$, $B$ des ensembles.
\begin{itemize}
	\item Une fonction $f: A \rightarrow B$ est une relation telle que pour $a \in
	A$, il existe au plus un $b \in B$ tel que $<a,b> \in f$
	\item écrire $f(a)=b$ est équivalent à $<a,b> \in f$
	\item Si il n'existe pas de $b \in B$ tel que $f(a)=b$ alors $f(a)$ est indéfini,
		$f(a) = \perp$
\end{itemize}

Dans le cours on utilise les propriétés classiques: dom($f$), image($f$), fonction totale,
fonction partielle, fonction surjective, injective et bijective. Celles-ci ne 
seront pas redéfinies ici.\\
On utilise aussi l'\textbf{extension} : 
$f: A \rightarrow B$ est une extension de $g: A \rightarrow B$ si $\forall x \in A : g(x)\neq \perp \Rightarrow f(x) = g(x)$.
Autrement dit, $f$ a la même valeur que $g$ partout où $g$ est définie.

\paragraph{Définition d'une fonction}
\label{par:d_finition_d_une_fonciton}
On définit une fonction par sa table qui peut-être infinie.\\
On peut définir la table de plusieurs façons :
\begin{itemize}
	\item Par un texte fini déterminant sans contradiction ni ambigüité le contenu
		de la table.
	\item Par un algorithme ex : $f(x) = 2x^3+5$
	\item Écrire toutes les paires de la relation.
\end{itemize}
Attention, il n'est pas nécessaire de décrire ou de connaître un moyen de la calculer
pour pouvoir la définir. Ex : $f(x) = 1$ s'il y a de la vie autre part que sur terre,
$0$ sinon.
% paragraph d_finition_d_une_fonction (end)
% subsubsection fonctions (end)
% subsection ensembles_langages_relations_et_fonctions (end)

\subsection{Ensemble énumérable}
\label{sub:ensemble_num_rables}

Avant de dire ce qu'est un ensemble énumérable, on doit savoir que deux ensembles
ont le même cardinal s’il existe une bijection entre eux.

\begin{mydef}[Ensemble énumérable]
	Un ensemble est énumérable ou dénombrable s'il est fini ou s'il a le même cardinal que $\mathbb{\N}$. \\
	Quelques propriétés : 
\end{mydef}
	
\begin{myprop}
	Tout sous-ensemble d'un ensemble énumérable est énumérable.
\end{myprop}

\begin{myprop}
L'union et l'intersection de deux ensembles énumérables sont énumérables.
\end{myprop}

\begin{myprop}
L'union d'une infinité d'ensembles énumérables est énumérable.\\ (Facile à
		démontrer, voir TP)
\end{myprop}

Quelques ensembles non énumérables : 
\begin{myexem}
 L'ensemble $\R$
\end{myexem}

\begin{myexem}
 L'ensemble des sous-ensembles de $\N$, $\mathcal{P}(\N)$
\end{myexem}

\begin{myexem}
 L'ensemble des chaînes infinies de caractère sur un alphabet fini
\end{myexem}

\begin{myexem}
 L'ensemble des fonctions de $\N$ dans $\N$ (Cas important)
\end{myexem}

% subsection ensemble_num_rables (end)

\subsection{Cantor}
\label{sub:cantor}
On va montrer qu'il existe des ensembles non énumérables par diagonalisation. Ex $\R$.
\begin{myexem}
	Exemple de démonstration par diagonalisation: 
	\begin{enumerate}
		\item Construire une table : Liste de tous les grands
			mathématiciens \\	
			\begin{tabular}{l}
				\textit{\textbf{D}}E MORGAN \\
				A\textit{\textbf{B}}EL\\
				BO\textit{\textbf{O}}LE\\
				BRO\textit{\textbf{U}}WER\\
				SIER\textit{\textbf{P}}INSKI\\
				WEIER\textit{\textbf{S}}TRASS\\
			\end{tabular}
		\item Sélectionner la diagonale : $diag = $DBOUPS
		\item Modifier l'élément égal à la diagonale : $diag' =$ CANTOR
		\item Montrer que l'élément n'est pas dans la liste $\Rightarrow$ Contradiction
		\item Conclusion :
			\begin{itemize}
				\item Soit on sait que la liste est complète\\
					$ \Rightarrow$ CANTOR n'est pas un grand
				mathématicien (cas utilisé pour démontrer
				halt).
				\item Soit on sait que CANTOR est un grand
					mathématicien \\
					$ \Rightarrow$ la liste est incomplète
				(cas utilisé pour la diagonalisation de CANTOR)
			\end{itemize}
	\end{enumerate}
\end{myexem}

\begin{mytheo}[Diagonalisation de Cantor]
	Soit $E = \{ x \text{ réel }| 0<x\leq1\}$, $E$ est non énumérable.
\end{mytheo}

\paragraph{Démonstration :}
On va montrer qu'un nombre $d'$ n'est pas dans l'énumération alors qu'on sait
que $d'$ est un nombre réel compris entre 0 et 1.

On suppose $E$ énumérable. Donc il existe une énumération des éléments de $E$,
$x_0, x_1,\dots,X_k,\dots$. On peut représenter un nombre $x_k$ comme étant une
suite de chiffre $x_{ki}$ : $x_k = 0.x_{k0}x_{k1}\dots x_{kk}\dots$.

\begin{enumerate}
	\item On peut donc construire une table infinie : \\
		\begin{tabular}{|c||c|c|c|c|c|c|}
			\hline
			& 1 digit & 2 digit & 3 digit & ... & k+1 digit & ... \\
			\hline
			$x_0$ & $x_{00}$ & $x_{01}$ & $x_{02}$ & ... & $x_{0k}$ & ... \\
			$x_1$ & $x_{10}$ & $x_{11}$ & $x_{12}$ & ... & $x_{1k}$ & ... \\
			$x_2$ & $x_{20}$ & $x_{21}$ & $x_{22}$ & ... & $x_{2k}$ & ... \\
			: & : &:& : & : & : &:\\
			$x_k$ & $x_{k0}$ & $x_{k1}$ & $x_{k2}$ & ... & $x_{kk}$ & ... \\
			: & : &:& : & : & : &:\\
			\hline
		\end{tabular}
	\item Sélection de la diagonale (celle-ci est un nombre réel compris
		entre 0 et 1)
		\[ d=0.x_{00}x_{11}...x_{kk}... \]	
	\item Modification de cet élément $d$ pour obtenir
		\[ d'=0.x_{00}'x_{11}'...x_{kk}'... \]	
		Où $x_{ii}'=5$ si $x_{ii}'\neq 5$ \\
		$x_{ii}'=6$ si $x_{ii}'= 5$ \\
		On a toujours que cet élément $d'$ est compris entre 0 et 1
	\item Contradiction, car $d'$ est dans l'énumération, car $E$ est
		énumérable (par supposition). Il existe donc $x_p=d'$, 
		\[ d'=x_p=0.x_{p0}x_{p1}...x_{pp}... \]	
		\[ d'=0.x_{00}'x_{11}'...x_{pp}'... \]	
		La contradiction vient du fait qu'on a choisi $x_{pp}' \neq
	       	x_{pp}$. Donc $d' \neq x_p$ ce qui implique que $d'$ n'est pas
		dans l'énumération.
	\item Conclusion : $E$ n'est pas énumérable

\end{enumerate}
% subsection cantor (end)

\subsection{Conclusion}

Les ensembles énumérables sont importants pour la suite du cours et aussi, car en 
informatique on ne considère que les ensembles énumérables.
Dans le cours, on va souvent devoir montrer qu'un ensemble est énumérable/non énumérable.
Généralement on va utiliser une des techniques suivantes: 
\begin{itemize}
	\item montrer qu'il y a une bijection avec $\N$ ou $\R$
	\item montrer que l'ensemble est fini
	\item utiliser la diagonalisation (cf. Cantor)
	\item écrire un programme qui énumère l'ensemble
\end{itemize}

% subsection conclusion (end)
% section concepts (end)

\section{Résultats fondamentaux}
\label{sec:r_sultats_fondamentaux}

\subsection{Algorithmes et effectivité}
\label{sub:algorithmes_et_effectivit_}
Qu'est-ce qu'un algorithme? 

\begin{mydef}[Algorithme]
	C'est une procédure qui peut être appliquée à n'importe
	quelle donnée et qui a pour effet de produire un résultat. C'est un ensemble fini
	d'instructions qui peuvent être exécutées. Dans ce cours, on ne tracasse pas 
	de la taille des données, des instructions ni de la mémoire disponible, mais 
	les considère comme finies. 
\end{mydef}

\begin{myrem}
	Un algorithme n'est pas une fonction, mais un algorithme calcule une 
	fonction.
	De plus dans le cours on se limite aux fonctions de $\N^n$ dans $\N$. Car on peut,
	montrer que ça revient au même que de considérer de $\N^n$ dans $\N^n$ (
	$\N^n$ est énumérable et donc au plus de même cardinal que $\N$). On va aussi
	utiliser Java comme modèle étant donné que c'est plus facile et qu'on va montrer 
	que les modèles complets sont équivalents.
\end{myrem}

% subsection algorithmes_et_effectivit_ (end)

\subsection{Fonctions calculables, ensembles récursifs et récursivement énumérables}
\label{sub:fonctions_calculables_ensembles_r_crusids_et_r_cursivement_num_rables}

\subsubsection{Fonction calculable}
\label{ssub:fonction_calculable}

\begin{mydef}[Fonction calculable]
	Une fonction $f$ est calculable s’il existe un algorithme qui, recevant comme donnée
	n'importe quels nombres naturels $x_1$,...$x_n$ fournit \textbf{tôt ou tard} comme 
	résultat $f(x)$ s’il existe.
\end{mydef}
	
\paragraph{} S’il ne se termine pas c'est que $f(x)=\perp$. \\

\begin{myrem}
	Il faut faire attention entre ne pas être capable d'écrire un algorithme
	et ne pas savoir l'écrire. (Voir exemple TP et cours : y a-t-il une rose 
	verte sur Mars ou encore x occurrences de 5 dans $\pi$).
\end{myrem}

\begin{myrem}
	Une fonction peut-être totale calculable ou partielle calculable.
\end{myrem}

% subsubsection fonction_calculable (end)

\subsubsection{Ensemble récursif et récursivement énumérable}
\label{ssub:ensemble_r_cursif_et_r_cursivement_num_rable}
Soit $A\subseteq \N$

\begin{mydef}[Ensemble récursif]
	$A$ est récursif s’ il existe un algorithme qui recevant un $x\in \N$,
	fournit \textbf{tôt ou tard} comme résultat 
	\begin{tabular}{l}
		1 si $x\in A$\\
		0 si $x\notin A$\\
	\end{tabular}
	. L'algorithme décide si $x$ est dans $A$ ou non.
\end{mydef}

\begin{mydef}[Ensemble récursivement énumérable]
	$A$ est récursivement énumérable s’ il existe un algorithme qui recevant
	un $x\in \N$, fourni \textbf{tôt ou tard} \\
	comme résultat
	\begin{tabular}{l}
		1 si $x\in A$\\
		 ne se termine pas ou retourne un résultat $\neq1$ si
		 $x\notin A$\\
	\end{tabular}
\end{mydef}

\begin{myrem}
	Le souci lorsque c'est récursivement énumérable,
	c'est que même si l'algorithme permet de dire si x est dans A, si x
	n'est pas dans A on ne sait rien dire. En effet, on ne peut pas dire à un moment qu'on
	arrête l'algorithme et que l'élément n'est pas dans A.
       	Car il est possible que x soit dans A et que l'algorithme ne
	l'ait pas encore déterminé (l'algorithme retourne tôt ou tard un
	résultat si x est dans A!).
\end{myrem}

\paragraph{Définition importante :}
\label{par:d_finition_importante}

\begin{mydef}[Fonction caractéristique]
	Fonction caractéristique de A:
	$X_A$ : $\N$ $\rightarrow$ $\N$, \\
	tel que $X_A(x)$ =
	\begin{tabular}{l}
		1 si x $\in$ A \\	
		0 si x $\notin$ A 
	\end{tabular}
\end{mydef}

\begin{myprop}
	A est un ensemble récursif ssi $X_A$ est une fonction totale
	calculable. \\ 
	Ça veut dire qu'il existe une fonction $X_A$ qui décide si n'importe
	qu'elle x appartient ou non à A. Ce qui est évident.
\end{myprop}

\begin{myprop}
	A est un ensemble récursivement énumérable ssi A = dom(f) et f est une 
	fonction (totale ou partielle) calculable.\\
       	En effet, si f(x) est défini alors
	x appartient à A.
\end{myprop}

\begin{myprop}
	A est un ensemble récursivement énumérable ssi A est vide ou A = image(f) et f
	est une fonction totale calculable. \\
	Car f est une fonction d'énumération (elle
	peut répéter plusieurs fois un élément, mais ce n'est pas gênant).
\end{myprop}

% paragraph d_finition_importante (end)

\paragraph{Propriétés importantes}
\label{par:propri_t_s_importantes}
\begin{myprop}
	A récursif $\Rightarrow$ A récursivement énumérable. (Propriété plus
		faible)
\end{myprop}

\begin{myprop}
	A récursif $\Rightarrow$ ($\N$\textbackslash A) récursif.\\ On peut facilement créer
		un programme qui retourne 1 - le programme qui décide A.
\end{myprop}

\begin{myprop}
	A récursivement énumérable et ($\N$\textbackslash A) récursivement énumérable
		$\Rightarrow$ A récursif.\\ Il suffit de créer un programme
		qui exécute un peu du programme qui décide A puis un peu de celui qui
		décide ($\N$\textbackslash A). Et ainsi de suite, jusqu'au moment ou l'un 
		des programmes retourne une réponse.
\end{myprop}

\begin{myprop}
	A fini $\Rightarrow$ A récursif. (Trivial)
\end{myprop}

\begin{myprop}
	($\N$\textbackslash A) fini $\Rightarrow$ A récursif. (Trivial)
\end{myprop}


% paragraph propri_t_s_importantes (end)
% subsubsection ensemble_r_cursif_et_r_cursivement_num_rable (end)
% subsection fonctions_calculables_ensembles_r_crusids_et_r_cursivement_num_rables (end)

\subsection{Thèse de Church-Turing}
\label{sub:th_se_de_church_turing}
Grâce à la définition, on sait montrer qu'une fonction est calculable. Mais comment
montrer qu'une fonction n'est pas calculable? Pour ça on a besoin d'une définition
couvrant la totalité des fonctions calculables. \\
Une autre question est est-ce que prendre un modèle particulier est restrictif?\\
La thèse de Turing répond à ces questions.
\begin{enumerate}
	\item Aucun modèle de la notion de fonction calculable n'est plus puissant
		que les Machines de Turing \\
		Version moderne : Une fonction est calculable s'il existe un 
		programme d'ordinateur qui calcul cette fonction
	\item Toute fonction calculable est calculable par une machine de Turing.
	\item Toutes les définitions formelles de la calculabilité connues à ce 
		jour sont équivalentes (Théorème, ça a été démontré) (justifie 
		l'utilisation de Java comme modèle)
	\item Toutes les formalisations de la calculabilité établies par la 
		suite seront équivalentes aux définitions connues
\end{enumerate}
1, 2 et 4 sont des thèses universellement reconnues comme vraies et la 3 est un
théorème.

% subsection th_se_de_church_turing (end)

\subsection{Programmes et fonctions}
\label{sub:programmes_et_fonctions}
Dans le cours on utilise un langage de programmation, Java, comme modèle.

\begin{mydef}[P]
	Soit P l'ensemble des programmes Java qui reçoit un ou plusieurs entiers comme 
	donnée et qui imprime/retourne un résultat.
\end{mydef}

\begin{myprop}
	P est un ensemble infini dénombrable, car c'est chaîne de caractère d'un 
	alphabet fini. P est récursif, car il existe un programme, le compilateur, qui détermine 
	si un programme est un programme Java ou non.
\end{myprop}

\begin{mydef}[Énumération de P]
	P = $P_0$, $P_1$,... ,$P_k$,... est l'énumération des programmes Java 
	sans répétition. Ce qui implique qu'on peut numéroter les programmes Java.\\
\end{mydef}

\begin{mydef}[$P_k$]
	$P_k$ est le programme numéro k dans P
\end{mydef}

\begin{mydef}[$\phi^{(n)}_k$]
	$\phi^{(n)}_k$ : $\N^n \rightarrow \N$ comme 
	étant la fonction calculée par $P_k$
\end{mydef}


\begin{myprop}
	Il existe donc une fonction f : $\N\rightarrow P$ telle que :
	\begin{itemize}
		\item f(k) = $P_k$
		\item f calculable
		\item k (numéro d'un programme) et $P_k$ sont deux représentations 
			distinctes d'un même objet.
	\end{itemize}
\end{myprop}

% subsection programmes_et_fonctions (end)

\subsection{Existence de fonctions non calculable}
\label{sub:existence_de_fonction_non_calculables}
Il existe beaucoup de fonctions non calculables, car le nombre de fonctions de $\N$ 
dans $\N$ est non dénombrable (Démo par Cantor lors d'un TP). Or le nombre de 
programmes Java est dénombrable. Donc il y a beaucoup de fonctions qui ne sont 
pas calculables.

\paragraph{} On va s'intéresser qu'aux fonctions qui sont définies par une table 
finie ou une table infinie que l'on peut décrire de façon finie 
(on n'est pas capable d'écrire une définition infinie). Il en existe une infinité 
dénombrable.

\paragraph{} On va maintenant montrer que ce n'est pas parce qu’une fonction 
est définie par une table finie qu'elle est nécessairement calculable (exemple la 
fonction halt qui détermine si un programme se termine ou non).

% subsection existence_de_fonction_non_calculables (end)

\subsection{Problème de l'arrêt}
\label{sub:probl_me_de_l_arr_t}

\begin{mydef}[halt]
	halt est la fonction : P x $\N$ $\rightarrow$ $\N$ telle que \\
	\begin{tabular}{rl}
	  halt(n, x) = 1 & si $P_n(x)$ se termine \\
	  halt(n, x) = 0 & sinon \\
	  ou &\\
	  halt(n, x) = 1 & si $\phi_n(x)\neq \perp$ \\
	  halt(n, x) = 0 & sinon \\
	\end{tabular}
\end{mydef}

\begin{myprop}
	halt est une fonction bien définie, totale et sa table est infinie, mais décrite 
	de manière finie. Or on va montrer que halt n'est pas calculable par 
	diagonalisation (comme pour la démonstration de Cantor).\\
\end{myprop}

\begin{myrem}
	Attention, juste dire qu'on ne sait pas écrire un programme qui calcule
	halt ne prouve pas qu'on ne sait pas calculer halt. En effet, comme vu
	dans le chapitre 1, le programme existe est différent de savoir écrire
	le programme.
\end{myrem}

\begin{mytheo}[halt]
	halt n'est pas calculable
\end{mytheo}

\paragraph{Démonstration :}
On suppose halt calculable. 
\begin{enumerate}
	\item On peut donc construire une table infinie définissant la fonction
		halt : \\
		\begin{tabular}{|c||c|c|c|c|c|c|}
			\hline
			& 0 & 1 & 2 & ... & k & ... \\
			\hline
			$p_0$ & $halt(0,0)$ & $halt(0,1)$ & $halt(0,2)$ & ... & $halt(0,k)$ & ... \\
			$p_1$ & $halt(1,0)$ & $halt(1,1)$ & $halt(1,2)$ & ... & $halt(1,k)$ & ... \\
			$p_2$ & $halt(2,0)$ & $halt(2,1)$ & $halt(2,2)$ & ... & $halt(2,k)$ & ... \\
			: & : &:& : & : & : &:\\
			$p_k$ & $halt(k,0)$ & $halt(k,1)$ & $halt(k,2)$ & ... & $halt(k,k)$ & ... \\
			: & : &:& : & : & : &:\\
			\hline
		\end{tabular}
	\item Sélection de la diagonale 
		\[ diag :halt(0,0),halt(1,1),...,halt(k,k),... \]	
		\[diag(n) = halt(n,n)\]
	\item Modification de cet élément diag pour obtenir
		$diag'(n) =$ 
		\begin{tabular}{c}
			1 si halt(n,n) = 0\\
			$\perp$ si halt(n,n) = 1\\
		\end{tabular}\\
		$diag'$ est calculable, car halt est calculable (il y a moyen
		d'écrire un programme qui calcul $diag'$ en utilisant $diag$)
	\item Contradiction :\\
	       	Donc il existe un programme $P_d$ qui calcule
		$diag'$.
		$diag'(d) =$ 
		\begin{tabular}{c}
			1 si halt(d,d) = 0\\
			$\perp$ si halt(d,d) = 1\\
		\end{tabular}
		Mais, 
		\begin{itemize}
			\item Si $diag'(d)= 1$ $\\
			\Rightarrow \  halt(d,d) = 0 \\
			\Rightarrow \ P_d(d)$ ne se termine donc pas $ \\
			\Rightarrow diag'(d)$ ne se termine pas $ \\
			\Rightarrow diag'(d) = \perp$ or on a supposé que $diag'(d) = 1$ $ \\
			\Rightarrow $
			Contradiction.

			\item Si $diag'(d)= \perp$ $\\
			\Rightarrow \  halt(d,d) = 1 \\
			\Rightarrow \ P_d(d)$ se termine $ \\
			\Rightarrow diag'(d)$ termine $ \\
			\Rightarrow diag'(d) = 1$ or on a supposé que $diag'(d) = \perp$ $ \\
			\Rightarrow $
			Contradiction.
		\end{itemize}
	\item Conclusion : $diag'$ n'est pas calculable $ \Rightarrow $ $diag$
	n'est pas calculable $ \Rightarrow $ halt n'est pas calculable.

\end{enumerate}

\paragraph{Conclusion} Il n'existe pas d'algorithme qui détermine si n'importe 
quel programme $P_n$ se termine ou non. Mais dans certains formalismes qui ne 
sont pas des modèles complets la fonction halt de ce formalisme est calculable.
Par exemple un langage qui ne permet de calculer 
que des fonctions totales (exemple java sans aucune boucle)
, halt est calculable (halt retourne toujours 1). \\

De plus, il faut faire attention, car ce n'est pas parce que halt n'est pas 
calculable que pour un programme donné k, $halt(k,x)$ est non calculable. Par 
exemple $halt(32,123)$ est une fonction constant donc calculable (ce n'est pas 
pour autant qu'on est capable d'écrire l'algorithme), $halt(32,x)$ peut-être 
calculable, mais ça dépend du 
programme 32, par exemple si celui-ci est constant.

\begin{myrem}
	Cette partie du cours est très importante, car on a trouvé un 
	"trou dans le mur des fonctions calculables" et on va étendre le trou (métaphore
	de Mr Deville). C'est-à-dire que maintenant on va utiliser halt pour montrer 
	que d'autres fonctions sont calculables/non calculable. Par exemple 
	par réduction par rapport à halt.
\end{myrem}

Il existe donc au moins un ensemble non récursif
K.

\begin{mydef}[K]
	K = 
	\begin{tabular}{l}
		\{n|(n,n)$\in$ HALT\}\\
		\{n| halt(n,n)=1\}\\
		\{n| $P_n(n)$ se termine\} \\
	\end{tabular}
	K est donc l'ensemble des programmes n, $P_n$, qui
	se termine pour l'entrée n.
\end{mydef}
	
\begin{mydef}[HALT]
	HALT est l'ensemble des programmes k qui se termine pour l'entrée x, 
	\[ HALT = \{(n,x)|P_n(x)\text{se termine}\}\]
\end{mydef}

\begin{myprop}
	K et HALT ne sont pas récursifs
\end{myprop}
	
\begin{myprop}
	K et HALT sont récursivement énumérables (car il suffit de lancer le 
	programme et s’il retourne quelque chose il se termine sinon on ne sait 
	pas)
\end{myprop}
	
\begin{myprop}
	$\stcomp{HALT}$ n'est pas récursivement énumérable sinon HALT 
		serait récursif.
\end{myprop}
	
\begin{myprop}
	$\stcomp{K}$ n'est pas récursivement énumérable
\end{myprop}
	

TODO insérer le schéma sur les fonctions et les ensembles

\begin{mydef}[Un ensemble co-récursivement énumérable] est un ensemble dont le 
	complément est récursivement énumérable. Par exemple $\stcomp{HALT}$. On peut 
	en déduire que si un ensemble est récursivement énumérable et co-récursivement 
	énumérable alors il est récursif.
\end{mydef}

% subsection probl_me_de_l_arr_t (end)

\subsection{Insuffisance des fonctions totales}
\label{sub:insuffisance_des_fonctions_totales}
Comme on a vu qu'il était possible de calculer halt dans un modèle qui
ne permet de calculer que des fonctions totales. On se pose la question de 
pourquoi on n'utilise pas un tel modèle pour lequel la fonction halt est
calculable (pour un tel modèle halt retourne toujours 1.
De plus les fonctions "pratiques" sont 
des fonctions totales. Mais on va montrer qu'un tel modèle nous restreint 
beaucoup sur ce qu'on peut calculer.

\begin{myexem}
	Un tel modèle est par exemple BLOOP (défini plus loin) ou encore 
	Java, mais sans boucle donc par intuition on se doute qu'il y a 
	beaucoup de choses qu'on ne peut pas calculer.
\end{myexem}

\begin{mydef}
	Posons Q un langage (\textbf{non trivial}) dont tous les programmes se terminent et pour 
	lequel il existe un interpréteur calculable, interpret(n,x)=$\phi'_n$.
\end{mydef}
	
\begin{mydef}
	$\phi'_k$ est la fonction calculée par le programme $Q_k$.
\end{mydef}

\begin{myprop}
	 L'interpréteur est une fonction totale.
\end{myprop}

\begin{mytheo}[Hoare-Allison]
	\label{Hoare_Allison}
	interpret(n,x) n'est pas calculable dans Q.\\
\end{mytheo}

\paragraph{Démonstration :}
On suppose interpret calculable. 
\begin{enumerate}
	\item On peut donc construire une table infinie définissant la fonction
		interpret : \\
		\begin{tabular}{|c||c|c|c|c|c|c|}
			\hline
			& 0 & 1 & 2 & ... & k & ... \\
			\hline
			$Q_0$ & $interpret(0,0)$ & $interpret(0,1)$ & $interpret(0,2)$ & ... & $interpret(0,k)$ & ... \\
			$Q_1$ & $interpret(1,0)$ & $interpret(1,1)$ & $interpret(1,2)$ & ... & $interpret(1,k)$ & ... \\
			$Q_2$ & $interpret(2,0)$ & $interpret(2,1)$ & $interpret(2,2)$ & ... & $interpret(2,k)$ & ... \\
			: & : &:& : & : & : &:\\
			$Q_k$ & $interpret(k,0)$ & $interpret(k,1)$ & $interpret(k,2)$ & ... & $interpret(k,k)$ & ... \\
			: & : &:& : & : & : &:\\
			\hline
		\end{tabular}
	\item Sélection de la diagonale 
		\[diag(n) = interpret(n,n)\]
	\item Modification de cet élément diag pour obtenir
		$diag'(n) = interpret(n,n)+1$ 
		$diag'$ est calculable, car interpret est calculable dans Q (il y a moyen
		d'écrire un programme qui calcule $diag'$ en utilisant $diag$)
	\item Contradiction :\\
	       	Donc il existe un programme $Q_d$ qui calcule
		$diag'(d) = interpret(d,d)+1$ (par construction).
		Mais, par définition $diag'(d) = \phi_d(d) = interpret(d,d)$.
		En effet, calculer $\phi_d(d)$ revient à interpréter le programme
		d avec la donnée d.
	\item Conclusion : $diag'$ n'est pas calculable $ \Rightarrow $ $diag$
	n'est pas calculable $ \Rightarrow $ interpret n'est pas calculable
dans Q.
\end{enumerate}

\begin{myrem}
	Si on toutes les fonctions calculées par les programmes de Q n'étaient
	pas totales, alors ça n'aurait pas posé de problème, car $interpret(d,d)$
	ne se serait pas terminé or un programme qui ne se termine pas +
	quelque chose, reste un programme qui ne se termine pas.
\end{myrem}



\subsubsection{Implication du théorème \ref{Hoare_Allison}, Hoare Allison }

\begin{myprop}
	Si un langage (\textbf{non trivial}) ne permet que le calcul de fonction total alors :
	\begin{itemize}
		\item l'interpréteur de ce langage n'est pas calculable dans ce langage
		\item il existe des fonctions totales non programmables dans ce langage
		\item ce langage est \bf{restrictif}
	\end{itemize}
\end{myprop}
	
\begin{myprop}
	Si on peut programmer l'interpréteur d'un langage L dans L alors il est
	impossible de programmer la fonction halt de L car celle-ci n'est pas calculable. 
\end{myprop}

\begin{myprop}
	Dans un langage de programmation, il est donc impossible que 
	l'interpréteur et la fonction halt (de ce langage) puissent être programmés dans ce langage.
\end{myprop}

\begin{myprop}
	Si on veut pouvoir programmer toutes les fonctions 
	totales dans un langage, le langage doit permettre la programmation de 
	fonctions non totales.
\end{myprop}

\begin{myprop}
	L'ensemble \{n| $\phi_n$ est totale\} n'est pas récursif. (sinon on 
	saurait créer un langage qui ne calcule que des fonctions totales??)
\end{myprop}

\begin{mytheo}[fonction universelle]
	La fonction universelle (c'est-à-dire l'interpréteur) est $\theta(n,x)$ (programme $P_z$) tel que :
	\[ \exists z \forall n,x : \theta(n,x) = \phi_n(x)\]	
\end{mytheo}

% subsection insuffisance_des_fonctions_totales (end)

\subsection{Extension de fonctions partielles}
\label{sub:extension_de_fonctions_partielles}

\begin{mytheo}
	Il existe une fonction partielle calculable g telle 
	qu'aucune fonction totale calculable n'est une extension de g.
\end{mytheo}

\begin{myrem}
	Ca implique que si on a une fonction partielle g, il n'est pas 
	toujours possible de créer une fonction totale f qui étend g
	tel que en dehors du domaine de g, f retourne un code d'erreur.
\end{myrem}
	
% subsection extension_de_fonctions_partielles (end)

\subsection{Théorème de Rice}
\label{sub:th_or_me_de_rice}

Soit A $\subseteq$ $\N$

\begin{mytheo}[Rice]
	Si $A$ récursif et $A\neq \emptyset$ et $A \neq \N$ \\
	Alors $\exists i \in A$ et $\exists j \in \N \setminus A$ tels que $\phi _i = \phi _j$
\end{mytheo}

On utilise le plus souvent le théorème de Rice en ayant recourt à sa contraposée:

\begin{mytheo}[Rice (contraposée)]
	Si $\forall  i \in A$ et $\forall j \in \stcomp{A}$ on a $\phi_i \neq \phi_j$ \\
	Alors $A$ non-récursif ou $A = \emptyset$ ou $A = \N$
\end{mytheo}

Dans de nombreux cas, on peut garantir $A \neq \emptyset$ et $A \neq \N$, ce qui permet de se servir de la contraposée pour démontrer qu'un ensemble est non-récursif sans utiliser la preuve par diagonalisation.

\paragraph{Démonstration : }
On a $\forall i \in A$ et $\forall j \in \stcomp{A}$ tel que $\phi_i \neq
\phi_j$\\
Supposons $A$ récursif, $A=\emptyset$ et $A\neq \N$\\
On va montrer que HALT est récursif, car on peut construire un programme qui 
décide HALT, alors qu'on sait que HALT n'est pas récursif.

\begin{enumerate}
	\item Construisons le programme $P_k$
\begin{lstlisting}
while true do;				
\end{lstlisting}
	$\forall x \ \phi_k(x) = \perp$
	\item $\stcomp{A}\neq \emptyset$ car $A \neq \N$,
	supposons $k\in \stcomp{A}$ (hypothèse sans importance, car montrer que
	$A$ ou $\stcomp{A}$ est non récursif revient au même, car $A$ non
	récursif $ \Leftrightarrow $ $\stcomp{A}$ non récursif) \\
	\item $A\neq \emptyset$ par hypothèse, supposons $m\in A$
	\item $\phi_i \neq \phi_j$ et ce $\forall i \in A, \forall j \in \stcomp{A}$ par hypothèse donc
		$\phi_m \neq \phi_k$
	\item Construisons un programme $P(z)$ qui calcule la fonction $g(z)$, 
		$P(z) \equiv $
\begin{lstlisting}
P_n(x);
P_m(z);
\end{lstlisting}
	\begin{myrem}
		On sait que si un programme calcule une fonction $
		f(x)=\perp \ \forall x$ alors ce programme doit être dans $\stcomp{A}$ car
		$f(x) =\phi_k(x)$.

		Or 
		\begin{itemize}
			\item soit notre programme $P(z)$ ne se termine pas $\forall
			z$, car $P_n(x)$ ne se termine pas et donc $g(z) =
			\phi_k(z)$.

		\item soit notre programme $P(z)$ calcule $\phi_m(z)$ or on
			sait que $m\in A$.
		\end{itemize}
		Donc en résumé si $P_n(x)$ ne se termine pas il sera dans
		$\stcomp{A}$ sinon il sera dans $A$.
	\end{myrem}	
	Un programme qui décide HALT $halt(n,x) \equiv $
\begin{lstlisting}
construire P(z);
d <- numero de P(z);
if d in A then print(1);
else print(0);
\end{lstlisting}
	\item Contradiction, car HALT n'est pas récursif.
	\item Conclusion: $A$ n'est pas récursif.
\end{enumerate}

\paragraph{} On est intéressé par l'analyse des propriétés d'un programme. Est-ce que ces propriétés peuvent être déterminées par un 
algorithme? On va utiliser le théorème de Rice pour différencier les propriétés 
qu'il est possible de déterminer par un algorithme de celles pour lesquelles ce 
n'est pas possible.

\paragraph{}Pour ça, considérons $A$ comme étant l'ensemble des programmes qui 
respectent une propriété. Par exemple $A_1 = \{i| \phi_i \text{ est total}\}$ ou 
$A_2=\{i|\phi_i = f\}$,... (il y a plein d'exemples dans le cours).

\paragraph{Analyse} 
\begin{itemize}
	\item Si la propriété est vérifiée par certains programmes, mais pas tous, 
		et qu'elle est décidable, alors il existe deux programmes calculant la 
		même fonction, mais l'un vérifie la propriété, et l'autre pas.

	\item Si la propriété est vérifiée par un programme, mais pas tous, 
		alors cette propriété ne peut-être décidée pas un algorithme.

	\item S'il existe un algorithme permettant de déterminer si un 
		programme quelconque calcule une fonction ayant cette propriété, 
		alors toutes les fonctions calculables ont cette propriété ou 
		aucune fonction calculable n'a cette propriété.
		
	\item Aucune question relative aux programmes, vu sous l'angle de la 
		fonction qu'ils calculent, ne peut être décidée par 
		l'application d'un algorithme.
		
	\item Les propriétés intéressantes d'un programme concernant la 
		fonction qu'il calcule, non pas sa forme,
		sont non calculables.
\end{itemize}


% subsection th_or_me_de_rice (end)

\subsection{Théorème de la paramétrisation}
\label{sub:th_or_me_de_la_param_trisation}

\subsubsection{Transformation de programmes}
\label{ssub:transformation_de_programmes}
\begin{mydef}[Transformateur de programme]
	On peut voir une fonction f: $\N \rightarrow \N$ comme une fonction qui prend 
	le numéro d'un programme et qui retourne le numéro d'un autre programme f: $P 
	\rightarrow P$. Donc on peut voir $P_k$, le programme qui calcule f comme un 
	transformateur de programme. En effet, $P_k$ prend un programme en entrée et 
	retourne un programme qui peut être différent.
\end{mydef}

\begin{mytheo}[S-m-n] 
	\label{S-m-n}Pour tout $m,n \geq 0$, \\
	il existe une fonction totale calculable $S^m_n : \N^{m+1} \rightarrow 
	\N$ \\
	telle que pour tout $k$ ($\phi_k$ est calculable),
	$$ \phi^{(n+m)}_k(x_1,...,x_n,x_{n+1},...,x_{n+m}) = 
	\phi^{(n)}_{S^m_n(k,x_{n+1}, ...,x_{n+m})} (x_1,...,x_n)$$
\end{mytheo}

\paragraph{Démonstration}
	Pour prouver que $S^m_n$ existe, on va montrer comment construire un programme qui 
	calcule  $S^m_n(k,x_{n+1}, ...,x_{n+m})$.\\
	Tout d'abord, comme $\phi_k$ est calculable, il existe un programme  
	$P_k(x_1,x_2,...,x_{n+m})$.\\
	On peut donc construire un programme $Q(x_1,...,x_n)$ qui calcule 
	$P_k(x_1,x_2,...,x_{n+m})$.\\
	$x_1,...,x_n$ restent des arguments du programme,
	tandis que $x_{n+1},...,x_{n+m}$ deviennent des valeurs fixées.\\
	Notre programme qui calcule $S^m_n(k,x_{n+1}, ...,x_{n+m})$ n'a plus 
	qu'à retourner le numéro du programme $Q$.\\
       	En résumé, $S^m_n(k,x_{n+1},
	...,x_{n+m}) \equiv$
	\begin{lstlisting}
construire Q(x1,x2,...,xn) = P_k(x1,x2,...xn,...,xn+m);
d <- numero du programme Q;
print(d);
	\end{lstlisting}

\begin{mytheo}[S]
	C'est la propriété S-m-n affaiblie.
	\[ \forall \ k \ \exists \ S \ \text{(totale calculable)} : \phi_k(x,y)=\phi_{S(x)}(y)\]
	% Lena : j'ai plutôt ceci (c'est équivalent)
	% $$ \forall \text{ programme } P, \exists S \text{ totale calculable }:
	% P(x,y) \equiv \left[S(y) \right](x) $$
\end{mytheo}

\paragraph{Démonstration}
	Par le théorème \ref{S-m-n} (S-m-n),
	\[ \exists \ S \text{ (totale calculable) } \forall \ k : \phi_k(x,y)=\phi_{S(k,x)}(y)\]
	\[ \forall \ k \ \exists \ S \ \text{ (totale calculable) } : \phi_k(x,y)=\phi_{S(k,x)}(y)\]
	\[ \Rightarrow \forall \ k \ \exists \ S : \phi_k(x,y) =\phi_{S(k,x)}(y) \]
	\begin{align}
		\Rightarrow S(k,x) &= \phi_{S}(k,x) \text{ (S est totale calculable)}\\
		&= \phi_{S'(S,k)}(x) \text{ (S-m-n)}\\
		&= \phi_{k'}(x) \text{ (renomage de } S'(S,k) \text{ en } k' \text{ )}\\
		&= S"(x)
	\end{align}
	\[ \Rightarrow \forall \ k \ \exists \ S" \ \text{(totale calculable)} :
       	\phi_k(x,y)=\phi_{S"(x)}(y)\]

\begin{myrem}
	On peut voir le théorème \ref{S-m-n}, S-m-n, comme : \\
	Étant donné $m,n \geq 0$\\
	il existe un transformateur de programme, $S^m_n$, qui recevant comme 
	données : un programme $P_k$ à n+m arguments et m valeurs $v_1,...,v_m$
	fournit comme résultat: un programme $P$ à n arguments tel que 
	$P(x_1,...,x_n)$ calcule la même fonction que 
	$P_k(x_1,...,x_n,,v_1,...,v_m)$ (Ce programme effectue une projection)
\end{myrem}

\begin{myrem}
	On peut donc voir la transformation de programmes $S^m_n$ comme un 
	programme qui particularise un autre programme à m+n argument en rendant 
	constant les m derniers paramètres.
\end{myrem}

\subsection{Théorème du point fixe}
\label{sub:th_or_me_du_point_fixe}
\begin{mytheo}[Point fixe] 
	\label{point-fixe}Soient $n \geq 0$ et f : fonction totale 
	calculable, il existe k tel que $\phi^{(n)}_k = \phi^{(n)}_{f(k)}$  
\end{mytheo}

%TODO Démonstration avec les lapins (les 3 lapins qui permettent
%de commencer la démonstration ne sont pas super intuitifs)
\begin{myrem}
	Le théorème \ref{point-fixe} n'est pas très intuitif. Mais on peut le 
	voir comme : quelque soit un transformateur de programme T qui calcule f 
	(n'importe quelle fonction totale calculable peut être vu comme un transformateur 
	de programme), \\
	il existe deux programmes $P_k$ et $P_j$ tels que 
	\begin{itemize}
		\item $P_j$ est la transformation de $P_k$ via T,
		\item $P_k$ et $P_j$ calcule la \textbf{même} fonction.
	\end{itemize}
\end{myrem}

\paragraph{Démonstration :}
Pour commencer, on va poser 3 "lapins" :
\begin{enumerate}
	%\item $h(u,v) =$
	%	\begin{tabular}{c}
	%		$\phi_{\phi_{u(u)}}(v)$ si $\phi(u)\neq \perp$\\
	%		$\perp$ sinon
	%	\end{tabular}\\
		
	\item
	$ h(u,v) = \left\{
	\begin{array}{l l}
		\phi_{\phi_{u(u)}}(v) & \quad \text{si $\phi_u(u)\neq \bot$}\\
    	\bot & \quad \text{sinon}
	\end{array} \right.$
		
		$h$ est calculable 
		\begin{myrem}
			on peut créer un programme qui calcule $h$
\begin{lstlisting}
a = P_u(u)
return P_a(v)
\end{lstlisting}
		\end{myrem}
		
	\item $h(u,v)=\phi_{S(u)}(v)$\\
	 $S$ est totale calculable, on a donc la propriété S (propriété S-m-n affaiblie).
	 
	\item $g(u)=f(S(u))$\\
	 $g$ est totale calculable car $S$ et $f$ le sont ($f$
		est la fonction donnée dans le théorème).
		\[ \exists k' \cdot \phi_{k'}(u) =g(u)=f(S(u)) \]
\end{enumerate}
On a que $k'$ est une constante et par le lapin 2 :
\[h(k',v) = \phi_{S(k')}(v)\]
Par le lapin 1 et, car $g=\phi_k'$ est une fonction totale calculable, on a :
\[h(k',v) = \phi_{\phi_k'(k')}(v)\]
Par le lapin 3 on a que $\phi_{k'}(u) = g(u)=f(S(u))$ donc :
\[h(k',v) = \phi_{f(S(k'))}(v)\]
C'est à dire :
\[ \phi_{f(S(k'))}(v) =\phi_{S(k')}(v) \]
Si on pose que $S(k')=k$ on a bien 
\[ \phi_{k}(v) = \phi_{f(k)}(v) \]
Ce qui conclut notre démonstration.

\begin{myrem}[Démonstration de K grâce au point fixe]
	On peut démontrer que K n'est pas récursif.\\
	Posons 3 fonctions :
	\begin{itemize}
		\item $\phi_i(x) = \bot \quad \forall \ x$
		\item $\phi_j(x) = x \quad \forall  \ x$
		%\item $f(x) = $ 
		%	\begin{tabular}{l}
		%		i si $x\in K$\\
		%		j si $x\notin K$\\
		%	\end{tabular}
		\item $ f(x) = \left\{
		\begin{array}{l l}
			i & \quad \text{si $x\in$ K}\\
    		j & \quad \text{si $x\notin$ K}
		\end{array} \right.$
	\end{itemize}
	$f$ décide K. Supposons que $f$ est totale calculable. \\
	$ \Rightarrow \exists \ k$ tel que $\phi_k = \phi_{f(k)}$ (par le théorème
du point fixe)\\
	On a alors 2 cas possibles :
	\begin{itemize}
		\item Soit $\phi_k(k)=\bot$
			\[ \Rightarrow k \notin K\]
			\[ \Rightarrow f(k)=j \notin K\]
			\[ \Rightarrow \phi_k = \phi_j \]
			\[ \Rightarrow \phi_k(k) \neq \bot\]
			Ce qui implique une contradiction
		\item Soit $\phi_k(k) \neq \bot$
			\[ \Rightarrow k \in K\]
			\[ \Rightarrow f(k)=i \in K\]
			\[ \Rightarrow \phi_k = \phi_i \]
			\[ \Rightarrow \phi_k(k) = \bot\]
			Ce qui implique une contradiction.
	\end{itemize}
	Donc il n'existe pas de fonction calculable qui décide K $ \Rightarrow$ K n'est pas récursif.
\end{myrem}

\subsection{Autres problèmes non calculables}
\label{sub:autres_probl_mes_non_calculable}

\begin{mydef}[Problème de correspondance de Post] Soit deux listes U et V 
	de mots non vides sur un alphabet $\Sigma$ : 
	\begin{itemize}
		\item U = ${u_1,u_2,...,u_k}$
		\item V = ${v_1,v_2,...,v_k}$
	\end{itemize}
	Le problème consiste à décider s’il existe une suite d'entiers 
	$i_1,i_2,..,i_n$ telle que les mots $u_{i1},u_{i_2},...,u_{in}$ et 
	$v_{i1},v_{i_2},...,v_{in}$ soient \textbf{identiques}. \\
	Pour démontrer l'indécidabilité de ce problème, Post à introduit un 
	nouveau modèle, la machine de Post qui ressemble à une machine de Turing.
\end{mydef}

% en français, on écrit "diophantiennes", an anglais "diophantines"
\begin{mydef}[Problème des équations diophantiennes] Décider si une équation 
	polynomiale de degré supérieur ou égal à 4 possède une solution entière.
\end{mydef}

Il n'existe pas d'algorithme résolvant ces problèmes. Il existe beaucoup
d'autres problèmes non calculables. Il y a d'autres exemples sur les grammaires dans le cours.
% subsection autres_probl_mes_non_calculable (end)

\subsection{Nombres calculables}
\label{sub:nombres_calculables}

\begin{mydef}[Nombre réel]
	Un nombre réel est défini comme la limite d'une suite (convergente) de 
	nombres rationnels: $\lim_{n \rightarrow +\infty} |x-s(n)| = 0 $ ou s’est 
	une fonction totale
\end{mydef}

\begin{mydef}[Nombre réel calculable]
	Un nombre réel x est calculable s’il existe une fonction totale 
	calculable $s$ tel que $\lim_{n \rightarrow +\infty} |x-s(n)| \leq 2^{-n}$
\end{mydef}

\begin{myrem}
	Donc un nombre est calculable s'il existe un programme qui peut 
	l'approximer aussi près que l'on veut. Par exemple $\pi$ et $e$ sont 
	calculable
\end{myrem}

\begin{myprop}
	L'ensemble des nombres réels calculables est énumérable, car on peut énumérer les 
	fonctions totales calculables.	
\end{myprop}

\begin{myprop}
	Il existe des nombres réels non calculables.
\end{myprop}

\begin{myprop}
	Il existe des nombres réels non calculables qui peuvent être définis de 
	manière finie.
\end{myprop}

% subsection nombres_calculables (end)

\subsection{Conclusion}

Le théorème S-m-n permet de démontrer le théorème du point fixe.
Le théorème du point fixe est un résultat central de la calculabilité. Il 
implique le théorème de Rice, la non-récursivité de K et la non-calculabilité 
de la fonction halt.

% subsection conclusion (end)
% section r_sultats_fondamentaux (end)

\section{Modèle de la calculabilité}
\label{sec:mod_le_de_la_calculabilit_}

\subsection{Familles de modèles}
\label{sub:fammilles_de_mod_les}

Il y a deux grandes familles de modèles :
\begin{itemize}
	\item Modèle de calcul (calcule une réponse)
	\item Modèle de langages (décide l'appartenance à un ensemble)
\end{itemize}

\subsubsection{Modèle de calcul}
\label{ssub:mod_le_de_calcul}
L'objectif est de modéliser le concept de fonctions calculables, processus de 
calcul, algorithme effectif.

On peut encore classer les modèles de calcul en 2 catégories, les 
modèles déterministes et les modèles non déterministes.

\begin{mydef}[Modèles déterministes] une seule exécution possible
\end{mydef}

\begin{mydef}[Modèles non déterministes] il existe plusieurs exécutions 
	possibles
\end{mydef}

On va voir les modèles de calcul suivant : 
\begin{itemize}
	\item Automate fini
	\item Automate à pile
	\item Machine de Turing
	\item Langages de programmation
	\item Lambda calcul
	\item Fonction récursive
\end{itemize}
Mais il en existe beaucoup d'autres.
% subsubsection mod_le_de_calcul (end)

\subsubsection{Modèle de langage}
\label{ssub:mod_le_de_langage}
Un langage est défini pas une grammaire formelle. L'objectif est de modéliser 
une classe de langage. Le langage est alors soit un ensemble récursif ou un 
ensemble récursivement énumérable.

% subsubsection mod_le_de_langage (end)
% subsection fammilles_de_mod_les (end)

\subsection{Langages de programmation}
\label{sub:langages_de_programmation}
C'est un modèle possible de la calculabilité. Pour définir un langage de 
programmation comme modèle de la calculabilité, il faut définir : 
\begin{itemize}
	\item Syntaxe du langage
	\item Sémantique du langage
	\item Convention de représentation d'une fonction par un programme
\end{itemize}

On se pose la question de savoir s'il y a des langages plus puissants que 
d'autres. On va montrer que tous les langages complets sont équivalents. (Et la 
plupart des langages sont complets.)

\paragraph{} Mais, il existe aussi des langages qui ne sont pas complets comme le 
langage BLOOP (bounded loop).

\begin{mydef}
	BLOOP : Sous ensemble de Java qui ne calcule que des fonctions totales. 
	(pas de boucle while, boucle for mais sans modification du compteur 
	dans le for, pas de goto en arrière, pas de fonctions récursives)
\end{mydef}

BLOOP a donc toutes les propriétés qui découlent du chapitre précédent:

\begin{myprop}
	Tous les programmes BLOOP se terminent\\
	$ \Leftrightarrow$ BLOOP ne calcule que des fonctions totales\\
	$ \Leftrightarrow$ BLOOP ne calcule pas toutes les fonctions totales\\
	$ \Leftrightarrow$ il existe un compilateur des programmes BLOOP (Java)\\
	$ \Leftrightarrow$ l'interpreteur est une fonction totale non calculable en
BLOOP (Hoare-Allison)\\
	$ \Leftrightarrow$ BLOOP n'est pas un modèle complet de la calculabilité\\
\end{myprop}

% subsection langages_de_programmation (end)

\subsubsection{Langage de programmation non déterministe}
\label{ssub:langague_de_programmation_non_d_terministe}

\begin{myrem}
	Il est difficile d'avoir de l'intuition sur cette partie. On peut 
	voir un programme ND comme un programme qui produit des résultats 
	différents d'une exécution à l'autre. On peut représenter toutes 
	les exécutions possibles du programmes sous forme de branches d'un
	arbre. Pour analyser la complexité, on ne 
	considère que la profondeur de l'arbre (longueur de la branche
	la plus longue).
\end{myrem}

On va un introduire un nouveau langage ND-Pascal qui est le langage Java 
auquel on ajoute le non-déterminisme sous la forme d'une fonction 
prédéfinie $choose(n)$. Celle-ci retourne un entier compris entre $0$ et $n$ et elle 
est non déterministe.

On peut voir un programme ND de 2 manières différentes :
\begin{enumerate}
	\item Il calcule une relation plutôt qu'une fonction
	\item C'est un moyen de décider si un élément appartient à un 
		ensemble
\end{enumerate}
On considère l'approche 2 en calculabilité.

\begin{mydef}[ND-récursif]
	Un ensemble $A \subseteq \N$ est ND-récursif s’il existe un 
	ND-programme tel que lorsqu'il reçoit comme donnée n'importe quel nombre 
	naturel $x$ \\
	\begin{tabular}{l}
	si $x \in A$ alors il existe une exécution fournissant tôt ou tard 
	comme résultat 1 \\
	si $x \notin A$ alors toutes les exécutions fournissent tôt ou tard 
	comme résultat 0 \\
	\end{tabular}
\end{mydef}

\begin{mydef}[ND-récursivement énumérable]
	Un ensemble $A \subseteq \N$ est ND-récursivement énumérable s’il existe un 
	ND-programme tel que lorsqu'il reçoit comme donnée n'importe quel nombre 
	naturel $x$ \\
	\begin{tabular}{l}
	si $x \in A$ alors il existe une exécution fournissant tôt ou tard 
	comme résultat 1 \\
	si $x \notin A$ alors les exécutions possibles ne se terminent pas ou 
	retournent un résultat $\neq 1$ \\
	\end{tabular}
\end{mydef}

\begin{myprop}
	On peut simuler les exécutions d'un ND-programme à l'aide d'un programme 
	déterministe. (BFS dans l'arbre d'exécution)
\end{myprop}

\begin{myprop}
	Un ensemble est ND-récursif ssi il est récursif
\end{myprop}

\begin{myprop}
	Un ensemble est ND-récursivement énumérable ssi il est récursivement 
	énumérable
\end{myprop}

\subsection{Automates finis FA}
\label{sub:automates_finis}

\paragraph{Objectif :} Décider si un mot donné appartient ou non à un langage.

\paragraph{Utilisation :} Utilisé dans les interfaces pour les humains (par 
exemple, les distributeurs).

\subsubsection{Modèles des automates finis}
\label{ssub:mod_les_des_automates_finis}
Un automate fini est composé de :

\begin{itemize}
	\item $\Sigma$ : ensemble fini de symboles
	\item $S$ : ensemble fini d'états
	\item $s_0 \in S$ : état initial
	\item $A \subseteq S$ : ensemble des états acceptants
	\item $\delta: S \times \Sigma \rightarrow S$ : fonction de transition
\end{itemize}

\begin{myrem}
	On peut aussi représenter un automate fini à l'aide d'un diagramme 
	d'état.
\end{myrem}

\paragraph{Fonctionnement}
\begin{itemize}
	\item départ avec un état initial
	\item parcours des symboles du mot d'entrée, un à un
	\item à chaque symbole lu, l'état change (fonction de transition 
		$\delta$) en fonction de l'état courant et du symbole lu
	\item état final est l'état après avoir parcouru tous les symboles en 
		entrée
	\item l'état final peut-être acceptant ou non
\end{itemize}

\begin{myrem}
	Il n'y a donc pas de mémoire. De plus, un automate peut-être simulé 
	par un programme Java.
\end{myrem}

\begin{myprop}
	Un automate fini définit un ensemble récursif de mots $=\{m \ |\ m$ est 
		accepté par FA$\}$
\end{myprop}

\begin{myprop}
	Certains ensembles récursifs ne peuvent pas être reconnus par un 
	automate fini. Par exemple $L = \{ a^n b^n \ | \ n\geq 0\}$ (il me semble que 
	c'est par ce que ça nécessiterait un nombre infini d'états)
\end{myprop}

\begin{myprop}
	L'interpréteur des automates finis est calculable, mais ne peut pas être 
	représenté par un automate fini, car ce n'est pas un \textbf{modèle 
	complet} de la calculabilité (Hoare-Allison)
\end{myprop}

\begin{mydef}[Langage régulier] est un langage défini par une expression 
	régulière.
\end{mydef}

\begin{mydef}[Expression régulière] 
       	Dans le cours, la syntaxe d'une expression régulière est la suivante :
	\begin{description}
		\item[+] ou
		\item[.] concaténation
		\item[*] fermeture de Kleene\footnote{définit un groupe qui existe zéro, une ou plusieurs fois}
		\item[( )] répétition
	\end{description}
\end{mydef}
% subsubsection mod_les_des_automates_finis (end)

\subsubsection{Extension des automates finis}
\label{ssub:automate_fini_nd}
\paragraph{NDFA} On étend le modèle en permettant d'avoir plusieurs transitions possibles pour 
une paire <état,symbole>. Ce qui implique que plusieurs exécutions sont 
possibles. On a donc plus une fonction de transition mais on a maintenant une
relation de transition.

\paragraph{} De même que pour un ND programme, un mot est accepté par un NDFA 
s’il existe au moins une exécution ou l'état final est acceptant. Dans l'autre 
sens, un 
mot n'est pas accepté si aucune exécution ne se termine avec l'état final 
acceptant.

\begin{myprop}
	Si un ensemble récursif est défini par un NDFA, alors cet ensemble est 
	défini par un FA.
\end{myprop}

\begin{myprop}
	Un NDFA définit un ensemble récursif de mots.
\end{myprop}

\paragraph{Ajout de transitions vides $\epsilon$} On peut encore étendre le modèle NDFA en 
rajoutant une possibilité de transition sans lire de symbole (transition 
spontanée). Ça a la même puissance et les mêmes propriétés qu'un NDFA.

% subsubsection automate_fini_nd (end)

\subsection{Automate à pile PDA}
\label{sub:automate_pile}
C'est une extension du modèle des automates finis. On ajoute une mémoire avec 
la pile de symboles.
Les différences principales sont :
\begin{itemize}
	\item la transition entre états dépend du symbole lu et du symbole au 
		sommet de la pile
	\item	chaque transition peut enlever le sommet de la pile et empiler 
		de nouveaux éléments ou ne pas changer la pile.
\end{itemize}

\paragraph{Objectif :} Décider si le mot donné appartient ou non à un langage.

\paragraph{Utilisation :} Utilisé dans les compilateurs.

\paragraph{Composition :}
On rajoute $\Gamma$ et on change la fonction de transition en une nouvelle 
relation de transition.
\begin{itemize}
	\item $\Sigma$ : ensemble fini de symboles d'entrée
	\item $\Gamma$ : ensemble fini de symboles de pile
	\item $S$ : ensemble fini d'états
	\item $s_0 \in S$ : état initial
	\item $A \subseteq S$ : ensemble des états acceptants
	\item $\Delta \subset S \times \Sigma \times \Gamma \times S \times 
		\Gamma^*$ : relation de transition (finie)
\end{itemize}

\begin{myprop}
	Tout comme un NDFA, un PDA définit un ensemble récursif de mots (langage 
	récursif).
\end{myprop}

\paragraph{Convention :} 
\begin{itemize}
	\item Z est le symbole initial de la pile (pile vide)
	\item $\epsilon$ signifie qu’aucun symbole ne doit être lu pour cette 
		transition (symbole "vide")
	\item A, B / C : A est le symbole lu, B est le symbole au 
		sommet de la pile et C est ce qui va remplacer le 
		sommet de la pile (peut-être un xB pour 
		rajouter x sur la pile, $\epsilon$ pour retirer B du sommet de la pile, 
		ou juste B pour ne pas changer le sommet)
\end{itemize}

\begin{myprop}
	Certains ensembles récursifs ne peuvent pas être reconnus par un automate 
	à pile. Ex: L = $\{a^n b^n a^n | n\geq 1\}$
\end{myprop}

\begin{myprop}
	Les automates à pile sont plus puissants que les automates finis (ils 
	peuvent reconnaitre plus d'ensembles)
\end{myprop}

\begin{myprop}
	Ce n'est pas un modèle complet de la calculabilité donc par Hoare-
	Allison, l'interpréteur n'est pas calculable dans le modèle.
	% Lena : pas sûre du sens de l'implication
\end{myprop}

% subsection automate_pile (end)

\subsection{Grammaires et modèles de calcul}
\label{sub:grammaires_et_mod_les_de_calcul}

\paragraph{Objectif :}
Définition d'un langage (ensemble de mots) et à partir de la grammaire on peut 
générer/dériver les mots du langage.

\paragraph{Utilisation :} Utilisé pour la définition de langages de 
programmation, pour l'analyse du langage naturel...

\paragraph{Composition du modèle :}

\begin{itemize}
	\item $\Sigma$ : alphabet
	\item les éléments de $\Sigma$ sont des symboles terminaux
	\item autres symboles utilisés durant la dérivation : symboles non 
		terminaux (A,B, ..., <dig>,..)
	\item S : point de départ de la dérivation (symbole non terminal)
\end{itemize}

\begin{mydef}[Règle de production]
	On appelle un ensemble de règles de dérivation des règles de production.
\end{mydef}

\begin{myexem}
	\begin{itemize}
		\item $\Sigma ={0,1,2}$ 
		\item $S \rightarrow <Dig>$
		\item $<Dig> \rightarrow D$
		\item $D \rightarrow 0 | 1 |2 | \epsilon $ ($\epsilon$ signifie rien)
	\end{itemize}
\end{myexem}
TODO Exemple littéraux real en Java

\begin{mydef}[Dériver] Appliquer des règles de la grammaire pour vérifier 
	si une chaîne de symbole appartient au langage (on part d'une chaîne de symboles 
	et on vérifie les règles sur celle-ci).
\end{mydef}

\begin{mydef}[Inférer] Dérivation dans "le sens contraire", 
	c'est-à-dire, on part des règles de grammaire et on génère une chaîne 
	de symboles.
\end{mydef}

\begin{mydef}[Arbre syntaxique]
	Un arbre syntaxique permet de représenter la dérivation, chaque noeud 
	correspond à un symbole terminal ou non. Les arêtes correspondent à 
	l'application d'une règle. Il y a plusieurs nœuds enfants si la règle 
	"génère" plusieurs symboles.
\end{mydef}

\begin{myprop}
	On peut dériver de plusieurs façons équivalentes, leftmost (on dérive 
	toujours le plus à gauche d'abord), rightmost (contraire de leftmost) 
	ou  aucun des deux.
\end{myprop}

\subsubsection{Hiérarchie de Chomsky}
\label{ssub:hi_rarchie_de_chomsky}

Chomsky a défini 4 types de grammaires formelles. On peut les classer selon 
leur "puissance".

\begin{mydef}[Puissance d'une grammaire]
	Une grammaire A est plus puissante qu'une B si on peut définir plus 
	de langages avec A qu'avec B.
\end{mydef}

On peut aussi faire correspondre chaque type de grammaire avec un type de 
calcul permettant de reconnaitre un langage de cette grammaire.

\begin{tabular}{|c|c|c|}
	\hline	
	 Type & Type de grammaire & Modèle de calcul\\
	 \hline
	3 & régulière & Automate fini \\
	 \hline
	2 & hors contexte & Automate à pile \\
	 \hline
	1 & sensible au contexte & Machine de Turing à ruban fini \\
	 \hline
	0 & récursivement énumérable & Machine de Turing \\
	\hline
\end{tabular}

Chaque type de grammaire est défini par une règle de production A $\rightarrow 
$ B. Il y a des conditions différentes sur A et B selon le type de 
grammaire.
% subsubsection hi_rarchie_de_chomsky (end)

\subsubsection{Grammaires régulières}
\paragraph{Règle de production :} 
\begin{itemize}
	\item $A \rightarrow \omega B$
	\item $A \rightarrow \omega$
\end{itemize}

\paragraph{Conditions :}
\begin{itemize}
	\item  $\omega \in \Sigma^*$, c'est-à-dire $\omega$ est une chaîne de symboles 
	terminaux. 
	\item A et B sont des symboles non terminaux.
\end{itemize}

\begin{myexem}
	$S \rightarrow abS$ \\
	$S \rightarrow \epsilon$ \\
	Cette grammaire définit différents langages, par exemple $L1 = 
	\{(ab)^n \ | \ n \geq 0\}$. Ce langage peut-être aussi défini par une expression 
	régulière : $L1 = (ab)^*$.
\end{myexem}

\subsubsection{Grammaires hors contexte}
Cette grammaire est importante, car il suffit de lui rajouter la portée des 
variables pour définir la syntaxe d'un langage de programmation.

\paragraph{Règle de production :} 
\begin{itemize}
	\item $A \rightarrow \beta$
\end{itemize}

\paragraph{Conditions :}

\begin{itemize}
	\item  $\beta$ est une chaîne de symboles composée de symboles terminaux
	       	ou non
	\item A est un symbole non terminal
\end{itemize}

\begin{myexem}
	$S \rightarrow aSb$ \\
	$S \rightarrow \epsilon$ \\
	Un langage défini par cette grammaire est par exemple $L1 = \{a^nb^n|n 
		\geq 0\}$
\end{myexem}

\subsubsection{Grammaires sensibles au contexte}
\paragraph{Règle de production :} 
\begin{itemize}
	\item $\alpha \rightarrow \beta$
\end{itemize}

\paragraph{Conditions :}
\begin{itemize}
	\item $\alpha$ et $\beta$ sont des chaînes de symboles composées de 
		symboles terminaux ou non.
	\item $\beta$ contient au moins 
		autant de symboles que $\alpha$.
\end{itemize}

\begin{myexem}
	$S \rightarrow aSBA$ \\
	$S \rightarrow abA$ \\
	$AB \rightarrow BA$ \\
	$bB \rightarrow bb$ \\
	$bA \rightarrow ba$ \\
	$aA \rightarrow aa$ \\
	Un langage défini par cette grammaire est par exemple $L1 =
	\{a^nb^na^n|n \geq 0\}$
\end{myexem}

\subsubsection{Grammaires sans restriction}

\paragraph{Règle de production :} 
\begin{itemize}
	\item $\alpha \rightarrow \beta$
\end{itemize}

\paragraph{Conditions :}

\begin{itemize}
	\item $\alpha$ et $\beta$ sont des chaînes de symboles composées de 
		symboles terminaux ou non.
\end{itemize}

\begin{myexem}
	Il y a donc moyen de créer des règles qui bouclent : \\
	$\alpha \rightarrow \beta$ \\
	$\beta \rightarrow \alpha$\\
\end{myexem}

\subsection{Machines de Turing}
\paragraph{Intérêt :}Le modèle des machines de Turing est le modèle le plus 
simple, le plus élémentaire et le plus puissant possible (c'est un modèle
complet de la calculabilité). Il permet une définition précise de procédure, 
d'algorithme ou encore de calcul.

\paragraph{Composition "abstraite" :}
\begin{description}
	\item[Ruban] Suite de cases potentiellement infinie (des 2 côtés), mais à 
		chaque moment, le ruban nécessaire est fini
	\item[Tête] Une seule tête, sur une case qui peut écrire et lire la 
		case sur laquelle elle est
	\item[Contrôle] Dirige les actions/opérations
\end{description}

\subsubsection{Contrôle}
\label{ssub:contr_le}
Le contrôleur est composé d'un nombre d'états fini dont un état initial et un 
final. Il contient un programme (des instructions).

\begin{mydef}[Une instruction] est sous la forme 
	$$<q,c> \quad \rightarrow \quad <new_q, Mouv, new_c>$$
	\begin{itemize}
		\item $q$ : état courant
		\item $c$ : symbole sous la tête de lecture
		\item $new_c$ : symbole à écrire sous la tête de lecture
		\item $Mouv$ : G ou D, mouvement que la tête de lecture doit faire
		\item $new_q$ : le nouvel état
	\end{itemize}
\end{mydef}

% subsubsection contr_le (end)

\subsubsection{Modélisation}
Pour définir une machine de Turing, il faut :
\begin{itemize}
	\item $\Sigma$ : ensemble fini de symboles d'entrée
	\item $\Gamma$ : ensemble fini de symboles de ruban
	\item $S$ : ensemble fini d'états
	\item $s_0 \in S$ : état initial
	\item $stop \in S$ : état d'arrêt
	\item $\delta : S \times \Gamma \rightarrow S \times \{G,D\} 
	\times \Gamma$ : fonction de transition (finie)
\end{itemize}
Il faut aussi que $\Sigma \subset \Gamma$ et que B $\in \Gamma$ mais que B 
$\notin \Sigma$

\begin{mydef}
		B correspond au symbole blanc.
\end{mydef}

\subsubsection{Exécution}
Au départ il y a juste les données d'entrée sur le ruban. Sur les autres cases, il y a 
le symbole B. La tête de lecture se trouve sur la première case des données. Tant que 
c'est possible, on applique des instructions. Il y a 2 cas possibles pour l'arrêt: soit 
l'état devient stop, soit il n'y a plus d'instruction applicable.

 Le résultat est le contenu du ruban à l'état stop. Si la machine 
ne s'arrête pas sur l'état stop alors il n'y a pas de résultat.

\begin{mydef}[T-calculable] Une fonction $f$ est T-calculable s’ il existe une machine 
de Turing qui, 
	recevant comme donnée n'importe quel nombre entier $x$ fourni tôt ou tard 
	comme résultat $f(x)$ si celui-ci existe.
\end{mydef}

\begin{mydef}[T-récursif] Soit $A\subseteq \N$, $A$ est T-récursif s’il existe 
	une machine de Turing qui, recevant comme donnée n'importe quel nombre 
	naturel $x$, fournit tôt ou tard comme résultat : 
	$ \left\{
		\begin{array}{l l}
			1 & \quad \text{si $x\in A$}\\
    		0 & \quad \text{si $x\notin A$}
		\end{array} \right.$
\end{mydef}

\begin{mydef}[T-récursivement énumérable] Soit $A\subseteq \N$, A est 
	T-récursivement énumérable s’ il existe 
	une machine de Turing qui, recevant comme donnée n'importe quel nombre 
	naturel $x$, fourni tôt ou tard comme résultat : $ 1 \text{ si } x \in A$.\\
	Si $x \notin A$, la machine renvoie un résultat $\neq 1$, s'arrête avec un
	état $\neq stop$ ou boucle.
\end{mydef}

\subsubsection{Thèse de Church-Turing}
\begin{enumerate}
	\item Toute fonction T-calculable est calculable
	\item Toute fonction calculable est T-calculable
	\item Tout ensemble T-récursif est récursif
	\item Tout ensemble récursif est T-récursif
	\item Tout ensemble T-récursivement énumérable est récursivement 
		énumérable
	\item Tout ensemble récursivement énumérable est T-récursivement 
		énumérable
\end{enumerate}
Les points 1, 3 et 5 sont des théorèmes. Les autres sont des thèses.

\subsubsection{Extension du modèle}
On peut modifier le modèle pour changer sa puissance et son efficacité.

\begin{mydef}[Puissance d'une MT] La puissance d'une MT se mesure en 
	fonction du nombre de fonctions qu'elle peut calculer.
\end{mydef}


\begin{mydef}[Efficacité d'une MT] L'efficacité d'une MT se calcule en 
	fonction du nombre d'instructions à exécuter (on ne tient pas compte de 
	la taille d'un mot mémoire).
\end{mydef}

\paragraph{Changer les conventions}
On peut par exemple permettre de se déplacer de plusieurs cases à la fois ou 
encore de permettre plusieurs états $stop$.

\paragraph{Influence :} 
\begin{itemize}
	\item Même puissance
	\item Speedup linéaire (pour aller 20 cases à gauche on doit plus 
		exécuter 20 instructions se déplacer à gauche)
\end{itemize}

\paragraph{Réduire les symboles} Par exemple, ne plus avoir que 0 et 1 comme
symboles dans $\Sigma$.

\paragraph{Influence :} 
\begin{itemize}
	\item Même puissance
	\item Même efficacité, car même s’ il y a un facteur logarithmique, en 
		calculabilité on le néglige
\end{itemize}

\paragraph{Limiter le nombre d'états} Cela implique qu'il y a seulement un nombre fini 
de machines de Turing différentes.

\paragraph{Influence :} 
\begin{itemize}
	\item Moins puissant
\end{itemize}

\paragraph{Autres rubans}

Ruban unidirectionnel, c'est-à-dire limité d'un coté (à priori à gauche).

\paragraph{Influence :} 
\begin{itemize}
	\item Même puissance
	\item Slowdown linéaire : il faut faire plus de déplacement, en 
		effet, avant les cases étaient numérotés 
		$$-\infty,...,-2,-1,0,1,2,...,+\infty$$
		alors que maintenant ce sera
	    $$0,-1,1,-2,2,...,-\infty,+\infty$$
\end{itemize}

\paragraph{Ruban multicases} La tête lis plusieurs cases en parallèle, ce qui 
implique que la taille de l'alphabet augmente ($\Sigma \times \Sigma \times ...$).

\paragraph{Influence :} 
\begin{itemize}
	\item Même puissance
	\item Même efficacité
\end{itemize}

\paragraph{Plusieurs rubans} Chaque ruban à sa propre tête.
On doit changer la relation de transition, car un état est défini par les positions
de toutes les têtes. Le relation doit maintenant prendre l'état ($E$) et plusieurs 
symboles ($s_1,...,s_n$) et retourner un état ($E'$), plusieurs symboles 
($s_1',...,s_n'$) à écrire et plusieurs directions différentes, une pour chaque tête 
($d_1,...,d_n$).
%$$<s_1,s_2,...s_n>, E \  \rightarrow \ E', M_1, M_2,..., M_n, D_1, D_2,..., D_n$$
$$ <s_1,...,s_n>, E \ \rightarrow \ E', <s_1',...,s_n'>, <d_1,...,d_n> $$
% autre proposition (alors il faut changer le texte!) : 
% $$ \delta : S \times \Gamma^n \ \rightarrow \ S \times \Gamma^n \times \{G,D\}^n $$
\paragraph{Influence :} 
\begin{itemize}
	\item Même puissance
	\item Speedup quadratique
\end{itemize}

\subsubsection{Machine de Turing non déterministe NDT}
Tout comme pour les automates non déterministes, on permet plusieurs 
transitions possibles pour une paire <état, symbole>. La fonction de transition
devient une relation de transition, ce qui implique qu'il y a plusieurs
 exécutions possibles.

\begin{myrem}
	On utilise les NDT uniquement pour décider un ensemble.
\end{myrem}

\begin{myrem}
	Cette partie est importante pour la partie concernant la complexité.
\end{myrem}

\begin{mydef}[NDT-récursif] Soit $A\subseteq \N$, $A$ est NDT-récursif s'il 
	existe une ND-machine de Turing telle que lorsqu'elle reçoit comme 
	donnée n'importe quel nombre naturel $x$:\\
	\begin{tabular}{l}
		Si $x\in A$, alors il existe une exécution fournissant tôt ou 
		tard comme résultat 1.\\
		Si $x\notin A$, alors toutes les exécutions fournissent tôt ou 
		tard comme résultat 0.\\
	\end{tabular}
\end{mydef}

\begin{mydef}[NDT-récursivement énumérable] Soit $A\subseteq \N$, $A$ est 
	NDT-récursivement énumérable s'il 
	existe une ND-machine de Turing telle que lorsqu'elle reçoit comme 
	donnée n'importe quel nombre naturel $x$:\\
	\begin{tabular}{l}
		Si $x\in A$, alors il existe une exécution fournissant tôt ou 
		tard comme résultat 1.\\
		Si $x\notin A$, toutes les exécutions possibles retournent soit un 
		nombre $\neq 1$, \\
		soit ne se terminent pas, ou encore s'arrêtent avec 
		un état $\neq stop$.\\
	\end{tabular}
\end{mydef}

\paragraph{Influence :} 
\begin{itemize}
	\item Même puissance, car il existe une machine de Turing qui interprète
	 les NDT.
	\item Speedup exponentiel, car on "descend" directement au bon endroit 
		dans l'arbre. Mais comme en pratique on doit simuler 
		l'exécution non déterministe par un parcours en largeur de l'arbre d'exécution,
		 ça ne change rien.
\end{itemize}

\subsubsection{Machine de Turing avec Oracle}
On ajoute 3 états spéciaux : soit $A \subseteq \N$
\begin{itemize}
	\item $oracle_{ask}$ : demander si l'entier représenté à droite de la 
		tête de lecture appartient à l'ensemble $A$
	\item $oracle_{yes}$ : l'entier appartient à $A$
	\item $oracle_{no}$ :  l'entier n'appartient pas à $A$
\end{itemize}

\paragraph{Puissance :} Elle dépend de $A$. Si $A$ est récursif, ça n'apporte rien et
  on garde la même puissance, car on peut remplacer l'oracle par un programme qui décide   
  $A$.
  
Par contre, si $A$ n'est pas récursif, alors c'est un modèle plus 
puissant (on pourrait déterminer halt). Mais il n’est pas possible d'exécuter un tel programme. 

\begin{myrem}
	Utilité : permet d'établir une hiérarchie parmi les problèmes 
	indécidables. Quels problèmes seraient encore
	indécidables si K était récursif?
\end{myrem}

\subsubsection{Machine de Turing Universelle}

\paragraph{Objectif :} Construire une machine de Turing qui soit un 
interpréteur de machines de Turing

\begin{myrem}
	On définit un encodage de 0, 1 qui permet de représenter une MT
\end{myrem}

Une telle machine est possible à construire. Il y a plusieurs façons différentes de faire. Une façon de faire est d'utiliser 3 rubans:
\begin{itemize}
	\item codage de la MT à interpréter
	\item donnée
	\item résultat intermédiaire de l'interpréteur
\end{itemize}
% subsection machines_de_turing (end)

\subsection{Fonctions récursives}
\label{sub:fonction_r_cursives}
Ce modèle de calcul se base sur la définition mathématique de fonction. On va 
s'intéresser aux fonctions de $\N^k \ \rightarrow \ \N$.

\paragraph{} Il y a 2 grandes classes de fonctions récursives: 
\begin{itemize}
	\item Fonctions primitives récursives, on se limite aux fonctions totales 
		(équivalent au langage BLOOP)
	\item Fonction récursives, c'est un modèle complet, on peut calculer 
		toutes les fonctions calculables 
\end{itemize}

\paragraph{Fonctions de bases} Ce sont des fonctions qui vont être utilisées 
pour construire nos fonctions.

\begin{description}
	\item[Fonctions constantes] 
		\begin{tabular}{|l|}
			\hline
			$a: \N^0 \rightarrow \N$\\
			$a() = a$\\
			\hline
		\end{tabular}
	\item[Fonctions successeur] 
		\begin{tabular}{|l|}
			\hline
			$s: \N \rightarrow \N$\\
			$s(n) = n + 1$\\
			\hline
		\end{tabular}
	\item[Fonctions de projection] 
		\begin{tabular}{|l|}
			\hline
			$p^k_i: \N^k \rightarrow \N$\\
			$p^k_i(x_1,..,x_i,...x_k) = x_i$\\
			\hline
		\end{tabular}
\end{description}

Il existe aussi 2 "règles" importantes :
\paragraph{Composition}
\begin{tabular}{|l|}
	\hline
	$h_1, h_2,...,h_m: \N^k \rightarrow \N$\\
	$g: \N^m \rightarrow \N$\\
	$\stcomp{x} =x_1,...x_k$ \\
	$f(\overline{x}) = 
	g(h_1(\overline{x}),h_i(\overline{x}),...,h_m(\overline{x}))$\\
	\hline
\end{tabular}

\paragraph{Récursion primitive}
\begin{tabular}{|l|}
	\hline
	$h: \N^{k+2} \rightarrow \N$\\
	$g: \N^k \rightarrow \N$\\
	$\stcomp{x} =x_1,...,x_k$ \\
	$f(\overline{x}, 0) = g(\overline{x}) \quad$ (Cas de base)\\
	$f(\overline{x}, n+1) = 
	h(\overline{x},n, f(\overline{x}, n))\quad$ (Cas récursif)\\
	\hline
\end{tabular}

\begin{myrem}
	Lors de l'utilisation de la récursion primitive, il faut faire 
	attention. Le cas de base ne peut pas faire appel à $f$ et on passe 
	toujours de $n+1$ à $n$, car il ne peut pas y avoir de récursion infinie.
\end{myrem}

\subsubsection{Fonctions primitives récursives}
Ce modèle ne permet d'utiliser que les fonctions de base et les fonctions 
obtenues suite à l'application de composition ou de récursion primitive.

\begin{myprop}
	Les fonctions primitives récursives ne sont pas un modèle de complet de 
	la calculabilité. En effet, il ne peut pas y avoir de récursion 
	infinie. Donc on ne peut calculer avec ce modèle que des fonctions 
	totales calculables. De plus, on sait par le théorème de Hoare-Allison que, comme ce 
	n'est pas un modèle complet, son interpréteur n'est pas calculable 
	dans le modèle.
\end{myprop}

\begin{myexem}
	La fonction d'Ackermann est une fonction calculable \textbf{non} 
	primitive récursive :
	\begin{align}
		ack(0,m) &= m+1 \\
		ack(n+1,0) &= ack(n+1)\\
		ack(n+1,m+1) &= ack(n, ack(n+1,m))
	\end{align}
	Cette fonction à une croissance plus rapide que n'importe quelle fonction 
	primitive récursive.
\end{myexem}


\subsubsection{Fonctions récursives}
\label{ssub:fonctions_r_cursives}
On va étendre les fonctions primitives récursives en ajoutant une règle :

\paragraph{Minimisation}
\begin{tabular}{|l|}
	\hline
	$h: \N^{k+1} \rightarrow \N$\\
	$f: \N^{k} \rightarrow \N$\\
	$\stcomp{x} =x_1,...,x_k$ \\
	$f(\overline{x}) = \mu_n (h(\overline{x}, n) = 0)$\\
	$\mu_n$ est le plus petit $n$ tel que $h(\overline{x}, n) = 0$ \\
	\hline
\end{tabular}

\begin{myprop}
	Les fonctions récursives sont un modèle complet de la calculabilité. 
	Toute fonction calculable est une fonction récursive et vice versa.
\end{myprop}
% subsection fonction_r_cursives (end)

\subsection{Lambda calcul}
\label{sub:lambda_calcul}
\begin{myrem}
	C'est encore un modèle peu intuitif. Je pense que c'est important 
	de refaire l'exercice sur le vrai ou faux en lambda calcul ou encore la 
	représentation des entiers dans le cours. Mais c'est un modèle complet 
	et qui contient la base de la programmation fonctionnelle.
\end{myrem}

\begin{mydef}[Symboles de base] Soit une variable : $a,b,c,...y,z,...$ ou un 
	symbole spécial : $\lambda, (, )$
\end{mydef}

\begin{mydef}[Expression lambda] est l'une des 3 choses suivantes :
	\begin{itemize}
		\item une variable
		\item $\lambda xB$ si $B$ est une expression lambda et que $x$ est 
			une variable. \\
			$\lambda x$ correspond à la définition 
			d'une variable \textbf{liée} \\
			$\lambda xB$ correspond à la définition d'une fonction 
			à un paramètre, $x$.
		\item $(FA)$ si $F$ et $A$ sont des expressions lambda. On dit que $F$ 
			est l'opérateur et $A$ est l'opérande. Ça représente 
			l'application de $F$ à $A$.
	\end{itemize}
\end{mydef}

\begin{mydef}[Variable liée] est une variable qui suit un $\lambda$ ou qui 
	apparait dans $M$ et qu'on a $\lambda xM$. 
\end{mydef}

\begin{mydef}[Variable libre] est une variable qui n'est pas liée.
\end{mydef}

\subsubsection{Réduction}

\paragraph{Objectif :} appliquer les fonctions (opérateur) à un opérande, 
jusqu'à ce qu'il n'y ait plus de fonction à appliquer. On obtient alors une 
forme réduite.

\begin{mydef}[Application de fonction] Si on a une expression lambda $(FA)$ où 
	$F$ est une fonction $\lambda xB$, on remplace toutes les occurrences liées 
	de $x$ dans $B$ par $A$.
\end{mydef}

\begin{myrem}
	Il faut faire attention, car lorsqu'on réduit une expression on ne peut 
	pas introduire de conflit de nom, donc il faut renommer les variables.
\end{myrem}

\begin{myrem}
	Il est possible d'avoir des réductions infinies, par exemple :\\ 
	$(\lambda x\ (xx)\ \lambda x \ (xx)) \ \rightarrow \ (\lambda x\ (xx) \  
\lambda x \ (xx))$
\end{myrem}

\begin{myrem}
	Il est important de voir qu'il y a plusieurs façons de réduire, ça 
	dépend de l'ordre dans lequel on applique les réductions.
\end{myrem}

\begin{myprop}
	Une expression lambda est non définie si, peu importe le choix de 
	réduction, on n’arrive pas à une forme réduite.
\end{myprop}

\begin{mytheo}[Church-Rosser] Si 2 séquences de réductions d'une expression 
	lambda conduisent à une forme réduite, alors les expressions obtenues 
	sont équivalentes.
\end{mytheo}

\begin{myprop}
	Si une forme réduite existe, le choix de réduire l'expression la plus à 
	gauche amène toujours à une forme réduite. (Donc, privilégier la 
	réduction la plus à gauche.)
\end{myprop}

\begin{myrem}
	Il existe 2 types de réduction la plus à gauche: la moins imbriquée 
	(semblable au passage par nom en programmation) et la plus imbriquée 
	(semblable au passage par valeur).
\end{myrem}
% subsection lambda_calcul (end)
% section mod_le_de_la_calculabilit_ (end)

\section{Analyse de la thèse de Church-Turing}
\label{sec:analyse_de_la_th_se_de_church_turing}
Dans ce chapitre on va principalement voir ce qu'est un bon formalisme.

\subsection{Fondement de la thèse}
\label{sub:fondement_de_la_th_se}
La forme originale ne contient que 2 parties :
\begin{enumerate}
	\item Toute fonction calculable par une MT est effectivement calculable
	\item Toute fonction effectivement calculable est effectivement 
		calculable par une MT 
\end{enumerate}
La partie 1 est démontrée et la 2 est supposée vraie. 
On la suppose vraie, car on a des évidences heuristiques (il y a eu beaucoup 
d'essais pour trouver une fonction qui ne respectait pas la thèse) et qu'on a montré 
l'équivalence entre tous les formalismes créés à ce jour (on a montré que toute 
machine constructible par la mécanique de Newton ne calcule que des fonctions 
calculables). 
% subsection fondement_de_la_th_se (end)

\subsection{Formalismes de la calculabilité}
\label{sub:formalismes_de_la_calculabilit_}
On va se poser la question de ce qui fait un bon formalisme de la 
calculabilité. Il faut un formalisme qui vérifie les fondements de la 
thèse... Plus précisément, on va étudier des caractéristiques (des propriétés) 
nécessaires et suffisantes pour avoir un bon modèle de la calculabilité.

\paragraph{} Dans ce chapitre, on va considérer un formalisme de la 
calculabilité D.

\paragraph{Caractéristiques} 
\begin{description}
	\item[SD] Soundness\footnote{Cohérence} des descriptions
	\item[CD] Complétude des descriptions
	\item[SA] Soundness algorithmique
	\item[CA] Complétude algorithmique
	\item[U] Description universelle
	\item[S] Propriété S-m-n affaiblie
\end{description}


\begin{myrem}
	\textbf{D} correspond à description, c'est-à-dire une description de fonction.\\
	\textbf{A} correspond à algorithme, c'est-à-dire à une description
	exécutable.
\end{myrem}

\begin{myrem}
	\textbf{Soundness} signifie que, si on a une description dans notre modèle D alors
	celle-ci est cohérente, correspond bien à une fonction
	calculable.\\
	\textbf{Complétude} signifie que notre modèle est complet, qu'il
	n'existe pas de fonction calculable qui ne le soit pas dans notre
	modèle.
\end{myrem}

\paragraph{Caractérisiques plus en détails}
\begin{description}
	\item[SD]  Toute fonction D-calculable est calculable (première partie 
		de la thèse de Turing)
	\item[CD]  Toute fonction calculable est D-calculable (deuxième partie 
		de la thèse de Turing)
	\item[SA]  L'interpréteur de D est calculable (on peut exécuter une 
		description de programme de D)
	\item[CA]  Il existe un 
		compilateur qui étant donné un programme $p$ dans un formalisme 
		respectant SA produit une description de programme $d \in D$ tel que 
		$p$ et $d$ calculent la même fonction.
	\item[U]  L'interpréteur de D est D-calculable (sinon on sait par 
		Hoare Allison que ce n'est pas un formalisme complet).
	\item[S] Il existe un transformateur de programme calculable, qui 
		recevant comme entrée un programme $d \in$ D à 2 arguments et une valeur 
		$x$ fournit comme résultat un programme $d'$ tel que $d'(y)$ calcule 
		la même fonction que $d(x,y)$.
		% checker si d' dans D!!!
\end{description}
Un bon formalisme de la calculabilité possède toutes ces propriétés. En pratique, il 
suffit d'en montrer certaines, car certaines propriétés en entraînent d'autres.

\begin{myprop}
	SA $\Rightarrow$ SD, car si on peut trouver une description exécutable,
	celle-ci existe.
\end{myprop}

\begin{myprop}
	CA $\Rightarrow$ CD, car si on a un compilateur qui compile un programme 
	de P en une description dans D, alors un programme de P est calculable dans D.
\end{myprop}

\begin{myprop}
	SD et U $\Rightarrow$ SA car si on sait qu'il existe une description D calculant
	une fonction et 
qu'on a un interpréteur de D D-calculable, alors la description est exécutable.
\end{myprop}

\begin{myprop}
	CD et S $\Rightarrow$ CA, considérons n'importe quel autre formalisme
Q qui a la propriété SA (ce qui signifie que sont interpréteur, $interp_Q(n,x)$ est calculable). 
Donc par la propriété CD, il existe un programme $p\in P$ tel que
$\phi_p=\phi_{interp_Q}(n,x)$. Ensuite par la propriété S, il existe T, un
transformateur de programme tel que : $\phi_{interp_Q}(n,x)=\phi_{T(n)}(x)$.
On peut donc voir T comme un programme qui compile/transforme une description $q\in Q$ en une
description $p\in P$. Ce qui implique qu'on a bien la propriété CA.

\end{myprop}

Un bon formalisme doit donc posséder soit SA et CA ou soit SD, CD, U et S ou 
soit SA, CD et S ou encore CA, SD et U, car
\begin{itemize}
	\item SA et CA $\iff$ SD, CD, U et S
	\item SA, CD et S $\iff$ SD, CA et U
\end{itemize}
% su section formalismes_de_la_calculabilité_ (end)

\subsection{Techniques de preuve}
\label{sub:techniques_de_preuve}

Pour prouver qu'un problème est non calculable, on peut utiliser :
\begin{itemize}
	\item Le théorème de Rice
	\item La démonstration directe de la non-calculabilité par 
		diagonalisation ou par preuve par l'absurde. 
		\textbf{A priori le plus dur!} C'est plus pratique de réutiliser les problèmes pour 
		lesquels on a déjà montré la non-calculabilité.
	\item La méthode de réduction
\end{itemize}
% subsection techniques_de_preuve (end)

\subsection{Aspects non couverts par la calculabilité\\ (Section pas très
	importante pour l'examen)}
\label{sub:aspects_non_couvert_par_la_calculabilit_}
La calculabilité se limite au calcul de fonctions. Or certains problèmes de la vie 
de tous les jours ne correspondent pas à une fonction.

\begin{myexem}
	Système d'exploitation
\end{myexem}

\begin{myexem}
	Système de réservation aérienne
\end{myexem}

\begin{myexem}
	Certains problèmes utilisent des caractéristiques de l'environnement comme 
	des données en provenance de sonde.
\end{myexem}
% subsection aspects_non_couvert_par_la_calculabilit_ (end)

\subsection{Au-delà de la calculabilité}
\label{sub:au_del_de_la_calculabilit_}
Est-il possible d'imaginer un modèle plus puissant que les modèles qu'on a 
aujourd'hui? Est-ce que les humains sont "plus puissants" que les machines dans 
le sens où ils pourraient calculer des fonctions non calculables?

Ce sont des questions qui font débat. Certain ne veulent même pas 
poser la deuxième question c'est-à-dire est-ce que H-calculable = T-calculable.

\begin{mydef}[H-calculable]
	Une fonction est H-calculable si un être humain
	est capable de calculer cette fonction.
	% tu confonds avec la thèse CT "procédés publics" sinon
\end{mydef}

\paragraph{} À la question "les machines pensent-elles?", Turing a proposé un 
raisonnement : 
\begin{itemize}
	\item \textbf{Hypothèse :} les machines pensent.
	\item Si on ne peut réfuter l'hypothèse alors celle-ci est vraie
	\item Envisager toutes les objections (théologique, émotions, 
		mathématiques...) et toutes les réfuter.
\end{itemize}

% subsection au_del_de_la_calculabilit_ (end)
% section analyse_de_la_t_se_de_chu ch_Turin (end)

\section{Complexité}
\label{sec:complexit_}
Lors de l'étude de la complexité, on ne va considérer que la borne supérieure 
(notation big O). De plus, on ne va considérer que les fonctions totales et 
donc la décision d'ensembles récursifs. 
En effet, si la fonction n'est pas totale, l'algorithme peut boucler. 
Donc on ne sait pas étudier l'efficacité.

\begin{mydef}[Complexité d'un problème] Complexité de l'algorithme le 
	\textbf{plus efficace} résolvant ce problème.
\end{mydef}

\begin{mydef}[Problème pratiquement faisable]
	S’il existe un algorithme de complexité polynomiale qui résout ce 
	problème, alors, celui-ci est pratiquement faisable.
\end{mydef}

\begin{mydef}[Problème intrinsèquement complexe]
	S’il n'existe pas d'algorithme de complexité polynomiale qui résout ce 
	problème, alors, celui-ci est intrinsèquement complexe.
\end{mydef}

\begin{myrem}
	Quelle est la différence entre intrinsèquement complexe et pratiquement 
	infaisable?
\end{myrem}

\subsection{Influence du modèle de calcul}
\label{sub:influence_du_mod_le_de_calcul}
Si un algorithme est de complexité polynomiale dans un modèle complet alors il sera 
polynomial dans un autre modèle de calcul. Il y aura juste un facteur 
polynomial entre les deux, car il existe un compilateur du premier modèle vers 
le second qui a une complexité polynomiale.
% subsection influence_du_mod_le_de_calcul (end)

\subsection{Influence de la représentation des données}
\label{sub:influence_de_la_repr_sentation_des_donn_es}
Le choix de représentation de données induit une variation polynomiale du temps 
d'exécution et de l'espace.

\begin{myrem}
	Certains problèmes sont intrinsèquement complexes juste pour certaines 
	données (simplexe). Celles-ci sont souvent des cas particuliers et peu 
	rencontrées en pratique.
\end{myrem}
% subsection influence_de_la_repr_sentation_des_donn_es (end)

% section complexit_ (end)

\section{Classes de complexité}
\label{sec:classes_de_complexit_}
On va se "limiter" au problème de décision.

\begin{myrem}
	On ne se limite pas vraiment, car on 
	peut facilement transformer un problème en un problème de décision.
\end{myrem}

\subsection{Réduction}
\label{sub:r_duction}

\paragraph{Objectif :} Déduire un algorithme pour un problème P' à partir d'un 
algorithme P permet:
\begin{itemize}
	\item de prouver la calculabilité/non calculabilité
	\item d'analyser le degré de non-calculabilité
	\item de déduire la complexité
	\item d'analyser le degré de complexité
\end{itemize}

\begin{mydef}[Relation de réductibilité]
	$A \leq B$ : $A$ est réductible à $B$. Cette relation induit des classes 
	d'équivalence. On peut comprendre ça comme $A$ est plus "simple" que $B$.
\end{mydef}

Il existe plusieurs méthodes de réduction qui ont des propriétés différentes.
Mais dans ce cours on va en étudier 
que 3 :
\begin{itemize}
	\item réduction algorithmique
	\item réduction fonctionnelle 
	\item réduction polynomiale
\end{itemize}

\begin{mydef}[A-complet]
	Soit $A$ une classe de problème, un problème $E$ est $A$-complet
	\textbf{par rapport} à une relation de réduction $\leq$ si 
	\begin{enumerate}
		\item $E \in A$
		\item $\forall B \in A \ : \ B \leq E$
	\end{enumerate}
\end{mydef}

\begin{myrem}
	Le problème $E$ appartient à la classe de problème $A$ et 
	est $A$-difficile.	
\end{myrem}

\begin{mydef}[A-difficile]
	Soit $A$ une classe de problème, un problème $E$ est $A$-difficile
	\textbf{par rapport} à une relation de réduction $\leq$ si 
	\begin{enumerate}
		\item $\forall B \in A \ : \ B \leq E$
	\end{enumerate}
\end{mydef}
	
\begin{myrem}
	N'importe quel problème de $A$ peut être réduit au problème $E$, mais $E$
	n'appartient pas nécessairement à $A$.
\end{myrem}


\subsubsection{Réduction algorithmique}
Ce type de réduction n'apporte aucune information au niveau de la complexité, car on 
peut répéter autant de fois qu'on veut l'algorithme qui décide $B$. On peut aussi 
faire un calcul avec une complexité très grande en plus d'utiliser $B$.

\begin{mydef}[Réduction algorithmique]
	Un ensemble $A$ est algorithmiquement réductible à un ensemble $B$ 
	($A\leq_a B$) si en supposant $B$ récursif, $A$ est récursif.
\end{mydef}

\begin{myrem}
	C'est à dire qu'en supposant qu'on connait un algorithme qui décide $B$, on 
	peut construire un algorithme qui décide $A$.
\end{myrem}

\begin{myprop}
	Si $A \leq_a B$ et $B$ récursif, alors $A$ récursif (par définition)
\end{myprop}

\begin{myprop}
	Si $A \leq_a B$ et $A$ non récursif, alors $B$ non récursif (par définition)
\end{myprop}

\begin{myprop}
	$A \leq_a \stcomp{A}$
\end{myprop}

\begin{myprop}
	$A \leq_a B \ \iff \ \stcomp{A} \leq_a \stcomp{B}$
\end{myprop}

\begin{myprop}
	Si $A$ est récursif alors peu importe le $B$, $A \leq B$
\end{myprop}

\begin{myprop}
	Si $A \leq_a B$ et $B$ récursivement énumérable alors $A$ n'est 
	\textbf{pas nécessairement récursivement énumérable}
\end{myprop}

\subsubsection{Réduction fonctionnelle}
Ce type de réduction n'apporte aucune information au niveau de la complexité,
car tout dépend de la complexité de la fonction $f$.

\begin{mydef}[Réduction fonctionnelle]
	Un ensemble $A$ est fonctionnellement réductible à un ensemble $B$ 
	($A\leq_f B$) s’il existe une fonction \textbf{totale calculable} $f$ 
	telle que 
	\[ a\in A \ \iff \ f(a) \in B \]
\end{mydef}

\begin{myrem}
	Donc pour décider si $a\in A$ il suffit de calculer $f(a)$ et décider si 
	$f(a) \in B$. Pour trouver une réduction fonctionnelle, il faut trouver 
	une fonction qui transforme un problème de $A$ en un problème de $B$.
\end{myrem}

\begin{myprop}
	Si $A \leq_f B$ et $B$ récursif, alors $A$ récursif (par définition)
\end{myprop}

\begin{myprop}
	Si $A \leq_f B$ et $A$ non récursif, alors $B$ non récursif (par définition)
\end{myprop}

\begin{myprop}
	$A \leq_f B \ \iff \ \stcomp{A} \leq_f \stcomp{B}$
\end{myprop}

\begin{myprop}
	Si $A$ est récursif alors peu importe le $B$, $A \leq B$
\end{myprop}

\begin{myprop}
	Si $A \leq_f B$ et $B$ récursivement énumérable alors A est
	\textbf{nécessairement récursivement énumérable}
\end{myprop}

\begin{myprop}
	$A\leq_f B \Rightarrow A\leq_a B$ (Attention ce n'est pas toujours vrai 
	dans l'autre sens)
\end{myprop}

\subsubsection{Différence entre $\leq_a$ et $\leq_f$}
La principale différence, c'est que $A \leq_a B$ est plus du point de vue de la 
calculabilité. On s'intéresse au fait que ça soit possible, on peut utiliser 
autant de fois que l'on veut le fait que $B$ soit récursif. \\
Alors que $A \leq_f B$ est plus du point de vue de la complexité. On est 
obligé d'utiliser un certain schéma d'algorithme :

\begin{lstlisting}
input a
// some work
a2 := f(a)
// some work
if a2 in B then 1
else 0
\end{lstlisting}

On est donc limité à utiliser qu'une fois le test $f(a) \in B$ \textbf{en 
	dernier lieu}.

\subsection{Modèles de calcul}
D'habitude, on utilise les machines de Turing pour avoir une définition précise 
de la complexité. Mais c'est peu intuitif et on s'intéresse aux frontières. Or la 
différence de complexité entre différents modèles est un facteur polynomial 
(c'est une thèse) ce qui n'a pas d'influence sur les frontières.

\subsection{Classes de complexité}

\paragraph{Classes basées sur le modèle déterministe}
\begin{mydef}[DTIME(f)]
	Famille des ensembles récursifs pouvant être décidés par un programme 
	Java de complexité temporelle $\mathcal{O}(f)$
\end{mydef}

\begin{mydef}[DSPACE(f)]
	Famille des ensembles récursifs pouvant être décidés par un programme 
	Java de complexité spatiale $\mathcal{O}(f)$
\end{mydef}

\paragraph{Classes basées sur le modèle non déterministe}
\begin{mydef}[NTIME(f)]
	Famille des ensembles récursifs pouvant être décidés par un programme 
	non déterministe Java de complexité temporelle $\mathcal{O}(f)$
\end{mydef}

\begin{myrem}
	On considère juste la complexité de la branche d'exécution la plus
	longue. Toutes les branches sont donc finies.	
\end{myrem}

\begin{mydef}[NSPACE(f)]
	Famille des ensembles récursifs pouvant être décidés par un programme 
	non déterministe Java de complexité spatiale $\mathcal{O}(f)$
\end{mydef}

\begin{mydef}[Classe P]
	\[ P = \mathop{\cup}_{i \geq 0} DTIME(n^i)\]
	Famille des ensembles récursifs pouvant être décidés par un programme
	Java de complexité temporelle polynomiale.
\end{mydef}

\begin{myrem}
	Les classes ne dépendent pas du modèle de calcul
\end{myrem}

\begin{mydef}[Classe NP]
	\[ NP = \mathop{\cup}_{i \geq 0} NTIME(n^i)\]
	Famille des ensembles récursifs pouvant être décidés par un programme
	Java non déterministe de complexité temporelle polynomiale.
\end{mydef}

\begin{myrem}
	Si on savait faire du non-déterminisme, on aurait une complexité polynomiale,
	mais pour le moment on ne peut que le simuler donc on a une complexité
	exponentielle.
\end{myrem}

\subsection{Relations entre les classes de complexité}
\label{sub:relations_entre_les_classes_de_complexit_}

\paragraph{Déterministe vs non-déterministe}
\begin{myprop}
	$A \in NTIME(f) \Rightarrow A \in DTIME(c^f)$ \\
	$f$ est la profondeur maximale de l'arbre. Si on simule le
	ND, alors on doit faire un bfs dans un arbre de profondeur $f$.
	$c$ est le facteur de branchement.
\end{myprop}

\begin{myprop}
	$A \in NSPACE(f) \Rightarrow A \in DSPACE(f^2)$ \\
	C'est une borne sur le nombre de nœuds d'un graphe de
	profondeur $f$. Théorème de Savitch.
\end{myprop}

\paragraph{Time vs Space}
\begin{myprop}
	$A \in DTIME(f) \Rightarrow A \in DSPACE(f)$ \\
	Le programme ne peut utiliser qu'au maximum un emplacement
	mémoire par instruction. Donc l'espace utilisé est limité par le
	nombre d'instructions.
\end{myprop}

\begin{myprop}
	$A \in NTIME(f) \Rightarrow A \in NSPACE(f)$ \\
	C'est la même chose que pour le cas déterministe (propriété précédente).
\end{myprop}

\begin{myprop}
	$A \in DSPACE(f) \Rightarrow A \in DTIME(c^f)$ \\
	On sait que le programme se termine, donc il trouve la réponse. Or,
	une combinaison particulière de la mémoire est cette réponse.
	Le programme ne peut pas générer plus que le nombre de combinaisons
	possibles de la mémoire, sinon il passerait la réponse.
\end{myprop}

\begin{myprop}
	$A \in NSPACE(f) \Rightarrow A \in NTIME(c^f)$ \\
	C'est la même chose que pour le cas déterministe (propriété précédente).
\end{myprop}

\paragraph{Hiérarchie de complexité}
On peut prouver qu'il existe pire qu'une complexité exponentielle.

\subsection{$NP$-complétude}
La question fondamentale de la complexité est la suivante :
\textbf{s'il existe un algorithme
non déterministe polynomial, existe-t-il un algorithme déterministe polynomial
résolvant ce même problème?}
 C'est-à-dire, est-ce que \textbf{$P = NP$?} On sait que $P
\subseteq NP$ mais on n'a pas encore montré si oui ou non $NP\subseteq P$.

\paragraph{} Pour démontrer ça, on essaye de montrer qu'un élément de $NP$, le
plus difficile, est dans $P$. On choisit un élément qui soit $NP$-complet par
rapport à une relation de réduction. Ainsi, si on y arrive, ça implique que
tous les autres éléments de $NP$ sont dans $P$ aussi.

\paragraph{} La question est maintenant de choisir la relation de réduction.
Les 2 relations de réduction définies précédemment ne suffisent pas. Ces
réductions ne permettent pas d'affirmer quelque chose sur la complexité. On
introduit donc une nouvelle réduction, la réduction polynomiale.

\begin{mydef}[Réduction polynomiale]
	Un ensemble $A$ est polynomialement réductible à un ensemble $B$, $A \leq
	_p B$ s’il existe une fonction \textbf{totale calculable} $f$ de
	\textbf{complexité temporelle polynomiale} telle que 
	\[a\in A \ \Leftrightarrow \ f(a)\in B \]
\end{mydef}

\begin{myrem}
	On ajoute à la réduction fonctionnelle une contrainte de complexité
	sur la fonction $f$. Cette réduction nous permet donc de tirer des
	conclusions sur la complexité de $A$ connaissant la complexité de $B$.
\end{myrem}

\begin{myprop}
	\[ A \leq_p B \text{ et } B\in P \Rightarrow A\in P \]
	Ce qui est logique étant donné qu'on a la complexité de $f$ qui est
	polynomiale + la complexité de la décision de $B$ qui est aussi
	polynomiale.
\end{myprop}

\begin{myprop}
	\[ A \leq_p B \text{ et } B\in NP \Rightarrow A\in NP \]
	Ce qui est logique étant donné qu'on à la complexité de $f$ qui est
	polynomiale + la complexité de la décision de $B$ qui est non déterministe
	polynomiale.
\end{myprop}


\begin{mydef}[$NP$-complétude]
	Un problème $E$ est $NP$-complet (par rapport à $\leq_p$) si :
	\begin{enumerate}
		\item $E\in NP$
		\item $\forall B \in NP$ : $B\leq_p E$
	\end{enumerate}
\end{mydef}

\begin{myprop}
	\[ E \leq_p B \text{ et } B\in NP \Rightarrow \text{$B$ est $NP$-complet} \]
	Ce qui est logique puisque ça veut dire que $B$ est $NP$-difficile et dans
	$NP$.
\end{myprop}

TODO schéma sur les classes de problèmes

\paragraph{} On va maintenant essayer de trouver des problèmes $NP$-complets et de
trouver des propriétés intéressantes sur $P$.

\subsubsection{Problème de décision}
On va définir différemment la classe $NP$. On va considérer des problèmes de
décision. Pour un ensemble $A$ cela consiste à dire si oui ou non une donnée $x$
appartient à $A$. On peut voir cela comme un prédicat. Par exemple $SAT(x)$ : la
formule $x$ est-elle satisfaisable?

\paragraph{Redéfinition de $P$ et $NP$} en problème de décision.

\begin{mydef}[Classe $P$]
	La classe $P$ est la classe des problèmes de décision pouvant être
	décidés par un algorithme polynomial.
\end{mydef}

\begin{mydef}[Classe $NP$]
	La classe $NP$ est la classe des problèmes de décision $A(x)$ pouvant
	s'exprimer sous la forme $\exists y \ B(x,y)$ tel que :
	\begin{itemize}
		\item $B(x,y) \in P$ (Il est donc facile de vérifier une
			solution)
		\item le domaine de $y$ est fini (taille polynomiale en $x$)
		       	et peut être généré, de manière non déterministe, en 
			un temps polynomial
	\end{itemize}
\end{mydef}

\begin{myrem}
	On peut se représenter ça comme si le non-déterminisme permettait
       	de générer tous les $y$ "en même temps" ou 
	que le non-déterminisme choisissait le bon $y$.
	Il est rapide de tester une solution, mais pas d'en trouver une.
\end{myrem}

\begin{mydef}[Calcul d'un problème $NP$]
	Pour décider $A(x)$
	\begin{enumerate}
		\item calculer $y$ (de manière non déterministe)
		\item déterminer $B(x,y)$
	\end{enumerate}
\end{mydef}

\subsection{Théorème de Cook : $SAT$ est $NP$-complet}
Pour pouvoir trouver des problèmes $NP$-complet en les réduisant par rapport à
un problème $NP$-complet, il faut trouver un premier problème $NP$-complet. 
\paragraph{} On va montrer que $SAT$ est $NP$-complet en 2 parties :
\begin{enumerate}
	\item $SAT \in NP$
	\item $\forall B \in NP \ : \  B\leq_p SAT $
\end{enumerate}

\subsubsection{Le problème SAT}
Le problème $SAT(x)$ est de décider si la formule propositionnelle $x$ est 
satisfaisable ou non. C'est-à-dire: est-ce que $x\in SAT$?

\paragraph{} La longueur d'une formule $x$ est $O(n\log n)$, où $n$ est le nombre
d'occurrences des variables. Ça se justifie par le fait qu'en utilisant un codage
d'Huffman, le code pour une variable prendra $\log n$ (c'est important pour
définir la complexité du problème).

\subsubsection{$SAT \in NP$}
Il existe un programme ND polynomiale capable de décider si $x\in SAT$. On pose
que $m$ est le nombre de variables de $x$ et $n$ est le nombre d'occurrences de
variables ($m\leq x$). Étapes de l'algorithme avec leur complexité :
\begin{itemize}
	\item  Générer une séquence de $m$ valeurs logiques de façon
		non déterministe : $\mathcal{O}(m)$
	\item  Substituer les occurrences des variables par leur valeur :
	$\mathcal{O}(n
		\log n)$ 
	\item Évaluer l'expression : Complexité polynomiale par une technique
		de réduction.
\end{itemize}

\subsubsection{$\forall B \in NP \ : \  B\leq_p SAT $}
Comme $B \in NP$, on a une NDMT qui décide $B$ en un temps polynomial $p(n)$. On va
montrer qu'on sait transformer en un temps polynomial la NDMT par rapport à $n$
en une formule propositionnelle et que cette formule à une longueur qui dépend 
de $p(n)$ ($\mathcal{O}(p(n))$ symboles). Ce qui prouve que $B \leq_p SAT$.

\paragraph{Idée de la transformation} Il me semble qu'on ne doit pas la connaitre
pour l'examen. Mais l'idée est de représenter le ruban comme un tableau de
variables booléennes (chaque ligne représente le ruban à un instant), 
même chose pour les états, le curseur, l'alphabet,...


\subsection{Quelques problèmes $NP$-complets}
\begin{itemize}
	\item Problème du circuit hamiltonien HC (trouver un chemin qui passe
		une seule fois par tous les sommets)
	\item Problème du voyageur de commerce TS (trouver un chemin qui relie
		tous les sommets et de longueur $\leq B$)
	\item Chemin le plus long entre 2 sommets dans un graphe
	\item $3SAT$ (forme conjonctive avec 3 variables par clause)
	\item Programmation entière (simplexe)
	\item ...
\end{itemize}

% section classes_de_complexit_ (end)
\end{document}