88_SolutionsExercices.tex

% Concepts
% =========

\chapter{Solutions exercices}
\label{ch:solExer}

% Les exercices apparaisssnet dan sle syllabus sius la forme 
% \begin{myexercice} \label{exerc:test1}
% Enoncé de l'exercice
% \end{myexercice}
%
% La solution dans ce chapitre est rédigée sous la forme
% \solexercice{exerc:test1}
% Solution de l'exercice

%------------------------------------------------------
\section{Introduction}





%------------------------------------------------------
\section{Concepts}

 \solexercice{exerc:ensembleEnumNumAlgebrique}
 Posons $E_k$ l'ensemble des nombres algébriques qui satisfont le polynôme:\\
   $a_0 + a_1x + a_2x^2 + ... + a_nx^n$. avec n<k et max($|c_j|$) < k.\\
 Il existe au plus $k^k$ polynômes de cette forme,
et chacun a au plus k racines.\\
Donc $E_k$ est un ensemble fini ayant au plus $k^{k+1}$ éléments. Ainsi nous listons les nombres algébriques $E_1, E_2, E_3, E_4$ et retirons les répétitions et obtenons une nouvelle ensemble qui est enumerable.
 
 
 \solexercice{exerc:conceptfct}
% Solution de l'exercice


\solexercice{exerc:ensembleNonEnumNumTranscendantaux}
Soit A l’ensemble des nombres algébriques et T l’ensemble des nombres transcendantaux.\\
Notons que l'ensemble $R = A \cup T$ et A est énumérable. Si T étais énumérables, alors R serait l’union de deux ensembles énumérables. Puisque R est non-énumérable, par conséquent, T est non-énumérable cas s'il etais R serait énumérable.

%------------------------------------------------------
\section{Resultats Fondamentaux}




%------------------------------------------------------
\section{Modèles de calculabilité}

% Solution exercice: réduire 1 + 2 (4.81)
\solexercice{exerc:reduire12}
Représentons d'abord \(1\) et \(2\) en expressions lambda.
$$\begin{array}{ll}
	1 \iff \lambda f \lambda c (fc)\\
	2 \iff \lambda f \lambda c (f(fc))\\
\end{array}$$
Par la règle de l'addition (\ref{prop:additionlambda}), nous trouvons
$$\begin{array}{ll}
	[\textcolor{red}{1}+\textcolor{blue}{2}] & \iff \lambda a \lambda b ( ( ( \textcolor{red}{\lambda f \lambda c (fc)} )a ) ( ( ( \textcolor{blue}{\lambda f \lambda c (f(fc))})a)b) ) \\
	& \iff \lambda a \lambda b ((\textcolor{red}{\lambda c (a c)}) ((\textcolor{blue}{\lambda c (a(a(c)))})b)) \\
	& \iff \lambda a \lambda b ((\textcolor{red}{\lambda c (a c)}) (\textcolor{blue}{(a(a(b)))}))\\
	& \iff \lambda a \lambda b (a(a(a(c))))
\end{array}$$
Ce qui est bien la représentation lambda de \(3\).
%------------------------------------------------------
\section{Analyse de la thèse de Church-Turing}




%------------------------------------------------------
\section{Complexité}




%------------------------------------------------------
\section{Classes de complexité}