summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--exercices-inf110.tex28
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.)