diff options
| -rw-r--r-- | exercices-inf110.tex | 28 |
1 files changed, 14 insertions, 14 deletions
diff --git a/exercices-inf110.tex b/exercices-inf110.tex index 71a7beb..7b163fd 100644 --- a/exercices-inf110.tex +++ b/exercices-inf110.tex @@ -125,7 +125,7 @@ $\mathbb{N}$ décidable réfute (1), et le fait que $\varnothing % -\exercice\label{exercice-image-calculable-est-semi-decidable}\ (${\star}{\star}$)\par\nobreak +\exercice\label{exercise-computable-image-is-semidecidable}\ (${\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) @@ -178,7 +178,7 @@ est indécidable : c'est exactement ce qui était demandé. % -\exercice\label{exercice-image-fonction-partielle-calculable}\ (${\star}{\star}{\star}$)\par\nobreak +\exercice\label{exercise-image-computable-partial-function}\ (${\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 @@ -224,7 +224,7 @@ remplacer $\tilde f \colon \mathbb{N}^2 \to \mathbb{N}, (n,m) \mapsto n,m\rangle \mapsto \tilde f(n,m)$, on a $f(\mathbb{N}) = B$. \textbf{(2)} Ici on ne peut pas appliquer bêtement l'algorithme exposé -dans l'exercice \ref{exercice-image-calculable-est-semi-decidable} +dans l'exercice \ref{exercise-computable-image-is-semidecidable} question (1) car si le calcul de $f(i)$ ne termine pas, il bloquera tous les suivants. Il faut donc mener le calcul des $f(i)$ « en parallèle ». On va procéder par énumération des couples $(n,i)$ et @@ -257,7 +257,7 @@ grand on va finir par tester le couple $(n,i)$.) % -\exercice\label{exercice-indices-fonctions-totales}\ (${\star}{\star}{\star}$)\par\nobreak +\exercice\label{exercise-indices-total-functions}\ (${\star}{\star}{\star}$)\par\nobreak Soit \[ @@ -397,7 +397,7 @@ une contradiction ». % -\exercice\label{exercice-graphe-calculable}\ (${\star}{\star}{\star}$)\par\nobreak +\exercice\label{exercise-computable-graph}\ (${\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 : @@ -413,7 +413,7 @@ commencer par s'entraîner en montrant que (2) implique (1). Pour montrer que (3) implique (1), on pourra chercher une façon de tester en parallèle un nombre croissant de valeurs de $q$ de manière à s'arrêter si l'une quelconque convient. On peut s'inspirer de -l'exercice \ref{exercice-image-fonction-partielle-calculable} +l'exercice \ref{exercise-image-computable-partial-function} question (2).) \begin{corrige} @@ -466,7 +466,7 @@ que $f$ était calculable puisqu'on a exhibé un algorithme qui la calcule. (Comme dans -l'exercice \ref{exercice-image-fonction-partielle-calculable}, on peut +l'exercice \ref{exercise-image-computable-partial-function}, on peut utiliser le $T$ de la forme normale de Kleene au lieu de parler d'« étapes » d'exécution d'une machine de Turing. Aussi, plutôt qu'utiliser le codage des couples $\langle n,i\rangle$, on peut @@ -479,7 +479,7 @@ tester le couple $(n,q)$.) % -\exercice\label{exercice-reconnaitre-fonctions-p-r}\ (${\star}{\star}{\star}$)\par\nobreak +\exercice\label{exercise-recognizing-p-r-functions}\ (${\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 @@ -537,7 +537,7 @@ exactement que $N$ est indécidable. % -\exercice\label{exercice-diagonalisation-0-1-fonctions-p-r}\ (${\star}{\star}{\star}{\star}$)\par\nobreak +\exercice\label{exercise-diagonalization-0-1-p-r-functions}\ (${\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 @@ -600,7 +600,7 @@ décidable. \begin{corrige} Comme dans le début du corrigé de -l'exercice \ref{exercice-diagonalisation-0-1-fonctions-p-r}, on +l'exercice \ref{exercise-diagonalization-0-1-p-r-functions}, on explique qu'on peut décider si $\psi^{(1)}_e(n)\downarrow$ (il s'agit juste de vérifier si $e$ est un code valable de fonction p.r.) et, une fois ce point vérifié, si $\psi^{(1)}_e(n) = 0$ (on peut calculer @@ -796,7 +796,7 @@ calculée en complexité en temps p.r., donc elle est elle-même p.r. % -\exercice\label{exercice-tableaux-fonctions-p-r}\ (${\star}{\star}{\star}$)\par\nobreak +\exercice\label{exercise-arrays-for-p-r-functions}\ (${\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 @@ -901,7 +901,7 @@ $A(m,n,k)$ est bien calculée par cet algorithme. \textbf{(2)} Expliquer pourquoi l'algorithme qu'on a écrit en (1) est primitif récursif (on pourra prendre connaissance des conclusions de -l'exercice \ref{exercice-tableaux-fonctions-p-r}). +l'exercice \ref{exercise-arrays-for-p-r-functions}). \textbf{(3)} En déduire que la fonction $B$ est primitive récursive. @@ -1009,7 +1009,7 @@ cherchait, alors l'algorithme renvoie $A(m,n,k)$. \textbf{(2)} L'algorithme qu'on a décrit ci-dessus ne fait aucun appel récursif et n'utilise que des boucles bornées (deux boucles imbriquées). L'utilisation d'un tableau est justifiée par -l'exercice \ref{exercice-tableaux-fonctions-p-r}. On a donc bien +l'exercice \ref{exercise-arrays-for-p-r-functions}. On a donc bien défini une fonction primitive récursive. \textbf{(3)} L'algorithme qu'on a décrit calcule de façon primitive @@ -1024,7 +1024,7 @@ l'algorithme n'a pas réussi à caluler $A(m,n,k)$ on renvoie « non » (On dit parfois abusivement que la fonction d'Ackermann a un graphe primitif récursif pour dire que la fonction indicatrice de son graphe est primitive récursive. On comparera à -l'exercice \ref{exercice-graphe-calculable} d'après lequel une +l'exercice \ref{exercise-computable-graph} d'après lequel une fonction dont la fonction indicatrice du graphe est calculable, i.e., générale récursive, est elle-même calculable, i.e., générale récursive.) |