diff options
Diffstat (limited to 'exercices-inf110.tex')
| -rw-r--r-- | exercices-inf110.tex | 42 |
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}$ : |