Prepare exercise sheet for publication.

1 files changed, 23 insertions, 19 deletions

diff --git a/exercices-inf110.tex b/exercices-inf110.tex
index 76130f0..ec141fe 100644
--- a/exercices-inf110.tex
+++ b/exercices-inf110.tex
@@ -42,7 +42,11 @@
 %
 %
 \begin{document}
+\ifcorrige
+\title{Logique et Fondements de l'Informatique\\Exercices corrigés}
+\else
 \title{Logique et Fondements de l'Informatique\\Exercices}
+\fi
 \author{David A. Madore}
 \maketitle
 
@@ -71,7 +75,7 @@ Git: \input{vcline.tex}
 \section{Calculabilité}
 
 
-\exercice\ (${\star}$)
+\exercice\ (${\star}{\star}$)\par\nobreak
 
 On considère la fonction $f\colon \mathbb{N} \to \mathbb{N}$ qui à $n
 \in \mathbb{N}$ associe le $n$-ième chiffre de l'écriture décimale de
@@ -102,7 +106,7 @@ calculable.  Mieux : comme la boucle utilisée est bornée \textit{a
 
 %
 
-\exercice\ (${\star}$)
+\exercice\ (${\star}$)\par\nobreak
 
 Supposons que $A \subseteq B \subseteq \mathbb{N}$.  \textbf{(1)} Si
 $B$ est décidable, peut-on conclure que $A$ est décidable ?
@@ -120,7 +124,7 @@ $\mathbb{N}$ décidable réfute (1), et le fait que $\varnothing
 
 %
 
-\exercice\label{exercice-image-calculable-est-semi-decidable}\ (${\star}$)
+\exercice\label{exercice-image-calculable-est-semi-decidable}\ (${\star}{\star}$)\par\nobreak
 
 \textbf{(1)} Soit $f\colon \mathbb{N} \to \mathbb{N}$ totale
 calculable.  Montrer que l'image $f(\mathbb{N})$ (c'est-à-dire $\{f(i)
@@ -153,7 +157,7 @@ boucle potentiellement infinie comme une boucle pour $i$ allant de $0$
 
 %
 
-\exercice\ (${\star}$)
+\exercice\ (${\star}$)\par\nobreak
 
 Montrer que l'ensemble des $e\in \mathbb{N}$ tels que
 $\varphi^{(1)}_e(0) = \varphi^{(1)}_e(1)$ (rappel : ceci signifie que
@@ -173,7 +177,7 @@ est indécidable : c'est exactement ce qui était demandé.
 
 %
 
-\exercice\label{exercice-image-fonction-partielle-calculable}\ (${\star}{\star}$)
+\exercice\label{exercice-image-fonction-partielle-calculable}\ (${\star}{\star}{\star}$)\par\nobreak
 
 \textbf{(1)} Soit $B \subseteq \mathbb{N}$ semi-décidable et non-vide.
 Montrer qu'il existe $f\colon \mathbb{N} \to \mathbb{N}$ totale
@@ -252,7 +256,7 @@ grand on va finir par tester le couple $(n,i)$.)
 
 %
 
-\exercice\label{exercice-indices-fonctions-totales}\ (${\star}$)
+\exercice\label{exercice-indices-fonctions-totales}\ (${\star}{\star}{\star}$)\par\nobreak
 
 Soit
 \[
@@ -392,7 +396,7 @@ une contradiction ».
 
 %
 
-\exercice\label{exercice-graphe-calculable}\ (${\star}{\star}$)
+\exercice\label{exercice-graphe-calculable}\ (${\star}{\star}{\star}$)\par\nobreak
 
 Soit $f\colon \mathbb{N} \to \mathbb{N}$ une fonction totale : montrer
 qu'il y a équivalence entre les affirmations suivantes :
@@ -474,7 +478,7 @@ tester le couple $(n,q)$.)
 
 %
 
-\exercice\label{exercice-reconnaitre-fonctions-p-r}\ (${\star}{\star}$)
+\exercice\label{exercice-reconnaitre-fonctions-p-r}\ (${\star}{\star}{\star}$)\par\nobreak
 
 Si $e \mapsto \psi^{(1)}_e$ est la numérotation standard des fonctions
 primitives récursives en une variable (= d'arité $1$) et $e \mapsto
@@ -532,13 +536,13 @@ exactement que $N$ est indécidable.
 
 %
 
-\exercice\label{exercice-diagonalisation-0-1-fonctions-p-r}\ (${\star}{\star}{\star}$)
+\exercice\label{exercice-diagonalisation-0-1-fonctions-p-r}\ (${\star}{\star}{\star}{\star}$)\par\nobreak
 
 On considère la fonction $f\colon \mathbb{N}^2 \to \mathbb{N}$ qui à
-$(e,x)$ associe $1$ si $\psi^{(1)}_e(x) = 0$ et $0$ sinon (y compris
-si $\psi^{(1)}_e$ n'est pas définie), où $e \mapsto \psi^{(1)}_e$ est
-la numérotation standard des fonctions primitives récursives en une
-variable (= d'arité $1$).
+$(e,x)$ associe $1$ si $\psi^{(1)}_e(x) = 0$, et $0$ sinon (y compris
+si $\psi^{(1)}_e$ n'est pas définie) ; ici, $e \mapsto \psi^{(1)}_e$
+est la numérotation standard des fonctions primitives récursives en
+une variable (= d'arité $1$).
 
 La fonction $f$ est-elle calculable ?  Est-elle primitive récursive ?
 On expliquera précisément pourquoi.  (On s'inspirera de résultats vus
@@ -579,7 +583,7 @@ quelle.
 
 %
 
-\exercice\ (${\star}{\star}{\star}$)
+\exercice\ (${\star}{\star}{\star}{\star}$)\par\nobreak
 
 Soit
 \[
@@ -645,7 +649,7 @@ essentiellement identique.)
 
 %
 
-%% \exercice\ (${\star}$)
+%% \exercice\ (${\star}{\star}$)\par\nobreak
 
 %% Montrer qu'il existe une machine de Turing qui, quand on la lance sur
 %% la configuration vierge (c'est-à-dire un ruban vierge et dans
@@ -661,7 +665,7 @@ essentiellement identique.)
 
 %
 
-\exercice\ (${\star}$)
+\exercice\ (${\star}{\star}{\star}$)\par\nobreak
 
 On rappelle que le mot « configuration », dans le contexte de
 l'exécution d'une machine de Turing, désigne la donnée de l'état
@@ -732,7 +736,7 @@ $\mathscr{F}$ n'était pas décidable.
 
 %
 
-\exercice\ (${\star}{\star}$)
+\exercice\ (${\star}{\star}{\star}{\star}$)\par\nobreak
 
 Soit $f \colon\mathbb{N} \to \mathbb{N}$ une fonction calculable par
 une machine de Turing en \emph{complexité d'espace} primitive
@@ -792,7 +796,7 @@ p.r.
 
 %
 
-\exercice\label{exercice-tableaux-fonctions-p-r}\ (${\star}{\star}$)
+\exercice\label{exercice-tableaux-fonctions-p-r}\ (${\star}{\star}{\star}$)\par\nobreak
 
 On s'intéresse à des tableaux d'entiers naturels, indicés par les
 entiers naturels, dont toutes les valeurs valent $0$ sauf un nombre
@@ -847,7 +851,7 @@ chaque tour de boucle).
 
 %
 
-\exercice\ (${\star}{\star}{\star}$)
+\exercice\ (${\star}{\star}{\star}{\star}{\star}$)\par\nobreak
 
 On rappelle la définition de la fonction d'Ackermann $A\colon
 \mathbb{N}^3 \to \mathbb{N}$ :