Autrement dit, la limite des $m$ premières << colonnes >> de la fonction $f$ est déjà atteinte et a la bonne valeur. Nous appellerons ces couples des conditions, car elles conditionnent une partie du comportement de la fonction $f$.

De la même manière que la relation de suffixe $\sigma \preceq \tau$ pour les chaînes binaires signifie que $\tau$ est une approximation plus précise de la suite que l'on construit, nous allons définir une relation d'extension sur les conditions $(g, m) \preceq (h, n)$ pour signifier que la condition $(h, n)$ est plus précise, ou plus contraignante, que la condition $(g, m)$.

Étant donné une fonction partielle $h \subseteq \mathbb{N} \times \mathbb{N} \to \{0,1\}$, on notera $\text{dom } h$ son domaine de définition. On dit donc que la condition $(h, n)$ étend $(g, m)$ (noté $(h, n) \succeq (g, m)$) si $n \ge m$ et si, en outre,

(P1) $g \subseteq h$, c'est-à-dire $\text{dom } g \subseteq \text{dom } h$ et pour tout $(x, y) \in \text{dom } g$,

$$g(x, y) = h(x, y);$$

(P2) pour tout $(x, y) \in \text{dom } h \setminus \text{dom } g$, si $x < m$, alors $h(x, y) = \emptyset''(x)$.

La propriété (P1) signifie que les fonctions finies doivent être compatibles, et plus précisément que la fonction $h$ doit étendre la fonction $g$, tandis que la propriété (P2) formalise l'idée selon laquelle le second paramètre d'une condition fixe les colonnes de la fonction en les stabilisant. La figure 10.3 illustre ce qui vient d'être expliqué.

Arrêtons-nous un instant pour nous familiariser avec ce nouvel objet mathématique et apprendre à le manipuler. Tout d'abord, pour toute condition $(g, m)$ et tout $n$, $(g, n)$ est également une condition. Si de plus $n \ge m$, alors $(g, n)$ est une extension. L'entier $m$ n'impose aucune contrainte en soi sur la fonction finie $g$ pour former une condition $(g, m)$. En revanche, $m$ impose des restrictions sur les extensions de $(g, m)$. Plus précisément, si $n \ge m$, alors l'ensemble des extensions de $(g, n)$ est un sous-ensemble des extensions de $(g, m)$. Enfin, $(\emptyset, 0)$ est une condition valide, où $\emptyset$ est la fonction définie nulle part.

Du point de vue de la calculabilité, l'ensemble des conditions est un ensemble calculable. En revanche, la relation d'extension entre deux conditions n'est pas calculable à cause de la propriété (P2) qui fait intervenir $\emptyset''$. Cependant, si l'on fixe $m$, alors la relation d'extension entre des conditions ayant $m$ pour seconde composante est calculable, car cela ne fait intervenir qu'un segment fini $\emptyset''|_m$ de l'ensemble $\emptyset''$. Il suffit de << coder en dur >> ce segment initial dans le programme. Cette observation sera exploitée pour satisfaire les contrats $S_e$.

De la même manière que l'on note $[\sigma]$ l'ensemble des suites binaires infinies ayant pour segment initial $\sigma$, on notera $[g, m]$ l'ensemble des fonctions totales $f: \mathbb{N} \times \mathbb{N} \to \{0,1\}$ telles que $g \subseteq f$ et telles que pour
<table><thead><tr><th rowspan="2">y</th><th rowspan="2">f(0, y)</th><th rowspan="2">f(1, y)</th><th rowspan="2">f(2, y)</th><th colspan="4">m = 3</th></tr><tr><th>f(3, y)</th><th>f(4, y)</th><th>f(5, y)</th><th>f(6, y)</th></tr></thead><tbody><tr><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td></tr><tr><td>2</td><td>1</td><td>1</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td></tr><tr><td>3</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td></tr><tr><td>4</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td></tr><tr><td>5</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td></tr><tr><td>6</td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td></tr><tr><td>7</td><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td></tr><tr><td></td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td></tr><tr><td></td><td>=</td><td>=</td><td>=</td><td>=</td><td>=</td><td>=</td><td>=</td></tr><tr><td></td><td>Ø''(0)</td><td>Ø''(1)</td><td>Ø''(2)</td><td>Ø''(3)</td><td>Ø''(4)</td><td>Ø''(5)</td><td>Ø''(6)</td></tr></tbody></table>

FIGURE 10.3 – La partie en gris foncé représente une condition avec $m = 3$. La partie en gris clair représente une extension de cette condition : chaque i-ième colonne pour $i < m$ est fixée pour toute extension à une valeur qui doit correspondre au i-ième bit du double arrêt.

tout $(x, y) \notin \text{dom } g$ avec $x < m$ on a $f(x, y) = Ø''(x)$. Ainsi, $[g, m]$ est la collection de l'ensemble des fonctions candidates que l'on peut obtenir en complétant l'approximation partielle $(g, m)$. Notons que $[g, m]$ ne contient pas que des fonctions stables.

Nous allons donc construire $f$ par approximations successives sous forme de conditions

$$ (g_0, m_0) \preceq (g_1, m_1) \preceq (g_2, m_2) \preceq \dots $$

pour définir $f = \bigcup_t g_t$. Autrement dit, $\text{dom } f = \bigcup_t \text{dom } g_t$, et pour tout couple $(x, y) \in \text{dom } f$, $f(x, y) = g_t(x, y)$ pour un $t$ tel que $(x, y) \in \text{dom } g_t$. La fonction $f$ est bien définie grâce à la propriété de compatibilité (P1). Si l'on s'assure que les entiers $m_t$ deviennent arbitrairement grands, il est facile de vérifier par la propriété (P2) que la fonction $f$ résultante est stable, et a pour limite $Ø''$. Notons en particulier que $f \in \bigcap_t [g_t, m_t]$.

Une condition $(g, m)$ force un contrat $S_e$ si la propriété est satisfaite pour toute $f \in [g, m]$. Ici, nous avons remplacé les occurrences de $A$ par $f$ dans le contrat $S_e$. À chaque étape de la construction, un contrat va être forcé.

**Satisfaction d'un contrat $S_e$.** L'argument est similaire à celui de la proposition 8.2, mais en manipulant des conditions et non des chaînes binaires. Soit $(g_t, m_t)$ une condition. Les trois cas suivants se présentent.
▷ Cas 1. Il existe une entrée $x$ et une fonction $f$ dans $[g_t, m_t]$ telles que
$$ \Phi_e^f(x) \downarrow \neq C(x). $$

Dans ce cas, par la propriété de l'usage, il existe une extension $(g_{t+1}, m_t)$ de $(g_t, m_t)$ telle que $\Phi_e^f(x) \downarrow \neq C(x)$ pour toute $f$ dans $[g_{t+1}, m_t]$. Notons que $m_{t+1} = m_t$. La condition $(g_{t+1}, m_t)$ force donc le contrat $S_e$.

▷ Cas 2. Il existe une entrée $x$ telle que pour toutes les fonctions $f$ dans $[g_t, m_t]$, $\Phi_e^f(x) \uparrow$. Dans ce cas, la condition $(g_t, m_t)$ force déjà le contrat $S_e$ en s'assurant que $\Phi_e^f(x) \uparrow$.

▷ Cas 3. Aucun des deux cas précédents ne se présente. Nous allons montrer alors qu'il est possible de calculer l'ensemble $C$, et donc d'en déduire une contradiction. Voici la procédure pour calculer la valeur de $C(x)$ : chercher une condition $(h, m_t)$ étendant $(g_t, m_t)$ avec la même seconde composante $m_t$, telle que $\Phi_e^h(x) \downarrow$. Nous prétendons les deux faits suivants :

(1) il existe une telle extension, et donc que la recherche se termine ;

(2) quelle que soit $(h, m_t) \succeq (g_t, m_t)$, $\Phi_e^h(x) \downarrow \rightarrow \Phi_e^h(x) = C(x)$.

Pour montrer (1), remarquons que la négation du cas 2 signifie que pour tout $x$ (et en particulier pour ce $x$ considéré), il existe une fonction $f \in [g_t, m_t]$ telle que $\Phi_e^f(x) \downarrow$. Par la propriété de l'usage, il existe alors une condition $(h, m_t) \succeq (g_t, m_t)$ telle que $\Phi_e^h(x) \downarrow$.

Montrons (2). Si $\Phi_e^h(x) \downarrow \neq C(x)$, alors le cas 1 serait vrai en prenant n'importe quel $f \in [h, m_t] \subseteq [g_t, m_t]$. Il s'ensuit que $\Phi_e^h(x) \downarrow = C(x)$. Enfin, remarquons que nous n'avons considéré que des conditions avec le même $m_t$. Comme expliqué plus haut, pour $m_t$ fixé, la relation d'extension est calculable.

Nous avons donc décrit une procédure calculable pour déterminer la valeur de $C(x)$ quel que soit $x$, contredisant l'hypothèse selon laquelle $C$ n'est pas calculable.

Il suffit alors de satisfaire chaque contrat $S_e$ en étendant petit à petit nos conditions, tout en faisant croître « artificiellement » leurs secondes composantes vers $+\infty$ afin de s'assurer que la solution finale est bien une fonction stable dont la limite est $\emptyset''$. Cela conclut la preuve de la proposition 10.2.■

**Corollaire 10.4**

Il existe un ensemble $A$ à la fois high et Turing-incomplet. Autrement dit, $A' \geq_T \emptyset''$ et $A \not\geq_T \emptyset'$.

PREUVE. Immédiat par la proposition 10.2, en prenant $C = \emptyset'$. ■
**Remarque**

L'appellation « condition » est un nom générique emprunté à la théorie du forcing, et qui sera amené à désigner des objets mathématiques très différents tout au long de cet ouvrage, bien que correspondant tous à l'idée d'une approximation d'un objet que l'on construit. Cette notion sera développée dans le chapitre 11.

Notons que l'argument de la preuve précédente ne dépend pas spécifiquement de $\emptyset''$ et l'on aurait pu construire pour tout $B$ un ensemble $A$ tel que $A' \geq_T B$ et $A \not\geq_T C$. Nous verrons dans le chapitre 13 qu'il existe des ensembles c. e. low non calculables. Sacks [187] a également montré l'existence d'ensembles c. e. incomplets de degrés high.

Il y a une différence de taille entre les ensembles low et high : les premiers sont tous calculables en $\emptyset'$, et ils sont par conséquent en quantité dénombrable. Les deuxièmes peuvent en revanche être arbitrairement complexes, et l'on montre facilement qu'ils sont en quantité indénombrable. Nous verrons en revanche avec le corollaire 19-3.9 et la proposition 10-3.38 qu'il y a « peu » d'ensembles high, du point de vue de la théorie de la mesure et de la théorie des catégories de Baire.

Terminons ce chapitre par quelques exercices.

**Exercice 10.5. (*)** Adapter la preuve de la proposition 10.2 pour montrer que pour tout ensemble $B$ et tout ensemble non calculable $C$, il existe un ensemble $A$ tel que $A' \geq_T B$ et $A \not\geq_T C$. $\diamond$

**Exercice 10.6. (★★)** Adapter la preuve de la proposition 10.2 pour montrer qu'il existe un ensemble high incomplet et $\emptyset'$-calculable. $\diamond$

**Exercice 10.7. (★★)** Montrer par la méthode des extensions finies qu'il existe une suite d'ensembles $(A_n)_{n \in \mathbb{N}}$ deux à deux incomparables pour la réduction Turing, c'est-à-dire tels que

$$A_n \not\leq_T A_m \text{ et } A_m \not\leq_T A_n,$$

pour tous $n \neq m \in \mathbb{N}$.

$\diamond$
<figure><img src="image_32.png" /></figure>
Chapitre 5

Hiérarchie arithmétique

On introduit une hiérarchie de complexité sur les ensembles d'entiers. Les ensembles calculatoirement énumérables sont dits $\Sigma_1^0$ et leurs complémentaires sont dits $\Pi_1^0$. Les intersections dénombrables d'ensembles $\Sigma_1^0$ sont dits $\Pi_2^0$ et les réunions dénombrables d'ensembles $\Pi_1^0$ sont dits $\Sigma_2^0$, et ainsi de suite.

On appelle cette construction *hiérarchie arithmétique*, car les ensembles qu'elle contient sont exactement ceux qui sont définissables par une formule du premier ordre dans le langage de l'arithmétique de Peano. Nous reparlerons de cette équivalence dans la section 9-3. Il y a une correspondance directe entre la définition d'un ensemble par réunions/intersections, et le fait de pouvoir le définir par une formule comportant des quantificateurs $∃/∀$. Ainsi, une réunion correspond à un quantificateur $∃$ et une intersection à un quantificateur $∀$.

**Exemple 1.** L'ensemble des codes *e* pour les fonctions calculables to-tales peut s'écrire

$$ \{e \in \mathbb{N} : \forall n \exists t \Phi_e(n)[t] \downarrow\} = \bigcap_n \bigcup_t \{e \in \mathbb{N} : \Phi_e(n)[t] \downarrow\}. $$

Il s'agit d'un ensemble $\Pi_2^0$, c'est-à-dire d'une intersection dénombrable d'ensembles $\Sigma_1^0$, chacun d'entre eux étant par ailleurs une réunion dénombrable d'ensembles calculables.
# 1. Propriétés élémentaires

Commençons par une définition formelle de la hiérarchie arithmétique.

**Définition 1.1.** Soient $m, n \ge 1$.

1. Un ensemble $A \subseteq \mathbb{N}^m$ est dit $\Sigma_n^0$ s'il existe un ensemble calculable $R$ inclus dans $\mathbb{N}^{n+m}$ tel que

$$ A = \{(y_1, \dots, y_m) : \underbrace{\exists x_1 \forall x_2 \dots Q x_n}_{n \text{ quantificateurs}} (x_1, \dots, x_n, y_1, \dots, y_m) \in R\}, $$
où $Q$ vaut $\exists$ si $n$ est impair, et $\forall$ si $n$ est pair.

2. Un ensemble $A \subseteq \mathbb{N}^m$ est dit $\Pi_n^0$ s'il existe un ensemble calculable $R$ inclus dans $\mathbb{N}^{n+m}$ tel que

$$ A = \{(y_1, \dots, y_m) : \underbrace{\forall x_1 \exists x_2 \dots Q x_n}_{n \text{ quantificateurs}} (x_1, \dots, x_n, y_1, \dots, y_m) \in R\}, $$
où $Q$ vaut $\forall$ si $n$ est impair, et $\exists$ si $n$ est pair. ◇

Attention dans la définition précédente, c'est l'alternance entre les quantificateurs $\exists$ et $\forall$ qui compte.

Ainsi, par exemple, l'ensemble

$$ \{y : \exists x_1 \forall x_2 R(y, x_1, x_2)\} $$

pour $R$ calculable est un ensemble $\Sigma_2^0$, mais l'ensemble

$$ \{y : \exists x_1 \exists x_2 \exists x_3 R(y, x_1, x_2, x_3)\} $$

est, malgré ses trois quantificateurs, un ensemble $\Sigma_1^0$: on peut facilement éliminer les répétitions de quantificateurs du même type. Considérons par exemple une formule de la forme

$$ \exists x_1 \exists x_2 \forall y_1 \forall y_2 R(x_1, x_2, y_1, y_2). $$

Cette dernière pourra simplement se récrire sous la forme $\exists x \forall y R'(x, y)$ où $R'$ sera une version de $R$ modifiée, qui considérera $x$ et $y$ respectivement comme des paires $\langle x_1, x_2 \rangle$ et $\langle y_1, y_2 \rangle$. Le prédicat $R'$ utilisera alors les projections $\pi_1$ et $\pi_2$ réalisant les fonctions inverses de la bijection calculable de couplage $\langle \cdot, \cdot \rangle : \mathbb{N}^2 \to \mathbb{N}$, afin de récupérer $x_1, x_2, y_1, y_2$. Le lecteur peut revenir à l'exercice 3-2.3 pour se convaincre que la bijection $\langle \cdot \rangle$ et que ses deux fonctions inverses sont calculables. Un abus de notation consistera par exemple à écrire $\exists \langle x_1, x_2 \rangle \forall \langle y_1, y_2 \rangle R(x_1, x_2, y_1, y_2)$, signifiant que le prédicat $R$ se charge de récupérer $x_1, x_2$ à partir de $\langle x_1, x_2 \rangle$, et de même pour $y_1, y_2$.
Prédicats

On parlera parfois de prédicats $\Sigma_n^0$ pour désigner une formule de la forme $\exists x_1 \forall x_2 \dots Qx_n R(x_1, x_2, \dots, x_n)$, où R est un prédicat calculable.

Notez qu’en utilisant le fait que le complémentaire d’un ensemble calculable est calculable, on voit facilement que les ensembles $\Sigma_n^0$ sont les complémentaires des ensembles $\Pi_n^0$. Il est par ailleurs tout à fait possible pour un ensemble d’être à la fois $\Sigma_n^0$ et $\Pi_n^0$. On introduit pour cela la notion suivante.

**Définition 1.2.** Soit $m \ge 1$. Un ensemble $A \subseteq \mathbb{N}^m$ est dit $\Delta_n^0$ pour $n > 0$ s’il est à la fois $\Sigma_n^0$ et $\Pi_n^0$. ♦

La hiérarchie arithmétique établit un premier niveau de distinction entre les ensembles arithmétiquement définissables. Intuitivement, un ensemble $\Sigma_{n+1}^0$ est strictement plus complexe qu’un ensemble $\Sigma_n^0$ ou même $\Pi_n^0$. En effet, chacun des deux derniers peut s’écrire sous une forme $\Sigma_{n+1}^0$ en rajoutant simplement des quantificateurs inutilisés.

**Exemple 1.3.** L’ensemble $\Sigma_2^0$ donné par $\{y : \exists x_1 \forall x_2 R(y, x_1, x_2)\}$ peut également s’écrire sous une forme $\Pi_3^0 : \{y : \forall z \exists x_1 \forall x_2 R(y, x_1, x_2)\}$ ou sous une forme $\Sigma_3^0 : \{y : \exists x_1 \forall x_2 \exists z R(y, x_1, x_2)\}$.

En revanche, il n’est pas toujours possible d’utiliser moins de quantificateurs. Nous allons montrer avec le corollaire 5.6 qu’il existe pour tout $n > 0$ des ensembles $\Delta_{n+1}^0$ qui ne peuvent être décrits de manière $\Sigma_n^0$ ou $\Pi_n^0$: la hiérarchie arithmétique est stricte.

Donnons avant de continuer quelques exemples d’ensembles de la hiérarchie arithmétique.

**Exemple 1.5.** ▷ Tout ensemble $A \subseteq \mathbb{N}$ calculable est $\Delta_1^0$ (nous en verrons une preuve avec la proposition 3.4). Il suffit de rajouter une quantification existentielle ou universelle inutile au prédicat calculable $A$ pour pouvoir l’exprimer respectivement comme ensemble $\Sigma_1^0$ ou $\Pi_1^0$.

▷ Tout ensemble $A \subseteq \mathbb{N}$ calculatoirement énumérable est $\Sigma_1^0$ (nous le verrons précisément avec la proposition 3.3). En effet, un tel $A$ est décrit comme $\{x : \exists t \Phi_e(x)[t] \downarrow\}$ pour un certain $e$.

▷ Nous avons vu avec l'exemple 1 que l'ensemble des codes de fonctions totales est $\Pi_2^0$. Son complémentaire, à savoir l'ensemble des codes de fonctions partielles, est donc $\Sigma_2^0 : \{e : \exists n \forall t \Phi_e(n)[t] \uparrow\}$
<figure><img src="image_33.png" /><figcaption>FIGURE 1.4 – Représentation de la hiérarchie arithmétique. Le triangle supérieur gauche hachuré représente les $\Sigma_1^0$. Le triangle inférieur gauche hachuré représente les $\Pi_1^0$. L'intersection entre les deux — le triangle doublement hachuré — représente les $\Delta_1^0$. Le reste du diagramme continue de la même manière.</figcaption></figure>

▷ L'ensemble des codes de fonctions qui sont totales, sauf pour un nombre fini d'éléments, est $\Sigma_3^0$ :

$$ \{e : \exists n \forall m \exists t \text{ tel que } m < n \text{ ou } \Phi_e(m)[t] \downarrow\} $$

Nous verrons un peu plus loin que les exemples précédents sont optimaux. Par exemple, l'ensemble des codes de fonctions qui sont totales sauf pour un nombre fini d'éléments ne peut pas s'exprimer de manière $\Pi_3^0$: il s'agit d'un ensemble $\Sigma_3^0$ strict.

Nous montrons à présent une série de trois propositions sur la stabilité des ensembles $\Sigma_m^0$ et $\Pi_m^0$ par différentes opérations. Par exemple, la stabilité par réunion finie signifie qu'une réunion finie d'ensembles $\Sigma_m^0$ est encore un ensemble $\Sigma_m^0$. Les propositions seront démontrées uniquement en considérant des sous-ensembles de $\mathbb{N}$, mais se généralisent sans problème aux sous-ensembles de $\mathbb{N}^n$ pour $n$ arbitraire.

**Proposition 1.6.** Les ensembles $\Sigma_m^0$ (resp. $\Pi_m^0$) sont stables par réunions finies et intersections finies.

<figure><img src="image_34.png" /></figure>

PREUVE. Soit $m > 0$. Soient

$$ A_0 = \{n : \exists x_1 \forall x_2 \dots Q x_m R_0(n, x_1, \dots, x_m)\} $$

$$ A_1 = \{n : \exists y_1 \forall y_2 \dots Q y_m R_1(n, y_1, \dots, y_m)\} $$

deux ensembles $\Sigma_m^0$, où $Q$ est le symbole $\exists$ si $m$ est impair et $\forall$ si $m$ est pair. On laisse au lecteur le soin de montrer, par inclusion dans un sens
puis dans l'autre, que :

$$A_0 \cap A_1 = \{ n : \exists \langle x_1, y_1 \rangle \forall \langle x_2, y_2 \rangle \dots Q \langle x_m, y_m \rangle \\ \text{tels que } R_0(n, x_1, \dots, x_m) \wedge R_1(n, y_1, \dots, y_m) \}.$$

Les ensembles $\Sigma_m^0$ sont donc stables par intersections finies. On a par ailleurs de la même manière :

$$A_0 \cup A_1 = \{ n : \exists \langle x_1, y_1 \rangle \forall \langle x_2, y_2 \rangle \dots Q \langle x_m, y_m \rangle \\ \text{tels que } R_0(n, x_1, \dots, x_m) \vee R_1(n, y_1, \dots, y_m) \}.$$

Les ensembles $\Sigma_m^0$ sont donc stables par réunions finies. Par passage au complémentaire, les ensembles $\Pi_m^0$ sont eux aussi stables par réunions et intersections finies. ■

Souvenons-nous du concept de suite uniformément calculable, introduit à l'occasion des développements qui suivent le lemme 4-7.2. Le concept d'uniformité passe à la hiérarchie arithmétique de la manière suivante : dans la prochaine proposition, une réunion dénombrable $(A_i)_{i \in \mathbb{N}}$ d'ensembles uniformément $\Sigma_m^0$ est donc une réunion telle que chaque ensemble $A_i$ admet la même description $\Sigma_m^0$, mais avec comme paramètre $i$. Formellement, si

$$A_i = \{ n : \exists x_1 \forall x_2 \dots Q x_m R_i(n, x_1, \dots, x_m) \},$$

il faut qu'il existe un processus calculable permettant à partir de $i$ de renvoyer un code pour le prédicat $R_i$. De manière équivalente, on peut considérer que $A_i$ est décrit comme

$$A_i = \{ n : \exists x_1 \forall x_2 \dots Q x_m R(i, n, x_1, \dots, x_m) \},$$

où $R$ est un prédicat calculable prenant $i$ comme paramètre supplémentaire.

**Proposition 1.7.** Les ensembles $\Sigma_m^0$ (resp. $\Pi_m^0$) sont stables par réunions dénombrables uniformes (resp. intersections dénombrables uniformes). ★

**PREUVE.** Soit $m > 0$, et soit $(A_i)_{i \in \mathbb{N}}$ une suite d'ensembles uniformément $\Sigma_m^0$: $$A_i = \{ n : \exists x_1 \forall x_2 \dots Q x_m R(i, n, x_1, \dots, x_m) \},$$

où $Q$ est le symbole $\exists$ si $m$ est impair et $\forall$ si $m$ est pair. On montre aisément par inclusion dans un sens puis dans l'autre que

$$\bigcup_i A_i = \{ n : \exists \langle i, x_1 \rangle \forall x_2 \dots Q x_m R(i, n, x_1, \dots, x_m) \}.$$

Les ensembles $\Sigma_m^0$ sont donc stables par réunions dénombrables uniformes. Par passage au complémentaire, les ensembles $\Pi_m^0$ sont eux aussi stables par intersections dénombrables uniformes. ■
Notons que la stabilité des ensembles $\Sigma_n^0$ par réunion dénombrable uniforme équivaut à la stabilité par quantification existentielle (resp. quantification universelle pour les ensembles $\Pi_n^0$).

**Exercice 1.8.** Montrer que les ensembles $\Sigma_n^0$ ne sont pas stables par réunions dénombrables non uniformes. ◇

On montre à présent la stabilité par quantification bornée uniforme. Une quantification bornée de la forme $\forall x < m$ peut être vue comme une réunion finie de $m$ ensembles paramétrés par $x$. La proposition suivante n'est toutefois pas identique à la proposition 1.6 : on veut ici l'uniformité en fonction de la borne qui peut elle-même être une variable, ou dépendre d'autres variables sur lesquelles on quantifie. Grosso modo, ce que dit la proposition suivante est que l'ensemble

$$ \{n : \exists x \forall y < x \exists t R(n, x, y, t)\}, $$

où $R$ est un prédicat calculable, peut se récrire comme

$$ \{n : \exists x \exists t \forall y < x \exists s < t R(n, x, y, s)\}. $$

Le prédicat $\forall y < x \exists s < t R(n, x, y, s)$ étant calculable, l'ensemble est $\Sigma_1^0$.

**Proposition 1.9.** Les ensembles $\Sigma_m^0$ et $\Pi_m^0$ sont stables par quantifications bornées uniformes. ★

**PREUVE.** On montre que l'on peut toujours déplacer la quantification bornée vers la droite, jusqu'à ce que celle-ci se retrouve à côté du prédicat calculable.

Soit $A = \{(n,k) : \forall y < k \exists x R(n, y, x)\}$, où $R$ est un ensemble calculable ou $\Pi_m^0$ pour $m > 0$. Alors, on a aussi

$$ A = \{(n, k) : \exists x \forall y < k \exists z < x R(n, y, z)\}. $$

L'égalité vient du fait que si pour tout $y < k$ un certain $x_k$ témoigne qu'une formule est vraie, comme le nombre de témoins est fini, ceux-ci sont bornés dans $\mathbb{N}$. La variable $x$ qui faisait auparavant office de témoin est à présent utilisée comme borne sur tous les témoins possibles. On a de la même manière par passage au complémentaire

$$ \{(n, k) : \exists y < k \forall x R(n, y, x)\} = \{(n, k) : \forall x \exists y < k \forall z < x R(n, y, z)\}, $$

où $R$ est un ensemble calculable ou $\Sigma_m^0$.

Si l'on a à présent $A = \{(n,k) : \exists y < k \exists x R(n, y, x)\}$, où $R$ est un ensemble calculable ou $\Pi_m^0$, alors on a aussi $A = \{(n,k) : \exists x \exists y < k R(n, y, x)\}$ de manière immédiate. On a de la même manière par passage au complémentaire $\{(n,k) : \forall y < k \forall x R(n, y, x)\} = \{(n,k) : \forall x \forall y < k R(n, y, x)\}$, où $R$ est un ensemble calculable ou $\Sigma_m^0$.
Par récurrence, on déplace ainsi les quantifications bornées vers la droite jusqu’à ce que celles-ci soient toutes collées au prédicat calculable. On utilise enfin le fait que les prédicats calculables sont stables par quantifications bornées (voir l’exercice 3-2.4) pour conclure. ■

## 2. Hiérarchie arithmétique et calculabilité

Voyons à présent à quoi correspondent les premiers niveaux de la hiérarchie arithmétique.

**Proposition 2.1.** Un ensemble $A \subseteq \mathbb{N}$ est $\Sigma_1^0$ ssi il est calculatoirement énumérable. ★

**PREUVE.** Supposons que l'ensemble $A$ soit calculatoirement énumérable. Alors, $A = \{n : \exists t \Phi_e(n)[t] \downarrow\}$ pour un certain $e$. Le prédicat $\Phi_e(n)[t] \downarrow$ est calculable. Donc, $A$ est $\Sigma_1^0$. Supposons à présent que $A$ soit $\Sigma_1^0$. Soit $A = \{n : \exists t R(n,t)\}$, où $R$ est un prédicat calculable. Alors, on définit facilement la machine de code $e$ qui sur l'entrée $n$ cherche le plus petit $t$ tel que $R(n,t)$ et s'arrête, ou continue sa recherche indéfiniment sinon. On a alors $\Phi_e(n) \downarrow$ ssi $\exists t R(n,t)$. ■

**Proposition 2.2.** Un ensemble $A \subseteq \mathbb{N}$ est $\Delta_1^0$ ssi il est calculable. ★

**PREUVE.** Un ensemble $A$ est $\Delta_1^0$ ssi $A \in \mathbb{N} \setminus A$ sont $\Sigma_1^0$ ssi $A \in \mathbb{N} \setminus A$ sont calculatoirement énumérables (d'après la proposition 2.1), ou encore ssi $A$ est calculable (d'après la proposition 3-7.4). ■

Nous avons vu qu'il y a des ensembles calculatoirement énumérables qui ne sont pas calculables, et en particulier dont le complémentaire n'est pas calculatoirement énumérable. Cela implique que certains ensembles sont $\Sigma_1^0$ mais pas $\Delta_1^0$, et en particulier pas $\Pi_1^0$. Nous allons voir dans les prochaines sections que la hiérarchie est stricte partout : pour tout $n$, il existe des ensembles $\Sigma_n^0$ qui ne sont pas $\Pi_n^0$, et il existe des ensembles $\Delta_{n+1}^0$ qui ne sont ni $\Sigma_n^0$, ni $\Pi_n^0$.

Intuitivement, le nombre de quantificateurs correspond au « nombre de fois qu'il faudrait compter jusqu'à l'infini » pour déterminer l'appartenance d'un élément à l'ensemble. Ainsi, pour un ensemble $\Sigma_1^0$ s'écrivant comme $\{n : \exists t R(t,n)\}$, où $R$ est un prédicat calculable, il faudrait tester la valeur de vérité de $R(t,n)$ pour tous les entiers $t$, afin d'en trouver un qui témoigne de l'appartenance de $n$ à l'ensemble, ou bien afin d'être sûr que $n$ n'y appartient pas.
Pour un ensemble $\Pi_2^0$ de la forme

$$ \{n : \forall t_1 \exists t_2 R(t_1, t_2, n)\}, $$

il faudrait une première procédure qui teste tous les entiers $t_1$, et qui pour chacun de ces tests, examine la valeur de vérité de $R(t_1, t_2, n)$ pour tous les entiers $t_2$. Cela correspondrait en quelque sorte à deux boucles imbriquées se déroulant chacune sur l'ensemble de tous les entiers.

## 3. Relativisation à un oracle

La hiérarchie arithmétique permet de définir des ensembles de plus en plus complexes, et dans un sens de moins en moins calculables. Toutefois, la classe des ensembles arithmétiquement définissables reste dénombrable. Il reste donc « beaucoup » d'ensembles, pour ainsi dire la majorité, qui ne peuvent être ni calculés, ni même définis par une formule de l'arithmétique. Il est évidemment difficile d'en parler, et toute tentative de les cerner plus précisément les rendraient définissables dans un certain langage, élargissant simplement un peu plus la classe immanquablement dénombrable des ensembles dont on arrive à dire quelque chose, laissant de côté la majorité des autres ensembles, cachés, inaccessibles.

Nous contournerons le problème tout au long des chapitres à venir, essentiellement en étudiant des « groupes d'ensembles » plutôt que chaque ensemble individuellement. Nous verrons en particulier dans les chapitres à venir de nombreuses propriétés calculatoires partagées par certains ensembles, en général une quantité indénombrable d'entre eux. Nous mènerons ensuite dans la partie II une étude des ensembles typiques du point de vue de la théorie de la mesure, c'est-à-dire des ensembles que l'on obtient avec probabilité 1 si l'on sélectionne leurs bits au hasard.

Pour le moment, nous nous contentons de relativiser la hiérarchie arithmétique à un oracle : étant donné un ensemble $X$ quelconque, on considère les ensembles $\Sigma_n^0$, $\Pi_n^0$ et $\Delta_n^0$ que l'on peut définir relativement à la connaissance de $X$. On se base pour cela sur les calculs avec oracle du théorème 4-2.2, et l'on itère comme dans la définition 1.1.

**Définition 3.1.** Soient $m, n \ge 1$. Soit $X \subseteq \mathbb{N}$.

1. Un ensemble $A \subseteq \mathbb{N}^m$ est dit $\Sigma_n^0(X)$ s'il existe un ensemble $X$-calculable $R \subseteq \mathbb{N}^{n+m}$ tel que

$n$ quantificateurs

$$ A = \{ (y_1, \dots, y_m) : \exists x_1 \forall x_2 \dots Q x_n \ (x_1, \dots, x_n, y_1, \dots, y_m) \in R \}, $$

où $Q$ vaut $\exists$ si $n$ est impair, et $\forall$ si $n$ est pair.
2. Un ensemble $A \subseteq \mathbb{N}^m$ est dit $\Pi_n^0(X)$ s'il existe un ensemble $X$-calculable $R \subseteq \mathbb{N}^{n+m}$ tel que

$n$ quantificateurs

$$A = \{(y_1, \dots, y_m) : \left. \forall x_1 \exists x_2 \dots Q x_n \ (x_1, \dots, x_n, y_1, \dots, y_m) \in R \right\},$$

où $Q$ vaut $\forall$ si $n$ est impair, et $\exists$ si $n$ est pair.

<figure><img src="image_35.png" /></figure>

**Définition 3.2.** Soit $m \ge 1$. Soit $X \subseteq \mathbb{N}$. Un ensemble $A \subseteq \mathbb{N}^m$ est dit $\Delta_n^0(X)$ pour $n > 0$ s'il est à la fois $\Sigma_n^0(X)$ et $\Pi_n^0(X)$. $\diamond$

<figure><img src="image_36.png" /></figure>

Les propositions suivantes se montrent comme leurs équivalents respectifs de la section précédente.

**Proposition 3.3.** Un ensemble $A \subseteq \mathbb{N}$ est $\Sigma_1^0(X)$ ssi il est $X$-c. e. $\star$

<figure><img src="image_37.png" /></figure>

**Proposition 3.4.** Un ensemble $A \subseteq \mathbb{N}$ est $\Delta_1^0(X)$ ssi il est $X$-calculable. $\star$

Notons qu'un oracle pourra fournir de la puissance de calcul supplémentaire, permettant à certains ensembles normalement non $\Sigma_n^0$, de devenir $\Sigma_n^0(X)$. On peut même par exemple définir un oracle $X$ tel que tous les ensembles arithmétiques, c'est-à-dire $\Sigma_n^0$ pour un certain $n$, deviennent $\Delta_1^0(X)$. Toute fois, quelle que soit la puissance de calcul de $X$, les ensembles arithmétiques en $X$ restent en quantité dénombrable.

## 4. Degrés many-one

La classification de la hiérarchie arithmétique en termes d'ensembles $\Sigma_n^0$ et $\Pi_n^0$ n'est pas une notion de degrés Turing, car un ensemble $\Sigma_n^0$ peut être Turing équivalent à un ensemble qui ne l'est pas. De fait, tout ensemble $\Sigma_n^0$ A est Turing équivalent à son complémentaire $\Pi_n^0 \bar{A}$. En ce sens, la réduction Turing est « grossière », car elle ne distingue pas un ensemble de son complémentaire.

Nous allons introduire une notion plus fine que la réduction Turing, au sens où elle implique cette dernière. Il s'agit de la réduction many-one, qui comme nous le verrons préserve la hiérarchie arithmétique. Dans les faits, beaucoup de preuves de réduction Turing que nous avons vues sont des réductions many-one.

**Définition 4.1.** Soient deux ensembles $A, B$. On dit que $A$ est *many-one réductible* à $B$, et l'on écrit $A \leq_m B$ s'il existe une fonction totale calculable $f : \mathbb{N} \to \mathbb{N}$ telle que $n \in A \leftrightarrow f(n) \in B$. Si $A \leq_m B$ et $B \leq_m A$, on écrit $A \equiv_m B$. On écrit $A <_m B$ si $A \leq_m B$ mais $B \not\leq_m A$. On appelle *degrés many-one* les classes d'équivalence de la relation $\equiv_m$. $\diamond$

<figure><img src="image_38.png" /></figure>
Quand on a $A \leqslant_m B$, la connaissance de $B$ est suffisante pour calculer $A$, et l'on a en particulier $A \leqslant_T B$ : soit $f$ la fonction totale calculable telle que $n \in A \leftrightarrow f(n) \in B$. Alors, pour savoir si $n \in A$, on utilise $f$ pour « poser une question » à l'ensemble $B$ : est-ce que $f(n) \in B$ ? Si la réponse est oui, alors $n \in A$. Sinon, $n \notin A$. La réduction many-one est très restrictive : si $A \leqslant_m B$, alors pour connaître un bit de $A$ on n'a le droit de poser qu'une seule question à l'oracle $B$. Comme si cela ne suffisait pas, la réponse à la question détermine directement l'appartenance du bit à $A$ sans qu'il ne soit possible d'inverser cette décision. L'importance de cette réduction, très restrictive, vient du fait qu'elle préserve la hiérarchie arithmétique.

**Proposition 4.2.** Soit $A \subseteq \mathbb{N}$ un ensemble $\Sigma_m^0(X)$ (resp. $\Pi_m^0(X)$) pour un certain $X \subseteq \mathbb{N}$, et soit $B \leqslant_m A$. Alors, $B$ est $\Sigma_m^0(X)$ (resp. $\Pi_m^0(X)$). ★

**PREUVE.** Soit $A$ un ensemble $\Sigma_m^0(X)$. Alors,

$$A = \{n : \exists x_1 \forall x_2 \dots Q x_m R(n, x_1, \dots, x_m)\},$$

où $R$ est un ensemble $X$-calculable. Soit $f$ la fonction totale calculable telle que $n \in B$ ssi $f(n) \in A$. On a donc

$$B = \{n : \exists x_1 \forall x_2 \dots Q x_m R(f(n), x_1, \dots, x_m)\},$$

ce qui est bien une description $\Sigma_m^0(X)$ de $B$.

On montre de la même manière que si $A$ est $\Pi_m^0(X)$ et $B \leqslant_m A$, alors $B$ est $\Pi_m^0(X)$. ■

Parmi les ensembles $\Sigma_1^0$, l'arrêt des programmes informatiques joue un rôle particulier : il est le plus « puissant » des ensembles $\Sigma_1^0$, dans le sens où tout ensemble $\Sigma_1^0$ est many-one réductible à l'arrêt.

**Proposition 4.3.** Un ensemble $A$ est $\Sigma_1^0$ si, et seulement si, $A \leqslant_m \emptyset'$. ★

**PREUVE.** Supposons $A \Sigma_1^0$. Alors, il existe $e$ tel que $n \in A$ ssi $\Phi_e(n) \downarrow$. En utilisant le théorème SMN, on définit une fonction calculable $s : \mathbb{N} \to \mathbb{N}$ telle que pour tout $m$ on ait $\Phi_e(n) = \Phi_{s(n)}(m)$. On aura en particulier $n \in A$ ssi $\Phi_e(n) \downarrow$, ou ce qui revient au même ssi $\Phi_{s(n)}(s(n)) \downarrow$, ou encore ssi $s(n) \in \emptyset'$. Donc, $A \leqslant_m \emptyset'$.

Supposons à présent $A \leqslant_m \emptyset'$. Alors, comme $\emptyset'$ est $\Sigma_1^0$, l'ensemble $A$ est lui aussi $\Sigma_1^0$, d'après la proposition 4.2. ■

On dit aussi que $\emptyset'$ est un ensemble $\Sigma_1^0$-complet, comme nous le verrons avec la définition 5.2.
# 5. Théorème de Post

Nous allons voir qu'il y a une correspondance précise entre les itérations du saut Turing et la hiérarchie arithmétique.

**Définition 5.1.** Étant donné un ensemble $X \subseteq \mathbb{N}$, on définit récursivement sur $n \ge 0$ :

1. $X^{(0)} = X$

2. $X^{(n+1)} = X^{(n)}$'.

<figure><img src="image_39.png" /></figure>

Ainsi, $\emptyset^{(1)} = \emptyset'$, $\emptyset^{(2)} = \emptyset''$, etc. Nous allons à présent montrer que, pour tout $n$, l'ensemble $\emptyset^{(n)}$ est $\Sigma_n^0$-complet : il s'agit d'un ensemble $\Sigma_n^0$, qui a également une puissance calculatoire maximale parmi les ensembles $\Sigma_n^0$, dans le sens où tout ensemble $\Sigma_n^0$ est many-one réductible à $\emptyset^{(n)}$.

**Définition 5.2.** Un ensemble $A \subseteq \mathbb{N}$ est $\Sigma_n^0(X)$-complet (resp. $\Pi_n^0(X)$-complet) s'il est $\Sigma_n^0(X)$ (resp. $\Pi_n^0(X)$) et si, pour tout ensemble $\Sigma_n^0(X)$ (resp. $\Pi_n^0(X)$) $B$, on a $B \le_m A$.

<figure><img src="image_40.png" /></figure>

**Proposition 5.3.** Soit $n > 0$. L'ensemble $\emptyset^{(n)}$ est $\Sigma_n^0$-complet. De la même manière, pour tout ensemble $X \subseteq \mathbb{N}$, l'ensemble $X^{(n)}$ est $\Sigma_n^0(X)$-complet.★

**PREUVE.** Montrons par récurrence sur $n$ que pour tout $n > 0$ l'ensemble $\emptyset^{(n)}$ est $\Sigma_n^0$. Par définition, l'ensemble $\emptyset^{(1)}$ est $\Sigma_1^0$. Supposons que l'ensemble $\emptyset^{(n)}$ soit $\Sigma_n^0$. Alors, l'ensemble $\emptyset^{(n+1)}$ est défini comme :

$$ \left\{ \begin{array}{ll} m : \exists t \in \mathbb{N} \ \exists \sigma \in 2^{<\mathbb{N}} & \left( \begin{array}{ll} \forall s < |\sigma| & (\sigma(s) = 1 \text{ et } s \in \emptyset^{(n)}) \\ \text{ou} & (\sigma(s) = 0 \text{ et } s \notin \emptyset^{(n)}) \end{array} \right) \\ \text{et} & \Phi_m(\sigma, m)[t] \downarrow \end{array} \right\} $$

La description de $\emptyset^{(n+1)}$ se fait donc avec des quantificateurs existentiels, suivi d'un prédicat utilisant $s \in \emptyset^{(n)}$, ce qui est par récurrence $\Sigma_n^0$, et utilisant $s \notin \emptyset^{(n)}$, ce qui est par récurrence $\Pi_n^0$, et donc $\Sigma_{n+1}^0$. En utilisant les propriétés de stabilité des propositions 1.9 et 1.6, le prédicat qui suit les quantificateurs existentiels $\exists t \in \mathbb{N} \ \exists \sigma \in 2^{<\mathbb{N}}$ est en particulier $\Sigma_{n+1}^0$ uniformément en $m, \sigma$ et $t$. En utilisant à présent la stabilité par réunion dénombrable uniforme de la proposition 1.7, l'ensemble $\emptyset^{(n+1)}$ est donc $\Sigma_{n+1}^0$.

Montrons à présent par récurrence sur $n$ que tout ensemble $\Sigma_n^0$ est many-one réductible à $\emptyset^{(n)}$.

C'est le cas par la proposition 4.3 pour $n = 1$. Supposons que ce soit le cas pour un certain $n$. Soit $A = \{x : \exists y R(x, y)\}$, où $R$ est un ensemble $\Pi_n^0$.
Par récurrence, il existe une fonction totale calculable $g : \mathbb{N} \to \mathbb{N}$ telle que $(x, y) \in \mathbb{R}$ ssi $g(\langle x, y \rangle) \notin \emptyset^{(n)}$. On définit la fonction totale calculable $f$ telle que $\Phi_{f(x)}^{\emptyset^{(n)}}$ s'arrête sur toute entrée si $\exists y g(\langle x, y \rangle) \notin \emptyset^{(n)}$, et ne s'arrête sur aucune entrée sinon. On a donc $f(x) \in \emptyset^{(n+1)}$ ssi $\Phi_{f(x)}(\emptyset^{(n)}, f(x)) \downarrow$, autrement dit ssi $\exists y g(\langle x, y \rangle) \notin \emptyset^{(n)}$, ou encore ssi $\exists y R(x, y)$, ou enfin ssi $x \in A$. L'ensemble $A$ est donc many-one réductible à $\emptyset^{(n+1)}$.

La relativisation à un oracle $X$ est similaire et ne présente pas de difficulté particulière. $\blacksquare$

**Corollaire 5.4**

Un ensemble $A$ est $\Sigma_n^0(X)$ ssi $A \leq_m X^{(n)}$.

PREUVE. Par la proposition précédente et par la définition de la $\Sigma_n^0(X)$-complétude. $\blacksquare$

Nous arrivons finalement au théorème de Post.

**Théorème 5.5 (Théorème de Post)**

Soient $A$ un ensemble et $n \ge 0$.

(1) $A$ est $\Sigma_{n+1}^0$ ssi $A$ est $\Sigma_1^0(\emptyset^{(n)})$, ou encore ssi $A$ est $\emptyset^{(n)}$-c. e.

(2) $A$ est $\Delta_{n+1}^0$ ssi $A$ est $\Delta_1^0(\emptyset^{(n)})$, ou encore ssi $A \leq_T \emptyset^{(n)}$

PREUVE. Montrons (1). Par le corollaire 5.4, $A$ est $\Sigma_{n+1}^0$ ssi $A \leq_m \emptyset^{(n+1)}$. En relativisant la proposition 4.3 à $\emptyset^{(n)}$, on obtient $A \leq_m \emptyset^{(n)'}$ (qui est égal à $\emptyset^{(n+1)}$) ssi $A$ est $\Sigma_1^0(\emptyset^{(n)})$. Enfin, d'après la proposition 3.3, $A$ est $\Sigma_1^0(\emptyset^{(n)})$ ssi $A$ est $\emptyset^{(n)}$-c. e.

Montrons (2). Par définition, $A$ est $\Delta_{n+1}^0$ ssi $A$ et $\bar{A}$ sont tous les deux $\Sigma_{n+1}^0$. Par le point précédent, c'est équivalent à dire que $A$ et $\bar{A}$ sont $\emptyset^{(n)}$-c. e. En relativisant la proposition 3-7.4 à $\emptyset^{(n)}$, $A$ et $\bar{A}$ sont $\emptyset^{(n)}$-c. e. ssi $A \leq_T \emptyset^{(n)}$. Enfin, d'après la proposition 3.4, on a $A \leq_T \emptyset^{(n)}$ ssi $A$ est $\Delta_1^0(\emptyset^{(n)})$. $\blacksquare$

**Corollaire 5.6**

La hiérarchie arithmétique est stricte. En d'autres termes,

▷ pour tout $n > 0$, il existe un ensemble $\Sigma_n^0$ qui n'est pas $\Pi_n^0$ et un ensemble $\Pi_n^0$ qui n'est pas $\Sigma_n^0$;

▷ pour tout $n > 0$, il existe un ensemble $\Delta_{n+1}^0$ qui n'est ni $\Sigma_n^0$ ni $\Pi_n^0$.
PREUVE. D'après la proposition 5.3, l'ensemble $\emptyset^{(n)}$ est $\Sigma_n^0$. Il ne peut pas être $\Pi_n^0$ auquel cas il serait $\Delta_n^0$, et donc calculable en $\emptyset^{(n-1)}$ d'après le théorème 5.5, contredisant le fait que $X$ ne calcule jamais son saut Turing. On montre de la même manière que $N \setminus \emptyset^{(n)}$ est $\Pi_n^0$, mais pas $\Sigma_n^0$.

On peut enfin construire pour tout $n$ l'ensemble $\Delta_{n+1}^0$ suivant : l'ensemble $X$ tel que $X(2m) = \emptyset^{(n)}(m)$ et tel que $X(2m+1) = (N \setminus \emptyset^{(n)})(m)$. Il est clair que $X$ est $\emptyset^{(n)}$-calculable, et donc $\Delta_{n+1}^0$ d'après le théorème 5.5. Enfin, si l'on suppose par l'absurde que $X$ est $\Sigma_n^0$ (resp. $\Pi_n^0$), cela permet de donner une description $\Sigma_n^0$ de $N \setminus \emptyset^{(n)}$ en ne gardant que les bits impairs de $X$ (resp. une description $\Pi_n^0$ de $\emptyset^{(n)}$ en ne gardant que les bits pairs de $X$), ce qui est en contradiction avec le fait que $\emptyset^{(n)}$ n'est pas $\Pi_n^0$ (resp. avec le fait que $N \setminus \emptyset^{(n)}$ n'est pas $\Sigma_n^0$). ■

**Exercice 5.7.** (⋆) Montrer que, pour tous $X, Y \in 2^N$, on a $X \equiv_T Y$ ssi $X' \equiv_M Y'$. ◇

# 6. Théorème de Rice

Le théorème de Rice dit en substance qu'aucune propriété sémantique des programmes n'est décidable. Par exemple, comme vu dans l'exercice 3-6.4, il est impossible de décider si un programme informatique effectue une multiplication par 2 ou pas. Nous entendons *propriétés sémantiques* par opposition à *propriétés syntaxiques*. Ces dernières sont sensibles aux variations de code, par exemple « ce programme possède trois variables distinctes » ou « ce programme contient deux boucles *for* ». Les propriétés sémantiques ne parlent pas directement des programmes, mais des fonctions qu'ils représentent. Par exemple, les propriétés « cete fonction est définie sur l'entrée 42 » ou « cette fonction ne renvoie que des valeurs paires » sont des propriétés sémantiques. Elles ne dépendent pas des détails d'implémentation des fonctions concernées.

**Définition 6.1.** Un ensemble sémantique de codes est un ensemble $A$ inclus dans $N$, tel que pour tous $x, y \in N$,

$$ \text{si } x \in A \text{ et } \Phi_x = \Phi_y, \text{ alors } y \in A. \diamond $$

Parmi les ensembles sémantiques de codes, on notera l'ensemble vide $\emptyset$ qui correspond à une propriété jamais satisfaite, et l'ensemble $N$ représentant une propriété toujours vraie. Un ensemble sémantique de codes est non trivial si $A \neq \emptyset$ et $A \neq N$.
**Théorème 6.2**

Si $A$ est un ensemble sémantique de codes non trivial, alors soit $\emptyset' \leq_m A$ soit $\emptyset' \leq_m \bar{A}$.

PREUVE. Soit $\Phi_{e_0}$ la fonction nulle part définie. Supposons que $e_0 \in \bar{A}$, l'autre cas étant traité par symétrie. Comme $A$ est non trivial, $A$ est non vide. Fixons un code $e_1 \in A$. En particulier, $\Phi_{e_0} \neq \Phi_{e_1}$. Par le théorème SMN (voir le théorème 3-4.1), il existe une fonction $f : \mathbb{N} \to \mathbb{N}$ totale et calculable telle que

$$ \Phi_{f(x)}(y) = \begin{cases} \Phi_{e_1}(y) & \text{si } x \in \emptyset' \\ \uparrow & \text{si } x \notin \emptyset'. \end{cases} $$

Montrons que la fonction $f$ est une réduction many-one de $\emptyset'$ à $A$. Si $x \in \emptyset'$, alors $\Phi_{f(x)} = \Phi_{e_1}$, et ainsi $f(x) \in A$. Inversement, si $x \notin \emptyset'$, $\Phi_{f(x)} = \Phi_{e_0}$, donc $f(x) \in \bar{A}$. ■

Le théorème de Rice affirme qu'aucune propriété non triviale sur les fonctions partielles calculables n'est décidable. Bien que les applications de ce théorème soient relativement limitées en calculabilité, le théorème de Rice revêt une grande importance pour la compréhension qu'il apporte sur la nature de la calculabilité. En particulier, l'indécidabilité du problème de l'arrêt n'est pas un phénomène isolé, car il est partagé par toutes les propriétés sur les fonctions partielles calculables.

**Corollaire 6.3 (Théorème de Rice)**

Soit $C$ une classe de fonctions partielles $\mathbb{N} \to \mathbb{N}$ calculables. Alors, l'ensemble $A = \{x : \Phi_x \in C\}$ est incalculable sauf si $C = \emptyset$ ou $C$ est la classe de toutes les fonctions partielles calculables.

PREUVE. L'ensemble $A$ est un ensemble sémantique de codes. Si $C = \emptyset$ ou $C$ est la classe de toutes les fonctions partielles calculables, alors $A = \emptyset$ ou $A = \mathbb{N}$ et, dans les deux cas, $A$ est calculable. Si $C$ n'est ni vide ni la classe de toutes les fonctions partielles calculables, alors $A$ est non trivial, et par le théorème 6.2 soit $\emptyset' \leq_m A$, soit $\emptyset' \leq_m \bar{A}$. Dans les deux cas, $\emptyset' \leq_T A$, et $A$ est non calculable. ■

# 7. Codes arithmétiques

Les ensembles d'entiers sont de manière générale des objets infinis, et ne peuvent donc pas être représentés par des entiers naturels sans que certains d'entre eux ne soient omis de cette représentation. C'est l'objet de l'argument diagonal de Cantor (voir la section 2-4). Certains ensembles d'entiers peuvent cependant être décrits de manière finitaire, à commencer par les ensembles calculables.
**Définition 7.1.** Un code $\Delta_1^0$ d'un ensemble calculable $A$ est un entier $e$ tel que $\Phi_e = A$ (c'est-à-dire $\forall n \Phi_e(n) \downarrow = A(n)$). $\diamond$

Notons qu'un ensemble est calculable ssi il a un code $\Delta_1^0$. Par le lemme 3-5.1 de remplissage, tout ensemble calculable est représenté par une infinité de codes $\Delta_1^0$. D'après le théorème de Rice, l'ensemble des codes $\Delta_1^0$ d'un ensemble calculable fixé n'est pas décidable. Il n'existe même pas de procédure pour décider si un entier $e$ est un code $\Delta_1^0$ d'un ensemble. En effet, cela reviendrait à être capable d'énumérer de manière calculable tous les ensembles calculables, et nous ferait tomber sous la coupe de l'argument diagonal de Cantor.

**Exercice 7.2.** (★) Soit TOT l'ensemble des codes $\Delta_1^0$; autrement dit,
$$TOT = \{e : \Phi_e \text{ est total}\}$$

(en supposant sans perte de généralité que $\Phi_e(n)$ renvoie 0 ou 1 pour tout $n$). Prouver que TOT est $\Pi_2^0$-complet, c.-à-d. que $N \setminus \emptyset'' \leq_m TOT$. $\diamond$

Les codes $\Delta_1^0$ permettent de donner une nouvelle définition d'une suite d'ensembles uniformément calculable. Rappelons qu'une suite $X_0, X_1, \dots$ d'ensembles est uniformément calculable si la fonction $f: N \times N \to \{0,1\}$ définie par $f(x,s) = 1$ ssi $x \in X_s$ est totale calculable.

**Proposition 7.3.** Une suite $X_0, X_1, \dots$ d'ensembles est uniformément calculable si, et seulement si, il existe une suite calculable $e_0, e_1, \dots$ tel que $e_s$ est un code $\Delta_1^0$ de $X_s$ pour tout $s$. ★

PREUVE. ⇒. Supposons que $X_0, X_1, \dots$ soit uniformément calculable à travers la fonction $f: N \times N \to \{0,1\}$. Par le théorème SMN, il existe une fonction totale calculable $h: N \to N$ telle que pour tous $e, x$, on ait l'égalité $\Phi_{h(e)}(x) = f(x, e)$. Il s'ensuit que la suite $h(0), h(1), \dots$ est une suite calculable telle que $h(s)$ est un code $\Delta_1^0$ de $X_s$.

⇒. Supposons maintenant qu'il existe une suite calculable $e_0, e_1, \dots$ de codes $\Delta_1^0$. Alors, vu l'existence d'une machine universelle, la fonction $f$ définie sur $N \times N$ par $f(x,s) = \Phi_{e_s}(x) \in N$ est totale calculable, et montre que la suite d'ensembles $X_0, X_1, \dots$ est uniformément calculable. ■

Les ensembles calculatoirement énumérables sont également représentables par un système de code. On utilisera pour cela souvent la notation ci-après.

**Notation**

On note $W_e$ l'ensemble $\{n \in N : \Phi_e(n) \downarrow\}$, lequel est calculatoirement énumérable. La notation se relativise à un oracle $X$, et $W_e^X$ ou $W_e(X)$ dénotera ainsi l'ensemble $\{n \in N : \Phi_e(X, n) \downarrow\}$.
**Définition 7.4.** Un code $\Sigma_1^0$ d'un ensemble c. e. $A$ est un entier $e$ tel que $W_e = A$. $\diamond$

Toujours par le théorème de Rice, l'ensemble des codes $\Sigma_1^0$ d'un ensemble c. e. fixé n'est pas calculable. Cependant, contrairement aux codes $\Delta_1^0$, tout entier est un code $\Sigma_1^0$. Les ensembles calculables étant a fortiori calculatoirement énumérables, ils possèdent à la fois des codes $\Delta_1^0$ et $\Sigma_1^0$. La représentation par des codes $\Delta_1^0$ est cependant calculatoirement plus informative, au sens où elle donne accès à plus d'informations sur l'ensemble qu'elle représente. En particulier, la fonction partielle $f: \mathbb{N} \times \mathbb{N} \to \{0,1\}$ telle que si $e$ est un code $\Delta_1^0$ d'un ensemble $A$, est définie pour $x \in \mathbb{N}$ par $f(e,x) \downarrow= 1$ si $x \in A$ et $f(e,x) \downarrow= 0$ si $x \notin A$, est calculable$^1$, tandis que la fonction équivalente pour les codes $\Sigma_1^0$ ne l'est pas.

**Exercice 7.5.** Montrer qu'il n'existe pas de fonction $f: \mathbb{N} \times \mathbb{N} \to \{0,1\}$ qui soit totale, calculable et telle que $f(e,x) = 1$ si $x \in W_e$ et $f(e,x) = 0$ si $x \notin W_e$. $\diamond$

De manière générale, on peut représenter tout ensemble de la hiérarchie arithmétique par des entiers à l'aide du théorème de Post.

**Définition 7.6.** Un code $\Sigma_{n+1}^0$ (resp. $\Delta_{n+1}^0$) d'un ensemble $A$ est un entier $e$ tel que $W_e(\emptyset^{(n)}) = A$ (resp. $\Phi_e(\emptyset^{(n)}) = A$). $\diamond$

**Remarque**

Étant donné un ensemble $A$, on aura tendance à privilégier le type de code qui apporte le plus d'information calculatoire sur $A$. Ainsi, si $A$ est calculable, il est préférable de manipuler un code $\Delta_1^0$ plutôt que $\Sigma_1^0$.

Cette recommandation s'applique également à des concepts de calculabilité plus élaborés, comme les ensembles low. Pour rappel, un ensemble $A$ est low si $A' \le_T \emptyset'$. Comme $A \le_T A' \le_T \emptyset'$, les ensembles low sont en particulier $\Delta_2^0$, et peuvent donc être représentés par un code $\Delta_2^0$, c'est-à-dire un entier $e$ tel que $\Phi_e(\emptyset') = A$. Cependant, cette représentation perd de l'information spécifique aux ensembles low (voir l'exercice 7.11), comme la capacité de $\emptyset'$ de décider $A'$. Il est donc préférable de représenter l'ensemble $A$ par un code $e$ tel que $\Phi_e(\emptyset') = A'$.

**Définition 7.7.** Un code de lowness d'un ensemble $A$ est un entier $e$ tel que $\Phi_e(\emptyset') = A'$. $\diamond$

<footnote n="1">1. Si $e$ n'est pas un code $\Delta_1^0$, la fonction $f$ agit tout de même comme si c'était le cas, et l'on aura éventuellement alors $f(e, x) \uparrow$.</footnote>
Enfin, dans le cas des ensembles finis, il est possible de stocker plus d'information que le simple fait d'être calculable. En effet, étant donné une suite $e_0, e_1, \dots$ de codes $\Delta_1^0$ d'ensembles finis, il n'est pas possible de calculer uniformément le cardinal de ces ensembles (voir l'exercice 7.10). On préférera donc la notion de code canonique qui contient notamment l'information de la taille de l'ensemble.

**Définition 7.8.** Le code canonique d'un ensemble fini $F$ est l'entier naturel $\sum_{i \in F} 2^i$. $\diamond$

On vérifie sans peine via l'exercice suivant qu'un code canonique contient toute l'information d'un ensemble fini, y compris la possibilité de connaître son dernier élément.

**Exercice 7.9.** Soit $D_0, D_1, \dots$ la suite des ensembles finis telle que $D_n$ est de code canonique $n$.

1. Montrer que la fonction $f : \mathbb{N} \to \mathbb{N}$ définie par $f(n) = |D_n|$ est calculable.

2. Montrer que la fonction $g : \mathbb{N} \times \mathbb{N} \to \{0,1\}$ définie par $g(n,x) = 1$ ssi $x \in D_n$ est calculable. $\diamond$

Les deux exercices suivants permettent de montrer que les informations que nous donnent les codes canoniques d'ensembles finis ou les codes de lowness ne peuvent être obtenues via des codes calculables ou $\Delta_2^0$.

**Exercice 7.10. (★★)** Supposer par l'absurde qu'il existe une fonction partielle calculable $f : \mathbb{N} \to \mathbb{N}$ telle que si $e$ est un code $\Delta_1^0$ d'un ensemble fini, alors $f(e)$ renvoie la taille de cet ensemble. En utilisant le théorème du point fixe, montrer qu'il existe $a$ un code $\Delta_1^0$ d'un ensemble fini tel que la taille de cet ensemble est différente de $f(a)$. $\diamond$

**Exercice 7.11. (★★)** Supposer par l'absurde qu'il existe une fonction partielle calculable $f : \mathbb{N} \to \mathbb{N}$ telle que si $e$ est un code $\Delta_2^0$ d'un ensemble fini, alors $f(e)$ renvoie un code $\Delta_2^0$ pour $X'$. En utilisant le théorème du point fixe, montrer qu'il existe $a$ un code $\Delta_2^0$ d'un ensemble calculable $X$ tel que $f(a)$ est le code $\Delta_2^0$ d'un ensemble différent de $X'$. $\diamond$
<figure><img src="image_41.png" /></figure>
Chapitre 6

La thèse de Church-Turing

# 1. L'Entscheidungsproblem et la quête du Graal

En l'an 1928, dans une période troublée par de profondes remises en ques-
tions sur les fondements des mathématiques, David Hilbert et Wilhelm
Ackermann posèrent la question de l'existence d'un algorithme permettant
de décider de la validité de n'importe quel énoncé mathématique. Ici, le
mot *algorithme* est à prendre dans un sens large, pour désigner un ensemble
d'étapes de calcul élémentaires que peut réaliser un mathématicien. Ce défi
lancé aux logiciens et passé à la postérité sous le nom d'*Entscheidungspro-
blem* — problème de décision — marque le début d'une longue quête fon-
dationnelle sur la formalisation de la notion d'algorithme.

Les théorèmes d'incomplétude de Gödel<fnref n="1" /> prouvés en 1931, énonçant l'exist-
ence d'énoncés fondamentalement indécidables dans toute théorie raison-
nable permettant de formaliser l'arithmétique, furent particulièrement mal-
venus dans une période qui cherchait à initier une nouvelle vague d'opti-
misme et de confiance dans les mathématiques. Ils eurent aussi comme
conséquence de faire pencher la balance vers l'existence d'une solution
négative à l'Entscheidungsproblem.

Une réponse positive à l'Entscheidungsproblem aurait été un algorithme
ou une série d'étapes déterministes, permettant de démontrer tout énoncé
mathématique ou sa négation. Une réponse négative consiste quant à elle en
la preuve qu'une telle méthode systématique ne peut exister. Cette direc-
tion pose un tout autre problème, à savoir définir formellement le concept

<footnote n="1">1. Voir le chapitre 9</footnote>
d'algorithme, ou de manière à peu près équivalente, de trouver une formalisation robuste et consensuelle de la notion de fonction calculable.

Il convient de préciser que le premier ordinateur, l'ENIAC, a été construit en 1940, soit une décennie après la formulation de l'Entscheidungsproblem. La notion de fonction effectivement calculable ne fait donc pas référence à ce qui est calculable par un ordinateur, mais par l'esprit humain. Il s'agisseait de trouver un procédé systématique, ou algorithme au sens informel du terme, permettant à un mathématicien de répondre à toute question mathématique.

Plusieurs définitions furent proposées au cours des années qui suivirent, chacune conjecturée de manière plus ou moins convaincante comme capturant exactement la notion épistémologique de fonction effectivement calculable. Ces définitions furent assez rapidement prouvées équivalentes, mais peinèrent à convaincre la communauté scientifique de leur capacité à capturer toutes les fonctions effectivement calculables. Ce n'est qu'en 1936 qu'Alan Turing amena un consensus en présentant son modèle de calcul, la *machine de Turing*, avec une démonstration éclatante de son équivalence avec les autres modèles, en particulier avec celui utilisé par Gödel pour montrer son fameux théorème d'incomplétude, apportant ainsi une réponse définitive à l'Entscheidungsproblem. Le lecteur intéressé par l'histoire de la calculabilité trouvera un excellent chapitre dédié au sujet dans l'ouvrage *Turing computability : Theory and Applications* de Robert Soare.

Bien que les différents modèles de calcul aient été depuis prouvés équivalents, nous allons détailler les principaux parmi ceux qui marquèrent cette histoire, chacun présentant son propre intérêt, en mettant l'accent sur un aspect différent de la notion de fonction calculable. Dans ce qui suit, nous ne considérerons que des fonctions partielles, de $N^n$ vers $N$ pour $n \ge 1$. On écrira $g(\bar{x}) \downarrow= y$ pour signifier que $g$ est définie sur $\bar{x} \in N^n$ et vaut $y$; la notation $\bar{x}$ étant un raccourci pour $x_1, \dots, x_n$.

**Les fonctions générales récursives.** Les fonctions récursives furent introduites sous une forme restreinte par Gödel dans le cadre de ses théorèmes d'incomplétude en 1931. Cette classe de fonctions a été généralisée par Gödel et Herbrand en 1934 pour obtenir les fonctions générales récursives, capturant d'après la thèse de Church-Turing — thèse détaillée dans la section suivante — l'intégralité des fonctions calculables.

L'idée sous-tendant la définition des fonctions générales récursives est très simple : partir de quelques fonctions élémentaires, dont la calculabilité ne fait pas place au doute, puis les combiner pour obtenir de nouvelles fonctions plus complexes, toujours calculables. Quelles sont les combinaisons valides permettant de créer de nouvelles fonctions ? Si deux fonctions sont
calculables, leur composition devrait naturellement être calculable : il suffit d'exécuter en série les étapes de calcul de chacune des fonctions. De manière un peu moins évidente, les fonctions définies par récursion à partir de fonctions calculables sont encore calculables. En effet, si l'on définit une fonction $f : \mathbb{N} \to \mathbb{N}$ par $f(0) = v$ pour un entier $v$, et $f(n+1) = g(n, f(n))$ pour une fonction calculable $g : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$, pour obtenir la valeur de $f(n)$, il suffit de calculer successivement $f(1), f(2), \dots, f(n)$ à l'aide des valeurs précédentes et en suivant les étapes de calcul de la fonction $g$. Enfin, si une fonction $g : \mathbb{N} \to \mathbb{N}$ est calculable, la recherche de la plus petite entrée $n$ telle que $g(n) = 0$ est également calculable, via une boucle qui incrémente $n$ jusqu'à avoir $g(n) = 0$ (cette recherche pouvant ne jamais aboutir).

**Définition 1.1.** La classe $\mathcal{C}$ des fonctions générales récursives est la plus petite classe de fonctions partielles contenant les fonctions de base suivantes :

(a) La fonction successeur : $succ(x) = x + 1$

(b) Les fonctions constantes : $c_m^n(x_1, \dots, x_n) = m$ pour tous $n, m \ge 0$

(c) Les projections : $p_i^n(x_1, \dots, x_n) = x_i$ pour tout $n$ et tout $i \in 1, \dots, n$ et qui est close par les opérations suivantes.

(i) Composition : si $g_1, \dots, g_m \in \mathcal{C}$ sont des fonctions de $n$ variables et $h \in \mathcal{C}$ est une fonction de $m$ variables, alors la fonction

$$f(\bar{x}) = h(g_1(\bar{x}), \dots, g_m(\bar{x}))$$

est dans $\mathcal{C}$.

(ii) Récursion primitive : si $g, h \in \mathcal{C}$ sont des fonctions partielles de respectivement $n$ et $n+2$ variables, la fonction $f$ définie par $f(\bar{x}, 0) = g(\bar{x})$ et $f(\bar{x}, m+1) = h(\bar{x}, m, f(\bar{x}, m))$ est alors une fonction partielle de $n+1$ variables dans $\mathcal{C}$.

(iii) Minimisation : si $g \in \mathcal{C}$ est une fonction partielle de $n+1$ variables, alors la fonction partielle $f$ qui à $\bar{x}$ associe le plus petit entier $m$, s'il existe, tel que $g(\bar{x}, i) \downarrow$ pour tout $i \le m$ et tel que $g(\bar{x}, m) = 0$, est dans $\mathcal{C}$. Si $m$ n'existe pas, alors $f$ n'est pas définie sur $\bar{x}$.

La classe des fonctions primitives récursives est la plus petite classe de fonctions totales contenant les fonctions de (a),(b),(c) et close par les schémas (i) et (ii) de composition et récursion primitive. ◇

Les fonctions générales récursives présentent l'avantage de mettre en valeur les propriétés de clôture de la notion de fonction calculable, à commencer par la clôture par composition. Notons que les fonctions primitives récursives sont totales, contrairement aux fonctions générales récursives, pour lesquelles le schéma de minimisation introduit une possibilité de partialité. Intuitivement, son implémentation en programmation consisterait
en une boucle **while** cherchant exhaustivement un entier *m* satisfaisant la propriété. Si cet entier n'existe pas, l'exécution du programme ne sortira jamais de la boucle, et le programme ne s'arrêtera pas. Nous étudierons ce modèle de manière détaillée dans la section 3 en nous efforçant de montrer qu'il correspond bien à la notion de fonction effectivement calculable. Mentionnons avant cela deux autres modèles de calcul.

**Le λ-calcul.** Défini par Church dans les années 30, le λ-calcul est un formalisme minimaliste servant de fondement théorique aux langages de programmation. Contrairement aux fonctions générales récursives, qui manipulent deux types d'objets, à savoir les entiers et les fonctions sur les entiers, le λ-calcul n'a qu'un seul objet primitif : les λ-fonctions. Celles-ci ne prennent pas en paramètre des entiers, mais des λ-fonctions. Il faudra donc recourir au codage des entiers par des λ-fonctions pour définir une notion de fonction calculable sur les entiers.

Les λ-fonctions sont définies par un langage d'expressions, comme c'est souvent le cas en mathématiques. Par exemple, $x, y \mapsto x + y$ est une expression définissant la somme de deux entiers. Cependant, en λ-calcul, les paramètres étant eux-mêmes des λ-fonctions, les seules opérations valides sont celles de manipulation de fonctions, à savoir, l'ajout d'un paramètre à une fonction, et l'application d'une fonction à ses paramètres. Par exemple, $f \mapsto (g \mapsto f(g))$ définit la fonction qui prend en paramètre une fonction $f$, et renvoie la fonction qui prend en paramètre une fonction $g$, et renvoie le résultat de l'application de $f$ à $g$.

L'aspect minimaliste du λ-calcul facilite les raisonnements sur le formalisme en lui-même, mais demande beaucoup plus de travail pour définir des fonctions non triviales sur les entiers. Il est notamment plus difficile de se convaincre que toutes les fonctions calculables peuvent-être représentées par des λ-fonctions. Comme exprimé précédemment, il est nécessaire de fixer une convention pour représenter les entiers. Il paraît assez naturel d'identifier l'entier $n$ avec la λ-fonction prenant en entrée une λ-fonction $f$ et retournant sa $n$-ième itération. Par exemple, l'entier 0 est représenté par la fonction qui prend en entrée une fonction $f$, et renvoie sa 0-ième itération, autrement dit renvoie la fonction identité. Dans le formalisme du λ-calcul, elle s'écrit $f \mapsto (x \mapsto x)$. De la même manière, l'entier 2 correspond à la fonction $f \mapsto (x \mapsto f(f(x)))$. Appelons $\overline{n}$ la λ-fonction représentant l'entier $n$ ; une fonction $g : \mathbb{N} \to \mathbb{N}$ est λ-définissable s'il existe une λ-fonction $h$ qui à $\overline{n}$ associe $g(n)$.

La syntaxe du λ-calcul est assez absconse au premier abord, et demande un peu de manipulation pour se familiariser avec les concepts. De nos jours, de nombreuses variantes et enrichissements sont étudiés afin de fournir un fondement théorique aux langages de programmation fonctionnelle. Il s'agit d'un domaine de recherche très actif.
**Les machines de Turing.** Si le λ-calcul fournit une base théorique aux langages de programmation, les machines de Turing peuvent être vues comme précurseurs de l'ordinateur moderne.

Conçue en 1936 par Alan Turing, cette machine est inspirée de la machine à écrire de son père. Elle comporte un *ruban*, qui peut être vu comme une succession de *cases* indexées par des entiers. On peut faire l'analogie avec des bits auxquels on accède dans la mémoire d'un ordinateur via un système d'adressage. La machine dispose aussi d'une tête de lecture/écriture qui peut se déplacer d'une case à l'autre, puis en lire ou en modifier le contenu. La machine va s'exécuter en fonction d'une entrée *n*. Au début du calcul, la tête de lecture se trouve au début du ruban, dont les *n* premières cases sont initialisées à 1, tandis que les cases restantes valent 0.

<figure><img src="image_42.png" /><figcaption>Alan Turing, 1912-1954</figcaption></figure>

<figure><img src="image_43.png" /><figcaption>**FIGURE 1.3 –** *Représentation d'une machine de Turing, avec sa tête de lecture/écriture se déplaçant sur les cases du ruban*</figcaption></figure>

La machine possède également un nombre fini d'états, incluant un état de départ dans lequel elle se trouve au début du calcul, ainsi qu'un état d'arrêt qui indique la fin du calcul lorsque la machine l'atteint. Les déplacements de la tête de lecture, le remplacement de la valeur de la case courante, ainsi que les changements d'état, sont soumis à un ensemble d'instructions représentées comme suit : étant donné l'état courant de la machine et la valeur de la case où se trouve la tête de lecture, une règle va décider de l'état suivant de la machine, de changer éventuellement la valeur de la case, et
de déplacer la tête d'une case à droite ou à gauche. Une machine de Turing est donc un automate élaboré conçu pour réaliser une tâche spécifique. Dans son article fondateur, Turing a démontré l'existence d'une machine de Turing *universelle* : une machine permettant de simuler le calcul de n'importe quelle autre machine de Turing.

Contrairement aux fonctions générales récursives ou au λ-calcul, le modèle de Turing constitue un processus mécanique très concret. On peut de fait réellement construire une machine de Turing universelle. Ce modèle a notamment l'avantage de rendre explicite la notion d'étape atomique de calcul ainsi que de quantifier l'espace mémoire utilisé. Pour ces raisons, les machines de Turing sont prises comme modèle de référence pour définir la théorie de la complexité algorithmique.

**S'abstraire des modèles.** À l'instar d'une citation de Michael Fellows <fnref n="2" />, la calculabilité n'est pas plus l'étude des modèles de calcul que l'astronomie n'est la science des télescopes. La calculabilité s'émancipe très rapidement des détails d'implémentation des modèles de calcul, pour manipuler les programmes de manière abstraite. Il est malgré tout instructif de voir en détail au moins un modèle de calcul, en particulier pour se forger une intuition quand celle-ci fait défaut, et c'est ce que nous ferons très bientôt dans la section 3.

## 2. Thèse de Church-Turing

En 1934, face au succès du λ-calcul, Church soumit l'idée à Gödel selon laquelle les fonctions λ-définissables captureraient la notion de fonction effectivement calculable, laissant Gödel dubitatif. Avec le développement des fonctions générales récursives de Herbrand et Gödel la même année et la preuve de leur équivalence avec le λ-calcul, Church formula publiquement sa thèse, connue sous le nom de *thèse de Church*, affirmant que les fonctions générales récursives coïncidaient avec les fonctions effectivement calculables. Son argumentation ne convainc pas Gödel, bien qu'il fût l'un des instigateurs des fonctions générales récursives. Avec son modèle de machine éponyme, Alan Turing fit finalement consensus en 1936, en démontrant ce dernier équivalent au modèle du λ-calcul et à celui des fonctions générales récursives, ce qui conduisit à ce que l'on appelle aujourd'hui la thèse de Church-Turing.

<footnote n="2">2. « L'informatique n'est pas plus l'étude des ordinateurs, que l'astronomie n'est celle des télescopes. » [59]</footnote>
**Thèse 2.1 (Church-Turing).**

Les fonctions effectivement calculables sont celles calculables par une ma-
chine de Turing, ou de manière équivalente les fonctions générales récursives
ou encore les fonctions $\lambda$-définissables. ■

Si Church fut le premier à formuler la thèse selon laquelle les fonctions $\lambda$-définissables correspondaient aux fonctions effectivement calculables, on attribue généralement la paternité de la calculabilité à Turing. La thèse de Church-Turing n'étant pas un énoncé mathématique, il n'est pas possible de la prouver formellement. Elle peut néanmoins être validée par ce qui se rapproche le plus d'une preuve au sens social du terme, c'est-à-dire par un argument engendrant un consensus de la communauté scientifique. C'est ce à quoi Turing est parvenu par la démonstration suivante.

**La démonstration de Turing.** Pour justifier sa thèse, Turing a employé trois types d'arguments :

(1) une description du processus par lequel un mathématicien effectue un calcul et sa formalisation par une machine de Turing,

(2) la preuve de l'équivalence des machines de Turing avec les modèles de calculs existants,

(3) le développement explicite de grandes classes de fonctions calculables par les machines de Turing. Voici les grandes lignes du premier argument de Turing :

Considérons un mathématicien, M. Dupont, effectuant un calcul. M. Dupont possède un crayon et une quantité potentiellement illimitée de papier. Étant donné la précision finie de son crayon, chaque feuille ne peut contenir qu'un nombre fini de symboles. Par simplification, et sans perte de généralité, on peut considérer que chaque feuille est une case d'un ruban infini, ne contenant qu'un seul symbole appartenant à un alphabet fini suffisamment grand. Le processus de calcul est le suivant : alors qu'il se trouve dans un état mental $e_0$, M. Dupont se situe face à la feuille courante, dans son champ de vision. Il lit les notes, avant de les corriger, en effaçant et changeant le symbole écrit sur la feuille. Cette lecture va faire évoluer ses pensées, et il se retrouvera dans un état mental $e_1$. Il va potentiellement tourner la page, ou revenir en arrière pour relire des notes précédentes, jusqu'à arriver à la fin de son calcul. M. Dupont considérera alors son calcul terminé, et se retrouvera dans l'état mental correspondant que l'on appelle *état final*.

**Du bon usage de la thèse de Church-Turing.** Il convient de se faire une idée claire de ce que dit la thèse de Church-Turing, de ses limites et de son usage. La thèse de Church-Turing n'est ni un théorème, ni une conjecture. Elle ne peut être formellement prouvée ou réfutée, par le simple fait qu'elle
n'est pas un énoncé mathématique, mais plutôt un pont entre un concept mathématique et une notion épistémologique. Cette thèse n'est pas pour autant une affirmation arbitraire, car elle est étayée par un raisonnement qui peut être soumis à la critique.

Si la thèse de Church-Turing peut être remise en question, voire un jour majoritairement rejetée, le développement de la calculabilité n'en repose pas moins sur des bases solides, indépendantes de cette correspondance. L'équivalence entre les fonctions calculables par les machines de Turing, les fonctions générales récursives, les fonctions $\lambda$-définissables, et les fonctions programmables en C, Java ou Python, est bien un théorème qui ne dépend pas de la thèse de Church-Turing. S'il est fréquent en calculabilité de décrire de manière informelle un algorithme pour ensuite en déduire l'existence d'une machine de Turing l'implémentant, ce procédé n'est pas à strictement parler un appel à la thèse de Church-Turing. Il s'agit plutôt d'une preuve informelle permettant de convaincre l'interlocuteur que, si nécessaire, il serait aisé de programmer cet algorithme dans un quelconque langage de programmation.

En outre, si la thèse de Church-Turing venait à être invalidée, l'édifice conceptuel construit autour de la calculabilité resterait, et continuerait vraisemblablement à être étudié. Il existe une hiérarchie de langages formels et de modèles de calcul, appelée *hiérarchie de Chomsky*. On y trouve par exemple les *langages rationnels*, correspondant aux langages reconnus par une classe de machines appelées *automates finis*. Bien que ces modèles soient pour la plupart moins expressifs que les machines de Turing, ils n'en sont pas moins un sujet très actif de recherche de nos jours. Si l'on trouve un jour de nouveaux paradigmes de calcul, la notion existante de fonction calculable n'en demeurera pas moins une classe de fonctions très robuste, et continuera à être étudiée au même titre que les langages rationnels ou tout autre niveau de la hiérarchie de Chomsky.

Certains phénomènes naturels sont étudiés dans l'espoir de résoudre des problèmes non calculables. Ces notions de calculabilité sont réunies sous le nom d'*hypercalcul* (nous en verrons une approche formelle dans la partie IV). Il n'existe pas à ce jour de perspective de réalisation de tels calculs. La découverte de nouveaux phénomènes de calcul dans la nature n'invaliderait cependant probablement pas la thèse de Church-Turing, car ils auraient peu de chances de satisfaire la définition de fonction effectivement calculable d'après Rosser [184], c'est-à-dire « une méthode dont chaque étape est précisément prédéterminée et qui produira de manière certaine une réponse en un nombre fini d'étapes. »
## 3. Étude détaillée des fonctions récursives

L'objectif de cette section est de convaincre le lecteur que les fonctions générales récursives coïncident avec les fonctions effectivement calculables telles que définies informellement dans les sections 3-2 et 3-1, comme étant « les fonctions que l'on peut programmer ». Les intérêts d'une telle étude sont multiples. Elle permet en premier lieu d'avoir une définition mathématique précise de ce qu'est une fonction calculable : il s'agit sans perte de généralité des fonctions générales récursives. Ensuite, l'étude que nous donnons fournira du même coup une preuve mathématique de l'existence d'une machine universelle telle que définie dans le théorème 3-3.1, concept utilisé tout au long de cet ouvrage. Pour finir, notre étude isolera la notion de fonction primitive récursive comme une sous-classe stricte des fonctions calculables; outre une certaine importance épistémologique (voir le théorème 3.22), cette sous-classe présente un indéniable intérêt en logique mathématique. Nous en verrons un exemple d'utilisation dans l'étude des mathématiques à rebours, à la section 23-7.

### 3.1. Machines à registres et diagrammes de programmation

Pour nous convaincre que les fonctions générales récursives coïncident avec les fonctions calculables, nous partons d'un modèle de calcul proche des langages de programmation modernes : les programmes structurés, exécutés par des machines à registres. Nos développements reprennent ici dans les grandes lignes le cours de calculabilité d'A. Durand et P. Rozière [51] du Master de logique mathématique de l'université Paris Diderot.

**Les machines à registres.** La littérature scientifique en a décliné plusieurs versions, sous le nom de « random access machine » (Melzak [155], Lambek [135], Shepherdson and Sturgis [197], Peter [174], Elgot et Robinson [55]). Il s'agit de machines dites à « random access memory » ou RAM, nom générique aujourd'hui pour désigner la mémoire vive des ordinateurs. Le terme « random access » (accès aléatoire) doit être compris par opposition à « sequential access » (accès séquentiel), et fait référence au fait que l'on peut accéder à chaque case mémoire directement à partir de son adresse, contrairement par exemple au modèle des machines de Turing, pour lesquelles une tête de lecture doit se déplacer case après case dans la mémoire pour arriver à l'endroit désiré.

La mémoire d'une machine à registre sera toutefois plus élémentaire qu'une mémoire RAM moderne : il s'agit simplement d'un nombre fini de registres $R_0, R_1, ..., R_k$ pour $k \in \mathbb{N}$ arbitraire. Chaque registre peut contenir un entier quelconque positif ou nul. Notons que les entiers peuvent être arbitrairement grands, et donc que chaque registre représente un espace mémoire « non borné ».
<figure><img src="image_44.png" /><figcaption>FIGURE 3.1 – Le modèle des machines à registres</figcaption></figure>

**Les programmes structurés.** Une machine à registre va exécuter un programme qui consiste en une liste finie d'instructions permettant de faire des calculs. Il existe de nombreuses variantes possibles quant au jeu d'instruction que l'on s'autorise. Nous en présentons un, volontairement proche de celui d'un langage de programmation impérative moderne.

**Définition 3.2.** Un programme structuré peut contenir les instructions suivantes.

1. ▷ Incrémentation d'un registre : « $R_i := R_i + 1$ ».

▷ Décrémentation d'un registre : « $R_i := R_i - 1$ ».

▷ Assignement d'un registre : « $R_i := x$ », $x \in \mathbb{N}$, ou « $R_i := R_j$ ».

Ces instructions respectivement incrémentent la valeur de $R_i$ de 1, la décrémentent de 1 (sauf si la valeur est de 0, auquel cas rien ne se passe), mettent la valeur de $R_i$ à x ou la mettent à celle de $R_j$).

2. L'instruction conditionnelle : « if $R_i = 0$ then $S$ else $S'$ », où les suites finies $S = (S_0, ..., S_n)$ et $S' = (S'_0, ..., S'_m)$ sont des suites d'instructions structurées.

Chaque instruction de $S$ est exécutée séquentiellement si $R_i$ est égal à 0. Sinon, chaque instruction de $S'$ est exécutée séquentiellement.

3. L'instruction de boucle for : « for $i = 1$ to $R_i$ do $S$ », où la suite finie $S = (S_0, ..., S_n)$ est une suite d'instructions structurées.

Soit $N$ le nombre présent dans le registre $R_i$ au moment où le programme commence cette instruction. Chaque instruction de $S$ est exécutée séquentiellement, le tout $N$ fois. Notez que si la valeur de $R_i$ change pendant l'exécution des instructions de $S$, cela ne change pas le nombre de fois que la boucle s'effectue.
4. L'instruction de boucle while : « while $R_i \neq 0$ do $S$ » où la suite finie $S = (S_0, \dots, S_n)$ est une suite d'instructions structurées.

Chaque instruction de S est exécutée séquentiellement tant que le registre $R_i$ est différent de 0.

L'exécution d'un programme structuré s'arrête une fois la dernière instruction exécutée. ◇

Notons qu'un programme structuré n'a qu'un nombre fini d'instructions et ne peut donc utiliser qu'un nombre fini de registres.

### Boucle for vs Boucle while

Le lecteur remarquera peut-être que l'instruction de boucle **for** est redondante dans la mesure où elle peut toujours être remplacée par une instruction de boucle **while**. Nous verrons que l'inverse n'est pas vrai. En particulier, le nombre de fois qu'une boucle **for** s'exécute est nécessairement fini, ce qui n'est pas le cas des boucles **while**, au sein desquelles un calcul peut se retrouver bloqué dans ce que l'on appelle classiquement en programmation *une boucle infinie*. Nous verrons que l'instruction de boucle **while** est indispensable, et que certaines fonctions calculables (et totales) ne peuvent se programmer en n'utilisant que des boucles **for**.

**Les diagrammes de programmation.** La programmation structurée trouve sa genèse dans les travaux de Goldstine et von Neumann [75], qui manifestent, dès 1946, un souci non plus de capturer mathématiquement la notion de calcul, mais celui de développer un système de programmation. Ils développent une manière de présenter des algorithmes à base de diagrammes de programmation.

Nous en donnons ici la présentation simplifiée que l'on trouve dans l'ouvrage de référence de Piergiorgio Odifreddi [169].

**Définition 3.3.** Un diagramme de programmation est obtenu en connectant entre elles des briques de base des deux types suivants.

▷ Des instructions d'assignements :

$R_i := R_i + 1$

$R_i := R_i - 1$

$R_i := 0$
<figure><img src="image_45.png" /><figcaption>FIGURE 3.4 – *Un diagramme de programmation pour la fonction d'addition de deux nombres. On suppose que le calcul démarre avec $R_0 = 0$, $R_1 = n_1$ et $R_2 = n_2$. À la fin de l'exécution, on aura $R_0$ égal à $n_1 + n_2$.*</figcaption></figure>

▷ Une instruction conditionnelle :

<figure><img src="image_46.png" /></figure>

Un diagramme de programmation possède une entrée et une ou plusieurs sorties. Le calcul s'effectue de manière linéaire en exécutant chaque bloc depuis l'entrée vers d'une de ses sorties. ◇

À titre d'exemple, la figure 3.4 est un diagramme de programmation correspondant à la fonction d'addition.

Les diagrammes de programmation peuvent être programmés sur des machines à registre avec un jeu d'instructions comportant des sauts conditionnels et inconditionnels (ces derniers étant simplement appelés « sauts »), c'est-à-dire des instructions de type *goto* en anglais, qui permettent de déterminer quelle est la prochaine instruction du programme qui sera exécutée. Il s'agit encore aujourd'hui du mécanisme à l'œuvre dans les différents
langages assembleurs des micro-processeurs.

**Définition 3.5.** Un programme *goto* est une suite numérotée d'instructions $I_0, I_1, \dots, I_n$ où chaque instruction est de l'un des types suivants :

1. ▷ Incrémentation d'un registre : « $R_i := R_i + 1$ ».

▷ Décrémentation d'un registre : « $R_i := R_i - 1$ ».

▷ Assignement d'un registre à 0 : « $R_i := 0$ ».

2. L'instruction de saut conditionnel : « if $R_i = 0$ goto $n_1$ else goto $n_2$ ».

Si $R_i$ est égal à 0, l'instruction numéro $n_1$ est la prochaine à être exécutée, sinon c'est l'instruction numéro $n_2$.

3. Le saut inconditionnel : « goto *m* ».

L'instruction numéro *m* est la prochaine à être exécutée.

L'exécution d'un programme goto s'arrête quand il n'y a plus de prochaine instruction à exécuter (ce qui en particulier peut arriver après une instruction de type « goto *m* » dans un programme comportant moins de *m* instructions.) ◇

Remarque

Notons que le saut inconditionnel « goto *m* » peut être remplacé par un saut conditionnel « if $R_i = 0$ goto *m* else goto *m* ». Un programme *goto* peut donc être exprimé sans l'instruction 3.

Il est clair que les diagrammes de programmation sont interchangeables avec les programmes de type goto, et nous utiliserons un formalisme ou l'autre en fonction de la situation.

**Fonctions calculables.** Les notations $\Phi_e(x_1, \dots, x_n) \downarrow = y$ et $\Phi_e(x_1, \dots, x_n) \uparrow$ utilisées tout au long du livre s'appliquent naturellement aux programmes exécutés par des machines à registres, une fois les conventions de passage des paramètres et de récupération du résultat fixées.

**Définition 3.6.** Étant donné $P$ un programme de type structuré ou bien goto, on écrit $P(x_1, \dots, x_k)$ pour désigner l'exécution de $P$ avec les registres $R_1, \dots, R_k$ initialisés à $x_1, \dots, x_k$, et tous les autres registres initialisés à 0. On écrit $P(x_1, \dots, x_k) \downarrow = x$ pour signifier qu'une telle exécution s'arrête avec la valeur $x$ dans le registre $R_0$, et $P(x_1, \dots, x_k) \uparrow$ pour signifier que l'exécution ne s'arrête pas. ◇

On peut à présent utiliser notre modèle de calcul pour donner une définition mathématique précise de fonction calculable. Officialisons auparavant les notations $\dom f$ et $\Im f$, qui désignent respectivement le domaine et l'image d'une fonction $f$.
## Notation

Étant donné une fonction (éventuellement partielle) $f : A \to B$, on note $\text{dom } f$ le domaine de définition de $f$, et

$$ \text{Im } f = \{X \in B : \exists Y \in \text{dom } f \ f(Y) = X\} $$
son image.

**Définition 3.7.** Une fonction (éventuellement partielle) $f : \mathbb{N}^n \to \mathbb{N}$ est calculable par programme structuré (resp. par programme goto) s'il existe un programme structuré (resp. un programme goto) $P_f$, tel que

$$ P_f(x_1, \dots, x_n) \downarrow = f(x_1, \dots, x_n) $$

pour tous éléments $x_1, \dots, x_n \in \text{dom } f$ et tel que $P_f(x_1, \dots, x_n) \uparrow$ pour tous éléments $x_1, \dots, x_n \notin \text{dom } f$. ◇

**Justification du modèle de calcul.** Le programmeur ne sera peut-être pas convaincu par le fait que le modèle des machines à registres avec programmes structurés (ou goto) permet effectivement de programmer toutes les fonctions qu'il pourrait écrire dans son langage favori.

Un aspect en particulier peut susciter l'inquiétude : un langage de programmation moderne permet l'utilisation de tableaux, et même de tableaux dynamiques, dont la taille peut augmenter au fur et à mesure des besoins. Nous verrons par exemple dans la définition 3.24 que la fonction dite d'Ackermann se calcule naturellement à l'aide d'une structure de pile, et qu'il n'est pas du tout clair que l'on puisse s'en passer. Fort heureusement, nous montrerons avec la proposition 3.26 qu'il est parfaitement possible de simuler les manipulations de tableaux dynamiques au sein des machines à registres, en codant ces derniers dans les registres, qui, rappelons-le peuvent contenir des entiers arbitrairement grands.

**Simulation des programmes structurés par les programmes goto.** Nous commençons par montrer que les programmes goto, malgré leur simplicité, sont suffisants pour calculer tout ce que peuvent calculer les programmes structurés.

**Proposition 3.8.** Soit $n \in \mathbb{N}^*$, et soit $f : \mathbb{N}^n \to \mathbb{N}$ une fonction calculable par un programme structuré. Alors, la fonction $f$ est calculable par un programme goto. ★

**PREUVE.** Il suffit de montrer que chaque instruction d'un programme structuré peut être remplacée par un diagramme de programmation.
L'instruction d'affectation suivante $\ll R_i := n \gg$ peut être remplacée par le diagramme de programmation ci-contre, où l'instruction $\ll R_i := R_i + 1 \gg$ est répétée $n$ fois.

<figure><img src="image_47.png" /></figure>

L'instruction d'affectation suivante $\ll R_i := R_j \gg$ peut être remplacée par le diagramme de programmation ci-contre, où $R_k$ est un nouveau registre que l'on suppose à 0, et différent de $R_i$ et $R_j$.

<figure><img src="image_48.png" /></figure>
L'instruction de boucle « for $i = 1$ to $R_i$ do $S$ » peut être remplacée par le diagramme de programmation ci-contre, où la boîte « PROGRAMME $S$ » est le diagramme de programmation correspondant à la liste d'instructions $S$, et où $R_k$ est un nouveau registre différent de $R_i$ et non utilisé dans le diagramme de programmation « PROGRAMME $S$ ».

<figure><img src="image_49.png" /></figure>

L'instruction de boucle « while $R_i \neq 0$ do $S$ » peut être remplacée par le diagramme de programmation ci-contre, où la boîte « PROGRAMME $S$ » est le diagramme de programmation correspondant à la liste d'instructions $S$.

<figure><img src="image_50.png" /></figure>

L'instruction d'affectation « if $R_i = 0$ then $S$ else $Q$ » peut être remplacée par le diagramme de programmation ci-contre, où les deux boîtes « Programme $S$ » et « Programme $Q$ » sont les diagrammes de programmation correspondant aux suites d'instructions $S$ et $Q$.

<figure><img src="image_51.png" /></figure>

<figure><img src="image_52.png" /></figure>
## 3.2. Les fonctions récursives sont calculables.

Les programmes structurés suivent les concepts de la programmation dite *impérative* : des instructions modifiant l'état de la machine sont exécutées les une après les autres. Les fonctions générales récursives suivent quant à elles le paradigme de la programmation dite *fonctionnelle* : un programme est une composition de fonctions mathématiques et un calcul l'évaluation de ces fonctions. Un avantage de la programmation fonctionnelle souvent mis en avant est l'absence d'effets de bord : le résultat d'une fonction dépend de ses paramètres et uniquement de ses paramètres (l'état de la machine sur laquelle la fonction s'exécute n'a pas d'incidence). On peut par exemple brancher la sortie d'une fonction sur l'entrée d'une autre sans s'attendre à de mauvaises surprises. À titre de comparaison, la combinaison de programmes structurés $P_f, P_g$ calculant des fonctions $f, g : \mathbb{N} \to \mathbb{N}$ en un programme calculant la fonction $x \mapsto f(g(x))$ demande un peu de travail, afin justement d'éviter les effets de bord.

**Définition 3.9.** Un programme de type structuré ou bien de type goto est propre s'il termine son calcul avec tous ses registres — à l'exception de $R_0$ — dans le même état qu'au début du calcul. ◇

**Exercice 3.10.** Montrer que pour tout programme structuré $M$, il existe un programme structuré $N$ propre tel que $M(\bar{x}) \downarrow = y \leftrightarrow N(\bar{x}) \downarrow = y$. ◇

**Théorème 3.11 (Wang [229], Peter [175], Ershov [57])**

Toute fonction générale récursive (éventuellement partielle) est calculable par un programme structuré. Toute fonction primitive récursive est calculable par un programme structuré sans boucle while.

**PREUVE.** On laisse au lecteur le soin de montrer que les fonctions constantes, les fonctions de projection et la fonction successeur sont toutes calculables par un programme structuré. Il reste à traiter les cas suivants.

*Schéma de composition.* Soit

$$f(x_1, \dots, x_m) = g(h_1(x_1, \dots, x_m), \dots, h_k(x_1, \dots, x_m)),$$

pour des fonctions $g : \mathbb{N}^k \to \mathbb{N}$ et $h_1, \dots, h_k : \mathbb{N}^m \to \mathbb{N}$ calculables par des programmes structurés $G, H_1, \dots, H_m$. Par l'exercice 3.10, on peut supposer que $G, H_1, \dots, H_m$ sont propres. Supposons que chacun de ces programmes utilise au plus les registres $R_0, \dots, R_z$ pour $z > m$. Le programme $F$ pour calculer $f$ est donné par la suite d'instructions suivantes.
Programme F

⟨Instructions de $H_1$⟩

$R_{z+1} := R_0$

$R_0 := 0$

⟨Instructions de $H_2$⟩

$R_{z+2} := R_0$

$R_0 := 0$

...

⟨Instructions de $H_k$⟩

$R_{z+k} := R_0$

$R_0 := 0$

$R_1 := R_{z+1}$

...

$R_k := R_{z+k}$

⟨Instructions de $G$⟩

Notons que si $G, H_1, \dots, H_m$ n'utilisent pas de boucle while, alors le programme pour calculer $F$ n'en utilise pas non plus.

Schéma de récursion primitive. Soient

$$ 
\begin{aligned}
f(x_1, \dots, x_n, 0) &= g(x_1, \dots, x_n) \\
f(x_1, \dots, x_n, y + 1) &= h(x_1, \dots, x_n, y, f(x_1, \dots, x_n, y))
\end{aligned}
 $$

pour $g$ et $h$ calculables respectivement par des programmes structurés propres $G$ et $H$, utilisant au plus les registres $R_0, \dots, R_z$ pour $z > n + 2$. Le programme $F$ suivant permet de calculer $f$.

Programme F

$R_{z+1} := R_{n+1}$

⟨Instructions de $G$⟩

$R_{n+1} := 0$

$R_{n+2} := R_0$

for $i = 1$ to $R_{z+1}$ do

$R_0 := 0$

⟨Instructions de $H$⟩

$R_{n+1} := R_{n+1} + 1$

$R_{n+2} := R_0$

end

Notons une fois de plus que si $G, H$ n'utilisent pas de boucles while, alors le programme pour calculer $F$ n'en utilise pas non plus.
*Schéma de minimisation.* Soit

$$f(x_1, \dots, x_n) = \min\{x \in \mathbb{N} : \forall i \le x (g(x_1, \dots, x_n, i) \downarrow \land g(x_1, \dots, x_n, x) = 0)\},$$

pour $g$ calculable par un programme propre $G$, utilisant au plus les registres $R_0, \dots, R_z$ pour $z > n + 1$. Le programme suivant permet de calculer $f$.

Programme $F$

$$R_{z+1} := 1$$

$$R_{n+1} := 0$$

while $R_{z+1} \neq 0$ do

$$ \left| \begin{array}{l} R_0 := 0 \\ \langle \text{Instructions de G} \rangle \\ R_{z+1} := R_0 \\ R_{n+1} := R_{n+1} + 1 \end{array} \right. $$

end

$$R_{n+1} := R_{n+1} - 1$$

$$R_0 := R_{n+1}$$

Cela conclut la preuve.

■

### 3.3. Étude des fonctions primitives récursives

Nous passons à présent à la partie la plus difficile de ce chapitre. Afin de montrer que les fonctions calculables par programmes structurés sont des fonctions générales récursives, nous avons besoin d'un certain nombre d'outils, notamment sur les fonctions primitives récursives. Nous alternons différentes propositions et exercices permettant de voir qu'il s'agit d'une large classe de fonctions. Rappelons les notations de la définition 1.1 pour les fonctions primitives récursives de bases.

**Notation**

On note $p_i^n : \mathbb{N}^n \to \mathbb{N}$ la projection telle que $p_i^n(x_1, \dots, x_n) = x_i$. On note $c_i^n : \mathbb{N}^n \to \mathbb{N}$ la fonction constante telle que $c_i^n(x_1, \dots, x_n) = i$. On note $\text{succ} : \mathbb{N} \to \mathbb{N}$ la fonction successeur, définie par $\text{succ}(n) = n + 1$.

**Exercice 3.12.** (⋆) Montrer que l'addition, la multiplication et la fonction exponentielle sont primitives récursives. ◇

**Exercice 3.13.** (⋆) Montrer que les fonctions prédécesseur et soustraction sont primitives récursives (comme nos fonctions sont à valeur dans $\mathbb{N}$, on utilisera $0$ à la place du résultat si celui-ci est négatif). ◇
**Exercice 3.14.** (⋆) Montrer que la fonction sg : $\mathbb{N} \to \mathbb{N}$ qui à 0 associe 0 et qui à tous les autres entiers associe 1 est primitive récursive. Montrer que la fonction $\overline{sg} : \mathbb{N} \to \mathbb{N}$ qui à 0 associe 1 et qui à tous les autres entiers associe 0 est primitive récursive. ◇

**Définition 3.15.** Un prédicat $P \subseteq \mathbb{N}^n$ est primitif récursif (resp. général récursif) s'il existe une fonction primitive récursive (resp. générale récursive) $f : \mathbb{N}^n \to \{0,1\}$ telle que $(x_1, \dots, x_n) \in P \leftrightarrow f(x_1, \dots, x_n) = 1$ pour tous $x_1, \dots, x_n \in \mathbb{N}$. ◇

**Exemple 3.16.** Les prédicats de comparaison $\leq, <, \geq, >, =, \neq$ sont primitives récursifs via les fonctions suivantes :

$$a \leq b = \operatorname{sg}(\operatorname{succ}(b) - a)$$

$$a > b = b < a$$

$$a < b = \operatorname{sg}(b - a)$$

$$a = b = (a \leq b) \times (b \leq a)$$

$$a \geq b = b \leq a$$

$$a \neq b = \overline{\operatorname{sg}}(a = b).$$

Formellement, les projections sont utilisées si nécessaire, par exemple pour inverser l'ordre des paramètres dans la définition de $\geq$ à partir de celle de $\leq$.

**Proposition 3.17.** Les fonctions primitives récursives sont closes par définition par cas sur un prédicat primitif récursif : si $g$ et $h$ sont deux fonctions primitives récursives de $\mathbb{N}^p$ dans $\mathbb{N}$, et si $P$ est un prédicat primitif récursif sur $\mathbb{N}^p$, alors la fonction

$$\begin{aligned} f(x_1, \dots, x_p) &= g(x_1, \dots, x_p) & \text{si } P(x_1, \dots, x_p) \\ &= h(x_1, \dots, x_p) & \text{sinon} \end{aligned}$$

est primitive récursive.

<figure><img src="image_53.png" /></figure>

**PRÉUVE.** Comme $P$ est un prédicat primitif récursif, il existe une fonction $d : \mathbb{N}^n \to \mathbb{N}$ telle que

$$\begin{aligned} d(x_1, \dots, x_p) &= 1 & \text{si } P(x_1, \dots, x_p) \\ &= 0 & \text{sinon.} \end{aligned}$$

On définit donc :

$$f(x_1, \dots, x_p) = g(x_1, \dots, x_p) \times \operatorname{sg}(d(x_1, \dots, x_p)) \\ + h(x_1, \dots, x_p) \times \overline{\operatorname{sg}}(d(x_1, \dots, x_p)). \quad \blacksquare$$

La preuve de la proposition suivante fournit un exemple d'application de la définition par cas.
**Proposition 3.18.** La division entière est primitive récursive. ★

PREUVE. On utilise le schéma de récursion primitive couplé au schéma de définition par cas. On définit $div(a, b) = div(a, b, a)$, où :

$$ 
\begin{align*}
\operatorname{div}(a, b, 0) &= 0 \\
\operatorname{div}(a, b, n+1) &= \begin{cases}
\operatorname{succ}(n) & \text{si } \operatorname{succ}(n) \times b = a \\
\operatorname{div}(a, b, n) & \text{sinon}
\end{cases}
\end{align*}
$$

■

**Exercice 3.19.** (★) Montrer que les prédicats primitifs récursifs sont clos par conjonction, disjonction, négation, quantification existentielle bornée et quantification universelle bornée. ◇

**Exercice 3.20.** (★) Montrer que les fonctions primitives récursives sont closes par minimisation bornée : si $f : \mathbb{N}^{p+1} \to \mathbb{N}$ est primitive récursive, alors la fonction $g : \mathbb{N}^{p+1} \to \mathbb{N}$ qui à $x_1, \dots, x_p, n$ associe le plus petit $t \le n$ tel que $f(x_1, \dots, x_p, t) = 0$ (et 0 si un tel $t \le n$ n'existe pas) est primitive récursive. ◇

Souvenons-nous des bijections de Cantor comme définies dans la section 2-3. Le codage des paires $\langle x_1, x_2 \rangle$ est une notation pour l'application de la bijection $\alpha_2 : \mathbb{N}^2 \to \mathbb{N}$ définie par $\alpha_2(x, y) = y + \frac{(x+y+1)(x+y)}{2}$. Le codage $\langle x_1, \dots, x_k \rangle$ des $n$-uplets est une notation pour l'application des bijections $\alpha_k : \mathbb{N}^k \to \mathbb{N}$ définies inductivement par

$$ \alpha_{k+1}(x_1, x_2, \dots, x_{k+1}) = \alpha_2(x_1, \alpha_k(x_2, \dots, x_{k+1})). $$

**Proposition 3.21.** Pour tout $n$, la bijection

$$ x_1, \dots, x_n \mapsto \langle x_1, \dots, x_n \rangle $$

est primitive récursive. Pour tout $n$ et tout $i \le n$, la fonction

$$ \langle x_1, \dots, x_n \rangle \mapsto x_i $$

est primitive récursive.

★

PREUVE. L'addition, la multiplication et la division entière étant primitives récursives, la fonction $(x, y) \mapsto y + \frac{(x+y+1)(x+y)}{2}$ est elle aussi primitive récursive par le schéma de composition. Il en va donc de même pour tout $n$ pour les fonctions $x_1, \dots, x_n \mapsto \langle x_1, \dots, x_n \rangle$ qui sont définies inductivement par composition.

La fonction qui à $\langle x_1, x_2 \rangle$ associe $x_1$ est primitive récursive, fait qui s'établit en utilisant la minimisation bornée et la clôture des prédicats primitifs
récursifs par quantification existentielle bornée :

$$f(n) = \min\{x \le n : \exists y \le n \langle x, y \rangle = n\}.$$

On laisse au lecteur le soin de broder sur cette idée pour montrer que toutes les projections sont ainsi primitives récursives. ■

Nous avons à ce stade tous les éléments nécessaires pour montrer un premier théorème important. Nous avions vu avec le théorème 3.11 que les fonctions primitives récursives peuvent être programmées par des programmes struc- turés n'utilisant pas de boucle while. La réciproque est vraie.

### Théorème 3.22

Toute fonction calculable par un programme structuré sans boucles while est primitive récursive.

PREUVE. Pour $k \in \mathbb{N}$ donné, et pour un programme structuré $P$ sans boucles while et utilisant au plus les registres $R_0, \dots, R_k$, on définit la fonction $f_P : \mathbb{N} \to \mathbb{N}$ par $f_P(\langle x_0, \dots, x_k \rangle) = \langle v_0, \dots, v_k \rangle$ où $v_i$ est la valeur du registre $R_i$ en fin d'exécution du programme $P$, quand son exécution commence avec ses registres initialisés aux valeurs $x_0, \dots, x_k$.

Montrons que pour tout programme structuré $P$ sans boucles while, la fonction $f_P$ correspondante est primitive récursive. Il est clair que c'est le cas pour le programme vide. Soit $Q$ le programme dont l'unique instruction est $R_i := R_i + 1$. Alors, la fonction $f_Q$ est donnée par

$$f_Q(\langle x_0, \dots, x_k \rangle) = \langle x_0, \dots, x_i + 1, \dots, x_k \rangle.$$

On laisse au lecteur le soin de trouver la fonction primitive récursive correspondant aux instructions $R_i := R_i - 1$, $R_i := c$ pour $c \in \mathbb{N}$ et $R_i := R_j$.

Supposons à présent que la proposition est vraie pour des programmes $P, P'$, via des fonctions $f_P, f_{P'}$, et soit $Q$ le programme $\ll$ if $R_j = 0$ then $P$ else $P' \gg$. La fonction $f_Q$ est donc donnée par

$$ \begin{aligned} f_Q(\langle x_0, \dots, x_k \rangle) &= f_P(\langle x_0, \dots, x_k \rangle) \quad \text{si } x_j = 0 \\ &= f_{P'}(\langle x_0, \dots, x_k \rangle) \quad \text{sinon.} \end{aligned} $$

Supposons à présent que la proposition est vraie pour des programmes $P$, via des fonctions $f_P$, et soit $Q$ de forme suivante : $\ll$ for $i = 1$ to $R_j$ do $P \gg$. La fonction $f_Q$ est donnée par :

$$f_Q(\langle x_0, \dots, x_k \rangle) = g(\langle x_0, \dots, x_k \rangle, x_j)$$

où

$$g(\langle x_0, \dots, x_k \rangle, 0) = \langle x_0, \dots, x_k \rangle$$

$$g(\langle x_0, \dots, x_k \rangle, z + 1) = f_P(g(\langle x_0, \dots, x_k \rangle, z)).$$
Supposons à présent la proposition vraie pour des programmes $P, P'$, via des fonctions $f_P, f_{P'}$, et soit $Q$ composé des instructions de $P$ suivies de celles de $P'$. Alors, $f_Q = f_{P'}(f_P(x_0, \dots, x_k))$.

En utilisant chacun des cas décrits, on montre par récurrence que l'état des registres de tout programme structuré sans boucles while est une fonction primitive récursive. Il suffit alors de récupérer la valeur du registre $R_0$. ■

## 3.4. Étude de la fonction d'Ackermann

Il existe plusieurs manières de voir que les fonctions calculables ne sont pas toutes primitives récursives. La suivante est la plus naturelle pour l'expert en calculabilité pour lequel les diagonalisations effectives n'ont plus de secret.

**Exercice 3.23.** (★) Montrer qu'il existe un ensemble calculable $A \subseteq \mathbb{N}$ tel que $n \mapsto \Phi_e(n)$ est une fonction primitive récursive pour tout $e \in A$ et tel que toute fonction primitive récursive a un code dans $A$. En déduire qu'il existe une fonction totale calculable qui n'est pas primitive récursive. ◇

Un exemple couramment donné de fonction non primitive récursive calculable est la fonction d'Ackermann.

**Définition 3.24 (Fonction d'Ackermann [3]).** On définit les diverses fonctions $A_n : \mathbb{N} \to \mathbb{N}$ par récurrence sur $n \in \mathbb{N}$ de la manière suivante :

▷ $A_0$ est la fonction $x \mapsto 2^x$;

▷ $A_{n+1}(x)$ est l'application $x$ fois de la fonction $A_n$ sur 1 :

$$A_n(A_n(\dots(A_n(1)))).$$

Formellement,

$$A_0(x) = 2^x$$

$$A_{n+1}(0) = 1$$

$$A_{n+1}(x) = A_n(A_{n+1}(x-1)).$$

La fonction d'Ackermann est la fonction $n \mapsto A_n(n)$. ◇

<figure><img src="image_54.png" /></figure>

La fonction d'Ackermann a une croissance extrêmement rapide :

$$A(0) = 1, \quad A(1) = 2, \quad A(2) = 16,$$

et $A(3)$ est déjà égal à 65536 itérations de la fonction $x \mapsto 2^x$ (en commençant sur 0), c'est-à-dire :

$$A(3) = 2^{2^{(\dots(2^0))}}, \text{ où la puissance est itérée 65536 fois.}$$

Malgré sa très forte croissance, la fonction d'Ackermann est calculable : pour calculer $A_n(n)$, on peut utiliser une pile contenant soit des fonc-
tions $A_n$ (en pratique une représentation de ces fonctions), soit des entiers. Par exemple, si l'on empile $A_n$, $A_{n+1}$ et ensuite $k$, cela correspond au calcul $A_n(A_{n+1}(k))$. Ainsi le sommet de la pile est-il toujours un entier, et l'élément qui suit (s'il existe) est toujours une fonction. Aussi, pour calculer $A_n(n)$, on procède comme suit.

1. On empile $A_n$, puis on empile $n$.

2. Tant que la pile contient plus d'un élément :

(a) on dépile l'entier $k$, puis on dépile la fonction $A_m$;

(b) si $m = 0$, on empile $2^k$;

(c) sinon, si $k = 0$ on empile 1;

(d) sinon, on empile $A_{m-1}$, puis $A_m$ et enfin $k-1$.

L'algorithme s'arrêtera quand la pile ne contiendra plus qu'un élément, le résultat du calcul de $A_n(n)$.

Nous laissons en exercice la preuve que la fonction d'Ackermann croît plus vite que toute fonction primitive récursive, et n'est donc pas elle-même primitive récursive.

**Exercice 3.25 (Cori et Lascar[42]). (*)**

(1) Montrer que $A_n(x) > x$ pour tous $n, x$.

(2) Montrer que la fonction $A_n$ est strictement croissante pour tout $n$.

(3) Montrer que la fonction $n \mapsto A_n(x)$ est croissante pour tout $x$.

(4) Montrer que $A_{n+1}(x+y) \ge A_n^{(y)}(x)$ pour tous $n, x, y$, où $f^{(m)}(x)$ dénote $f(f(...f(x)...))$ où l'application de $f$ est itérée $m$ fois.

(5) Montrer que pour tout $n$, on a $A_{n+2}(x) > A_n^{(x+1)}(x+1)$ pour presque tout $x$.

(6) Soit $n > 0$, et soit $f : \mathbb{N}^n \to \mathbb{N}$. On note $P(f)$ le prédicat
$$ \exists k \forall \infty x_1, \dots, x_n A_k(\max(x_1, \dots, x_n)) > f(x_1, \dots, x_n). $$

Montrer que $P(f)$ est vrai pour toute fonction primitive récursive $f$.

En déduire que la fonction d'Ackermann n'est pas primitive récursive. ◇

Les boucles de type `while` sont donc indispensables pour calculer certaines fonctions, et avec elles, surviennent la possibilité d'écrire des programmes qui ne s'arrêtent pas.

### 3.5. Les fonctions calculables sont récursives

Nous nous apprêtons à présent à montrer que le schéma de minimisation des fonctions récursives permet de calculer n'importe quelle fonction programmable avec ou sans boucles `while`. Pour ce faire, nous commençons
par voir comment simuler des structures de listes de taille arbitraire par
des entiers. Cela semble en effet pour le moment être un manque de notre
modèle de machine à registres et de programmes structurés. Nous avons
par exemple besoin d'une pile pour calculer la fonction d'Ackermann via
l'algorithme mentionné ci-dessus.

**Proposition 3.26.** Il existe une bijection [ ] : $\bigcup_{n \in \mathbb{N}} \mathbb{N}^n \to \mathbb{N}$ (où l'on note $[x_1, \dots, x_n]$ l'entier correspondant au $n$-uplet $(x_1, \dots, x_n)$), telle que les opérations suivantes sont primitives récursives.

1. La fonction $\mathcal{O}(\cdot)$ d'ajout en tête de liste définie par

$$a :: [x_1, \dots, x_n] = [a, x_1, \dots, x_n].$$

2. Les fonctions hd et tl de tête et queue de liste, définies par

$$hd([ ]) = 0 \qquad tl([ ]) = 0 \\ hd(x :: l) = x \qquad tl(x :: l) = l.$$

3. La fonction $|\cdot|$ de taille d'une liste définie par $|[x_1, \dots, x_n]| = n$.

4. Les fonctions get, set telles que

$$\begin{align*} \text{get}([x_0, \dots, x_{n-1}], i) &= x_i \quad \text{si } i < n \\ \text{get}([x_0, \dots, x_{n-1}], i) &= 0 \quad \text{sinon} \end{align*}$$

et

$$\begin{align*} \text{set}([x_0, \dots, x_{n-1}], a, i) &= [x_0, \dots, x_{i-1}, a, x_{i+1}, \dots, x_{n-1}] \quad \text{si } i < n \\ \text{set}([x_0, \dots, x_{n-1}], a, i) &= [x_0, \dots, x_{n-1}] \quad \text{sinon.} \end{align*}$$

*

**PREUVE.** La bijection $[ ] : \bigcup_{n \in \mathbb{N}} \mathbb{N}^n$ est définie par récurrence en commençant par la liste vide $[ ] = 0$ et en appliquant l'opération d'ajout en tête de liste définie par $a :: l = 1 + \alpha_2(a, l)$, où $\alpha_2 : \mathbb{N}^2 \to \mathbb{N}$ est la bijection de l'exercice 2-3.7. Il est clair que la fonction d'ajout en tête est primitive récursive, de même que les fonctions hd et tl obtenues grâce aux fonctions inverses de $(x_1, x_2) \mapsto (x_1, x_2)$. Montrons que le codage des listes obtenu ainsi est bien une bijection.

Montrons par récurrence que deux listes de tailles différentes ne peuvent pas être codées par le même élément. Le code de la liste vide est $0$ et le code d'une liste non vide est de la forme $1 + \alpha_2(a, l) \neq 0$. Donc, le code de la liste vide est toujours différent du code d'une liste non vide.

Supposons à présent que toutes les listes de taille $n$ ont un code différent de celui des listes de taille $m > n$. Montrons que toutes les listes de taille $n+1$ ont un code différent de celui des listes de taille $m > n+1$. Les codes des listes de taille $n+1$ sont de la forme $1 + \alpha_2(a, l_1)$ pour $l_1$ le code d'une liste de taille $n$. Les codes des listes de taille $m > n+1$ sont de
la forme $1 + \alpha_2(b, l_2)$ pour $l_2$ le code d'une liste de taille $m > n$. Par hypothèse de récurrence, on a forcément $l_1 \neq l_2$ et comme $\alpha_2$ est injectif, on a forcément $1 + \alpha_2(a, l_1) \neq 1 + \alpha_2(b, l_2)$. Donc, les codes des listes de taille $n+1$ sont différents des codes des listes de taille $m > n + 1$. Par récurrence, on en déduit que les codes de listes de tailles différentes sont différents.

Montrons à présent par récurrence sur $k$ que si $(a_1, \dots, a_k) \neq (b_1, \dots, b_k)$, on a alors $[a_1, \dots, a_k] \neq [b_1, \dots, b_k]$.

Pour $k=1$, on a $a_1 \neq b_1$ implique $1 + \alpha_2(a_1, 0) \neq 1 + \alpha_2(b_1, 0)$, car $\alpha_2$ est injective. On a donc $[a_1] \neq [b_1]$. Supposons que ce soit le cas pour $k$, et montrons que c'est le cas pour $k+1$. Supposons $(a_1, \dots, a_{k+1}) \neq (b_1, \dots, b_{k+1})$. Si $a_1 \neq b_1$, on a alors $1 + \alpha_2(a_1, [a_2, \dots, a_{k+1}]) \neq 1 + \alpha_2(b_1, [b_2, \dots, b_{k+1}])$, car $\alpha_2$ est injective. Si $(a_2, \dots, a_{k+1}) \neq (b_2, \dots, b_{k+1})$, alors par hypothèse de récurrence on a $[a_2, \dots, a_{k+1}] \neq [b_2, \dots, b_{k+1}]$, et donc

$$1 + \alpha_2(a_1, [a_2, \dots, a_{k+1}]) \neq 1 + \alpha_2(b_1, [b_2, \dots, b_{k+1}]),$$

car $\alpha_2$ est injective. Par récurrence, pour tout $k$ on a donc

$$(a_1, \dots, a_k) \neq (b_1, \dots, b_k) \text{ implique } [a_1, \dots, a_k] \neq [b_1, \dots, b_k].$$

La fonction $[]$ est ainsi injective.

Montrons à présent que $[]$ est surjective. Supposons par l'absurde que ce n'est pas le cas. Dans ce cas, il existe un plus petit $n$ tel que $n$ n'est le code d'aucune liste. Notons que l'on a forcément $n > 0$, car $0$ est le code de la liste vide. Aussi, comme $\alpha_2$ est surjective, il existe $(a,b)$ tel que $\alpha_2(a, b) = n-1$, et donc tel que $1 + \alpha_2(a, b) = n$. On a par ailleurs nécessairement $b \le n-1 < n$. Aussi, par minimalité de $n$, il doit exister une liste $l$ dont $b$ est le code. Donc, $n$ est le code de la liste $a :: l$, ce qui contredit notre hypothèse sur $n$.

Afin de montrer que les fonctions $|\cdot|$ et $\text{set}$ sont primitives récursives, on donne une définition primitive récursive de la fonction $\text{tl}(l, n)$ qui ampute une liste $l$ de ses $n$ premiers éléments :

$$\begin{aligned} \text{tl}(l, 0) &= l \\ \text{tl}(l, n + 1) &= \text{tl}(\text{tl}(l, n)). \end{aligned}$$

La taille est alors définie via le schéma de minimisation bornée par l'entier $|l| = \min\{n \le l : \text{tl}(l, n) = []\}$. La fonction get a la définition primitive récursive suivante : $\text{get}(l, n) = \text{hd}(\text{tl}(l, n))$. La fonction set est quant à elle définie en deux fois, en ajoutant d'abord un paramètre supplémentaire :

$$\begin{aligned} \text{set}(l, a, i) &= \text{set}(l, a, i, i) \\ \text{set}(l, a, n, 0) &= a :: \text{tl}(l, \text{succ}(n)) \\ \text{set}(l, a, n, i + 1) &= \text{get}(l, n - \text{succ}(i)) :: \text{set}(l, a, n, i) \end{aligned}$$

■
Nous avons à présent tous les éléments nécessaires pour montrer que les fonctions calculables par des programmes structurés sont récursives.

**Théorème 3.27**

Toute fonction calculable par un programme goto (et donc aussi par un programme structuré) est une fonction générale récursive.

Le reste de la section est consacré à la preuve, pour laquelle nous avons besoin de fixer un codage des programmes goto et des machines à registre.

**Codage des programmes goto.** On code les instructions des programmes goto comme suit :

▷ « $R_i = R_i + 1$ » est codé par $\langle 0, i \rangle$

▷ « $R_i = R_i - 1$ » est codé par $\langle 1, i \rangle$

▷ « $R_i = 0$ » est codé par $\langle 2, i \rangle$

▷ « if $R_i = 0$ goto $n_1$ else $n_2$ » est codé par $\langle 3, \langle i, \langle n_1, n_2 \rangle \rangle \rangle$

▷ « goto $n$ » est codé par $\langle 4, n \rangle$.

Pour des raisons d'uniformité, il sera utile d'avoir une borne sur l'indice maximal des registres utilisés. Le code d'un programme goto est simplement donné par le code : $\langle k, [I_1, \dots, I_n] \rangle$, où $k$ est tel que le programme utilise au plus les registres $R_0, \dots, R_k$ et où $I_e$ est le code de la $e$-ième instruction pour $1 \le e \le n$.

**Codage des machines à registres.** On fixe à présent un codage de l'état d'une machine à $k$ registres. Cet état est donné par la valeur des registres ainsi que par l'indice de la prochaine instruction à exécuter. Pour un nombre de registres $k$ donné, ce code est $\langle m, [R_0, \dots, R_k] \rangle$, où $m$ est le numéro d'instruction et $R_i$ est la valeur du registre numéro $i$ pour $0 \le i \le k$.

**Fonction d'initialisation.** Fixons maintenant une fonction d'initialisation init, qui étant donné un code $e = \langle k, I \rangle$ d'un programme (où $I$ est une liste d'instructions), des valeurs $x_1, \dots, x_n$ (pour $n \le k$), donne le code représentant l'état de la machine à $k$ registres, au début du calcul.

$$ \text{init}(\langle k, I \rangle, x_1, \dots, x_n) = \langle 0, 0 \::\:: x_1 \::\:: \dots \::\:: x_n \::\:: \text{aux}(k-n) \rangle $$

avec aux définie par

$$ \text{aux}(0) = [] $$

$$ \text{aux}(k+1) = 0 \::\:: \text{aux}(k). $$

Il est clair que la fonction init est primitive récursive.
**Fonctions de transition 1.** On définit une fonction de transition $tr_1$, qui étant donné le code $e = \langle k, I \rangle$ d'un programme et le code $p = \langle m, R \rangle$ de l'état d'une machine, renvoie le numéro de la prochaine instruction à exécuter à l'étape de calcul suivante. On va utiliser pour cela une fonction cur : $N \to N$ qui, étant donné le code $e = \langle k, I \rangle$ d'un programme et le code $p = \langle m, R \rangle$ de l'état d'une machine, permet d'obtenir l'instruction courante de la machine :

$$ \mathrm{cur}(\langle k, I \rangle, \langle m, R \rangle) = \mathrm{get}(I, m). $$

En utilisant la fonction cur, les fonctions $\pi_1, \pi_2$ telles que $n = \langle \pi_1(n), \pi_2(n) \rangle$ on définit $tr_1(e, p)$ comme étant :

<table><tr><td>$\pi_1(p) + 1$</td><td>si</td><td>$\pi_1(\mathrm{cur}(e, p)) \le 2$</td></tr><tr><td>$\pi_1(\pi_2(\pi_2(\mathrm{cur}(e, p))))$</td><td>si</td><td>$\pi_1(\mathrm{cur}(e, p)) = 3$ et<br>$\mathrm{get}(\pi_2(p), \pi_1(\pi_2(\mathrm{cur}(e, p)))) = 0$</td></tr><tr><td>$\pi_2(\pi_2(\pi_2(\mathrm{cur}(e, p))))$</td><td>si</td><td>$\pi_1(\mathrm{cur}(e, p)) = 3$ et<br>$\mathrm{get}(\pi_2(p), \pi_1(\pi_2(\mathrm{cur}(e, p)))) \ne 0$</td></tr><tr><td>$\pi_2(\mathrm{cur}(e, p))$</td><td>si</td><td>$\pi_1(\mathrm{cur}(e, p)) = 4$.</td></tr></table>

Il est clair que $tr_1$ est primitive récursive.

**Fonctions de transition 2.** On définit à présent une fonction de transition $tr_2$ qui étant donné le code $e$ d'un programme et le code $p$ de l'état d'une machine, permet d'obtenir l'état des registres de la machine à l'étape de calcul suivante.

Pour cela l'on utilisera deux fonctions primitives récursives inc : $N \times N \to N$ et dec : $N \times N \to N$, telles que

$$ \begin{aligned} \mathrm{inc}([x_0, \dots, x_n], i) &= [x_0, \dots, x_i + 1, \dots, x_n] \\ \mathrm{dec}([x_0, \dots, x_n], i) &= [x_0, \dots, \max(0, x_i - 1), \dots, x_n] \end{aligned} $$

définies de la manière suivante.

$$ \begin{aligned} \mathrm{inc}(l, i) &= \mathrm{set}(l, \mathrm{succ}(\mathrm{get}(l, i)), i) \\ \mathrm{dec}(l, i) &= \mathrm{set}(l, \mathrm{pred}(\mathrm{get}(l, i)), i). \end{aligned} $$

On peut à présent définir $tr_2(e, p)$ comme étant :

<table><tr><td>$\mathrm{inc}(\pi_2(p), \pi_2(\mathrm{cur}(e, p)))$</td><td>si</td><td>$\pi_1(\mathrm{cur}(e, p)) = 0$</td></tr><tr><td>$\mathrm{dec}(\pi_2(p), \pi_2(\mathrm{cur}(e, p)))$</td><td>si</td><td>$\pi_1(\mathrm{cur}(e, p)) = 1$</td></tr><tr><td>$\mathrm{set}(\pi_2(p), 0, \mathrm{cur}(e, p))$</td><td>si</td><td>$\pi_1(\mathrm{cur}(e, p)) = 2$</td></tr><tr><td>$\pi_2(p)$</td><td>sinon.</td><td></td></tr></table>

Il est clair que $tr_2$ est primitive récursive.
**Fin de la preuve.** On définit à présent la fonction $\text{tr} : \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ de transition d'un état à un autre :

$$ \text{tr}(e, p) = \langle \text{tr}_1(e, p), \text{tr}_2(e, p) \rangle. $$

On définit ensuite la fonction primitive récursive

$$ \text{st} : \mathbb{N} \times \mathbb{N}^n \times \mathbb{N} \rightarrow \mathbb{N} $$

telle que $\text{st}(e, x_1, \dots, x_n, t)$ renvoie l'état de la machine qui exécute le programme $e$, avec les registres $R_1, \dots, R_n$, initialisés à $x_1, \dots, x_n$ respectivement, après $t$ étapes de calcul.

$$ \begin{aligned} \text{st}(e, x_1, \dots, x_n, 0) &= \text{init}(e, x_1, \dots, x_n) \\ \text{st}(e, x_1, \dots, x_n, t+1) &= \text{tr}(e, \text{st}(e, x_1, \dots, x_n, t)). \end{aligned} $$

On arrive enfin à l'étape pour laquelle on a besoin de schéma de minimisation, laissant la possibilité à une fonction de ne pas être définie sur certaines entrées. La fonction récursive time : $\mathbb{N} \times \mathbb{N}^n \rightarrow \mathbb{N}$ donne le plus petit temps de calcul nécessaire pour que la machine s'arrête, c'est-à-dire arrive à un numéro d'instruction plus grand que le nombre d'instructions du programme. La fonction sera définie si, et seulement si, la machine s'arrête pour le programme et les entrées correspondantes.

$$ \text{time}(e, x_1, \dots, x_n) = \min\{t \in \mathbb{N} : \pi_1(\text{st}(e, x_1, \dots, x_n, t)) \ge |\pi_2(e)|\}. $$

Finalement, voici la fonction récursive qui correspond au calcul de la machine de code $e$. On lance la fonction de transition pour le nombre d'étapes nécessaires avant que la machine ne s'arrête, et l'on renvoie la valeur du registre $R_0$ :

$$ f(x_1, \dots, x_n) = \text{hd}(\pi_2(\text{st}(e, x_1, \dots, x_n, \text{time}(e, x_1, \dots, x_n))))). $$

Cela conclut la démonstration.

## 3.6. Conséquences

D'après la preuve précédente, étant donné notre codage d'un programme par un entier $e$, son exécution pour $t$ étapes de calcul est une fonction primitive récursive et donc elle-même calculable par un programme strukturé. La recherche de ce plus petit temps de calcul peut se faire à l'aide d'une boucle while. Remarquons de plus que la preuve est uniforme : la même fonction primitive récursive s'adapte en fonction de tout code $e$ d'un programme.

Cela permet d'obtenir le théorème 3-3.1 de l'existence d'un programme universel, utilisé tout au long du livre, via la notation $\Phi_e$ pour le programme de code $e$.
**Théorème (3-3.1)**

Soit $n \in \mathbb{N}^*$. Il existe un code $e$ de programme informatique pour lequel $\Phi_e : \mathbb{N}^{n+1} \to \mathbb{N}$ est tel que, pour tous $x_1, \dots, x_n$, on a

$$ \triangleright \Phi_e(a, x_1, \dots, x_n) \uparrow \text{ssi } \Phi_a(x_1, \dots, x_n) \uparrow; $$

$$ \triangleright \Phi_e(a, x_1, \dots, x_n) \downarrow = y \text{ ssi } \Phi_a(x_1, \dots, x_n) \downarrow = y. $$

Le code $e$ du théorème ci-dessus est un code de la fonction

$$ (x_1, \dots, x_n) \mapsto \text{hd}(\pi_2(\text{st}(a, x_1, \dots, x_n, \text{time}(a, x_1, \dots, x_n)))) $$

donnée à la fin de la section précédente. La fonction

$$ (a, x_1, \dots, x_n) \mapsto \text{time}(a, x_1, \dots, x_n) $$

qui cherche le plus petit temps de calcul tel que le programme s'arrête est la seule qui utilise le schéma de minimisation. Notons que cela permet aussi de donner une définition mathématique précise aux notations

$$ \Phi_a(x_1, \dots, x_n)[t] \downarrow \text{ et } \Phi_a(x_1, \dots, x_n)[t] \uparrow. $$

Elles correspondent respectivement aux prédicats primitifs récursifs :

$$ \exists s \le t \pi_1(\text{st}(e, x_1, \dots, x_n, s)) \ge |\pi_2(e)| $$

$$ \text{et } \forall s \le t \pi_1(\text{st}(e, x_1, \dots, x_n, s)) < |\pi_2(e)|. $$
Chapitre 7

Immunité et croissance de
fonction

La calculabilité étudie la puissance calculatoire des ensembles d'entiers, modulo la réduction Turing. Dans ce chapitre, nous allons étudier en particulier deux grandes familles de propriétés calculatoires, à savoir la capacité à calculer des ensembles difficiles à décrire (ensemble immune, hyperimmune, effectivement immune), et la capacité à calculer des fonctions à croissance rapide (fonction hyperimmune, fonction dominante). Prenons quelques exemples.

**Exemple 1.** D'après l'exercice 3-7.10, tout ensemble infini c. e. contient un sous-ensemble infini calculable. Quelle puissance calculatoire faut-il pour obtenir un ensemble infini ne possédant pas de sous-ensemble infini calculable ? Nous étudierons cela dans la section 1 sous le concept d'ensemble immune.

**Exemple 2.** D'après le théorème 3-6.2 du point fixe de Kleene, pour toute fonction totale calculable $f : N \to N$, il existe un code $e$ tel que $\Phi_{f(e)} = \Phi_e$. Quelle est la puissance calculatoire d'une fonction sans point fixe ? Cette notion sera étudiée dans la section 2.

**Exemple 3.** Toute fonction calculable est trivialement dominée par une fonction calculable. Quelle puissance calculatoire faut-il pour calculer une fonction qui n'est dominée par aucune fonction calculable ? Ce sera le sujet de la section 4.
Il est difficile de se faire une intuition sur la puissance calculatoire *a priori*
de propriétés formulées de manière aussi diverses, et en particulier de les
comparer. Les propriétés tirées des trois exemples précédents admettent ce-
pendant des caractérisations qui rendront cette comparaison plus aisée. De
manière générale, l'existence de nombreuses caractérisations d'une même
puissance calculatoire avec des formulations très diverses est un gage de
robustesse de la notion. C'est en particulier le cas des propriétés étudiées
dans ce chapitre.

# 1. Ensembles immunes

La première famille de propriétés calculatoires sur les ensembles relève de
la capacité à approximer les éléments d'un ensemble. Un ensemble est cal-
culable s'il est possible de déterminer calculatoirement quels éléments lui
appartiennent ou non. Au niveau suivant, un ensemble est calculatoire-
ment énumérable s'il existe une procédure calculable pour lister tous les
éléments qui lui appartiennent, mais potentiellement dans le désordre, ce
qui fait qu'il n'est généralement pas possible d'être certain qu'un élément
n'appartient pas à l'ensemble. Nous allons maintenant étudier la puissance
calculatoire des ensembles infinis pour lesquels il n'est même pas possible
d'énumérer de manière calculable une quantité infinie de ses éléments.

**Définition 1.1.** Un ensemble infini $A \subseteq \mathbb{N}$ est *immune* s'il ne contient pas de sous-ensemble infini c. e. ◇

Comme nous l'avons vu, tout ensemble infini c. e. contient un sous-ensemble
infini calculable. Ainsi, de manière équivalente, un ensemble infini est im-
mune si, et seulement si, il ne contient pas de sous-ensemble infini cal-
culable. En particulier, tout ensemble immune $A$ est nécessairement non
calculable, car $A$ serait alors son propre sous-ensemble infini calculable
contredisant son immunité.

L'immunité est une notion d'ensemble, mais non pas de degré. En effet, si $A$
est un ensemble immune, l'ensemble $A \oplus \mathbb{N} = \{2n : n \in A\} \cup \{2n+1 : n \in \mathbb{N}\}$
est de même degré Turing que $A$, mais $A \oplus \mathbb{N}$ possède le sous-ensemble infini
calculable $\{2n+1 : n \in \mathbb{N}\}$. Inversement, tout degré Turing non calculable
contient un ensemble immune, comme le montre la proposition suivante.

**Proposition 1.2.** Tout ensemble non calculable est Turing équivalent à un ensemble immune. ★

PREUVE. Soit $A$ un ensemble non calculable, et soit $B = \{\sigma \in 2^{\mathbb{N}} : \sigma \prec A\}$
l'ensemble des segments initiaux de $A$. En particulier, $A \equiv_T B$. Il est par
ailleurs évident que tout sous-ensemble infini de $B$ permet de calculer des
segments initiaux arbitrairement grands de A, et donc A (ainsi d'ailleurs que B). Comme A n'est pas calculable, B ne possède pas de sous-ensemble infini calculable.

La notion d'ensemble immune possède deux renforcements orthogonaux, à savoir les ensembles effectivement immunes, et les ensembles hyperimmunes. Ces deux notions sont des propriétés calculatoires fondamentales en calculabilité, et nous verrons pour chacune d'entre elles plusieurs définitions équivalentes.

Rappelons que $W_e$ désigne l'ensemble c. e. de code $e : \{n : \Phi_e(n)\downarrow\}$.

**Définition 1.3.** Un ensemble infini $A \subseteq \mathbb{N}$ est *effectivement immune* s'il existe une fonction totale calculable $h : \mathbb{N} \to \mathbb{N}$ telle que pour tout code $e$, si $|W_e| \ge h(e)$ alors $W_e \not\subseteq A$. ◇

Intuitivement, un ensemble infini $A$ est effectivement immune si non seulement les ensembles infinis finissent par se tromper et énumérer un élément en-dehors de $A$, mais plus encore, cette erreur doit arriver après suffisamment peu d'éléments énumérés, en fonction du code de l'énumération. En particulier, tout ensemble effectivement immune est immune.

Nous verrons que le concept d'immunité effective est particulièrement digne d'intérêt du point de vue des degrés Turing. La puissance de calcul correspondant à la capacité de calculer un ensemble effectivement immune possède de nombreuses caractérisations qui seront étudiées dans la section 2.

Rappelons que le code canonique d'un ensemble fini $F$ est l'entier

$$n = \sum_{i \in F} 2^i.$$

Soit $D_0, D_1, \dots$ la collection des ensembles finis telle que $D_n$ est canoniquement codé par $n$, pour tout $n \in \mathbb{N}$.

**Définition 1.4.** Un tableau est une collection d'ensembles finis mutuellement disjoints $F_0, F_1, \dots$. Un tableau $F_0, F_1, \dots$ est c. e. s'il existe une fonction calculable $f : \mathbb{N} \to \mathbb{N}$ telle que pour tout $n$, $F_n = D_{f(n)}$. Un ensemble infini $A$ est *hyperimmune* si pour tout tableau c. e. $F_0, F_1, \dots$, il existe un entier $n$ tel que $F_n \cap A = \emptyset$. ◇

Cette définition plus complexe, formalise l'idée selon laquelle non seulement il n'est pas possible de lister calculatoirement une infinité d'éléments de $A$, mais plus encore il n'est même pas possible de lister une infinité de « blocs » finis d'éléments disjoints deux à deux, tels que chaque bloc contient au moins un élément de $A$.
Tout comme pour le concept d'immunité effective, c'est l'extension de l'hyperimmunité aux degrés Turing qui nous intéressera surtout dans la suite. La puissance de calcul correspondant à la capacité de calculer un ensemble hyperimmune possède de nombreuses caractérisations qui seront étudiées dans la section 4.

**Exercice 1.5.** Montrer que tout ensemble hyperimmune est immune. ◇

## 2. Fonctions DNC

Nous voyons à présent un exemple de degré Turing remarquable, dont l'étude remonte sans doute aux travaux d'Arslanov [8], qui étudia les degrés Turing permettant d'échapper au fameux théorème du point fixe de Kleene : étant donné une fonction calculable $f$, il existe $e$ tel que $\Phi_e = \Phi_{f(e)}$. Quelle puissance est nécessaire pour calculer une fonction $f$ pour laquelle ce n'est pas le cas ? Ces travaux ont été étendus par Jockusch, Lerman, Soare, et Solovay qui ont trouvé une caractérisation équivalente, qui constitue aujourd'hui la définition moderne de degré DNC.

**Définition 2.1.** Une fonction $f: \mathbb{N} \to \mathbb{N}$ est diagonalement non calculable (DNC) si $f(n) \neq \Phi_n(n)$ pour tout $n$. ◇

Insistons sur le fait que la fonction $f$ doit être totale dans la définition ci-dessus. Notons que si $\Phi_n(n) \uparrow$, il n'y a pas de restriction sur la valeur de $f(n)$. Un degré Turing est DNC s'il contient une fonction DNC.

**Exercice 2.2.** (*) Montrer que les degrés DNC sont clos par le haut, c'est-à-dire que si un ensemble calcule une fonction DNC, son degré est lui-même DNC. ◇

La notion de degré DNC présente de nombreuses applications dans les liens entre calculabilité et aléatoire algorithmique, tout comme en mathématiques à rebours. Nous verrons en particulier avec le corollaire 18-4.3 que les DNC sont nombreux du point de vue de la mesure, mais d'après la proposition 10-3.36 peu nombreux du point de vue des catégories de Baire (nous verrons en particulier l'existence de degrés non DNC et non calculables).

Observons tout d'abord qu'il n'existe pas de fonction DNC calculable, par un simple argument diagonal, ce qui est à l'origine de l'appellation « diagonalement non calculable ». La proposition suivante montre en revanche que l'on peut calculer une fonction DNC à l'aide du problème de l'arrêt.

**Proposition 2.3.** Le degré Turing $0'$ du problème de l'arrêt est un degré DNC. ★
**PREUVE.** Soit $f : \mathbb{N} \to \mathbb{N}$ la fonction $\emptyset'$-calculable, qui pour une entrée $e$, renvoie $1 - \Phi_e(e)$ si $e \in \emptyset'$, et 0 sinon. Cette fonction est DNC, car elle est totale, et lorsque $\Phi_e(e) \downarrow$, elle renvoie une valeur différente. Comme $\emptyset'$ calcule une fonction DNC, et que les degrés DNC sont clos par le haut, $\mathbf{0}'$ est DNC.

■

Nous verrons dans la section 3 que $\mathbf{0}'$ est le seul degré à la fois DNC et c. e. Il est clair que les degrés DNC sont en quantité indénombrable, car c'est également le cas des degrés au-dessus de $\mathbf{0}'$. Nous verrons avec la proposition 10-3.36 que les degrés non DNC sont eux aussi en quantité indénombrable.

Pour le moment, nous nous attachons à montrer que la notion de degré DNC est naturelle, dans le sens où elle possède de nombreuses caractérisations via des formulations très différentes (et nous en verrons d'autres encore dans la partie II sur l'aléatoire algorithmique).

**Définition 2.4.** Une fonction $f$ est libre de point fixe si $\Phi_n \neq \Phi_{f(n)}$ pour tout $n$. $\diamond$

**Théorème 2.5 (Jockusch, Lerman, Soare, et Solovay [101])**

Soit $X \in 2^\mathbb{N}$. Alors, les énoncés suivants sont équivalents.

(1) $X$ calcule une fonction diagonalement non calculable.

(2) $X$ calcule une fonction libre de point fixe.

**PREUVE.** Montrons (1) ⇒ (2). Soit $g \leq_T X$ telle que $g(n) \neq \Phi_n(n)$ pour tout $n$. Alors également, $f \leq_T X$ telle que $f(n)$ est un code pour une fonction calculable définie uniquement sur l'entrée $n$, et qui à $n$ associate $g(n)$. On a en particulier $\Phi_{f(n)}(n) \downarrow= g(n)$. Supposons qu'il existe $n$ tel que $\Phi_{f(n)}(m) = \Phi_n(m)$ pour tout $m$. Alors, $\Phi_n(n) \downarrow= \Phi_{f(n)}(n) \downarrow= g(n)$, ce qui contredit la définition de $g$. Donc, $f$ est une fonction libre de point fixe.

Montrons (2) ⇒ (1). Soit $f \leq_T X$, une fonction libre de point fixe. Alors, à partir de $X$, on calcule la fonction $g : \mathbb{N} \to \mathbb{N}$ qui sur l'entier $n$ crée le code $e_n$ de la fonction $m \mapsto \Phi_{\Phi_n(n)}(m)$, et renvoie $f(e_n)$. On utilise ici le même abus de notation que dans la preuve du point fixe de Kleene : si $\Phi_n(n) \uparrow$, alors $m \mapsto \Phi_{\Phi_n(n)}(m)$ désigne la fonction nulle part définie. Notons que $g$ est totale, car elle ne cherche pas à faire le calcul $\Phi_n(n)$. Supposons que $g$ ne soit pas DNC, c'est-à-dire qu'il existe $n$ tel que $g(n) = \Phi_n(n)$. Par définition de $g$, $f(e_n) = \Phi_n(n)$. En particulier, $\Phi_{f(e_n)} = \Phi_{\Phi_n(n)} = \Phi_{e_n}$. La fonction $f$ n'est donc pas libre de point fixe, ce qui contredit la définition de $f$. Donc, $g$ est une fonction DNC.

■
Voyons à présent l'équivalence entre degré DNC et degré effectivement immune. La troisième équivalence du théorème ci-dessous est plus technique, mais présente un grand intérêt et sera réutilisée par la suite. Il s'agit en fait d'un renforcement de la notion d'être DNC : considérons la suite $(A_n)_{n \in \mathbb{N}}$ d'ensembles c. e. définie par

$$A_n = \begin{cases} \{\Phi_n(n)\} & \text{si } \Phi_n(n) \downarrow \\ \emptyset & \text{sinon.} \end{cases}$$

Être de degré DNC est la capacité de calculer une fonction $f$ telle que pour tout $n$ entier, $f(n) \notin A_n$. La troisième équivalence étend ce résultat à l'énumération uniforme $(W_n)_{n \in \mathbb{N}}$ de tous les ensembles c. e. dont on sait borner le nombre d'éléments par un entier $n$.

### Théorème 2.6

Soit $X \in 2^{\mathbb{N}}$. Les énoncés suivants sont équivalents.

(1) X calcule une fonction diagonalement non calculable.

(2) X calcule un ensemble effectivement immune.

(3) X calcule une fonction $h: \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ telle que pour $e, n \in \mathbb{N}$,

$$|W_e| \le n \Rightarrow h(e, n) \notin W_e.$$

PREUVE. (1) ⇒ (3). Soit $f \le_T X$ une fonction DNC. Nous décrivons un processus uniforme en $e, n$ afin de calculer une valeur qui, sous l'hypothèse $|W_e| \le n$, n'est pas dans $W_e$. Pour chaque $0 \le i < n$, on calcule le code $u(e, i)$ de la fonction partielle calculable qui, pour toute entrée, cherche le $i$-ième élément $k$ dans l'énumération de $W_e$, s'il existe. Si un tel élément $k$ est trouvé, la fonction l'interprète comme le $n$-uplet $\langle k_0, \dots, k_{n-1} \rangle$, et renvoie $k_i$. Sinon, la fonction ne s'arrête pas. Notons que $\Phi_{u(e,i)}$ est soit une fonction constante, soit la fonction définie nulle part.

Montrons que la fonction X-calculable

$$h(e, n) = \langle f(u(e, 0)), \dots, f(u(e, n-1)) \rangle$$

satisfait (3). Raisonnons par l'absurde, et supposons que $h(e, n) \in W_e$ avec $|W_e| \le n$. Disons que $h(e, n)$ est le $i$-ième élément de $W_e$ dans l'ordre d'énumération. Alors, $\Phi_{u(e,i)}$ est la fonction constante qui trouve

$$k = h(e, n) = \langle f(u(e, 0)), \dots, f(u(e, n-1)) \rangle$$

et renvoie le $i$-ième élément du tuple, c'est-à-dire $f(u(e, i))$. En particulier, $\Phi_{u(e,i)}(u(e, i)) \downarrow= f(u(e, i))$, ce qui contredit l'hypothèse selon laquelle $f$ est DNC.

(3) ⇒ (2). Soit $h \le_T X$ une fonction satisfaisant (3). Soit $D_0, D_1, \dots$ une énumération effective de tous les ensembles finis tels que $n$ est le code
canonique de $D_n$. Soit $g: \mathbb{N} \to \mathbb{N}$ une fonction partielle calculable telle que si $|W_e| \ge e+1$; alors, $D_{g(e)} \subseteq W_e$ et $|D_{g(e)}| = e+1$. Nous allons définir une suite X-calculable infinie croissante d'entiers $x_0 < x_1 < \dots$ telle que pour tout $s$,

$$ \forall e \le s, \quad (|W_e| > e \Rightarrow D_{g(e)} \not\subseteq \{x_i : i \le s\}). \qquad (\star) $$

Il s'ensuit que $H = \{x_n : n \in \mathbb{N}\}$ est effectivement immune, car si $W_e \subseteq H$, alors $|W_e| \le e$. Le fait que l'on veuille $x_i < x_{i+1}$ est simplement pour que l'ensemble $H$ soit X-calculable. Supposons maintenant que l'on ait déjà défini $x_0 < \dots < x_s$ satisfaisant $(\star)$. Soit

$$ W_{v(s)} = \{y : y \le x_s\} \cup \bigcup_{e \le s+1 \text{ t.q. } g(e) \downarrow} D_{g(e)}. $$

Le but est d'utiliser notre fonction $h$ pour trouver un élément qui n'est pas dans $W_{v(s)}$. Soit $x_{s+1}$ un tel élément — nous verrons après comment l'obtenir. Notons d'abord que $x_{s+1}$ est bien strictement plus grand que $x_s$. Notons ensuite que pour tout entier $e \le s+1$ tel que $|W_e| > e$ et tel que $D_{g(e)} \not\subseteq \{x_i : i \le s\}$, alors également $D_{g(e)} \not\subseteq \{x_i : i \le s+1\}$. Notons finalement que pour $e \le s$ tel que $|W_e| > e$, on a bien $D_{g(e)} \not\subseteq \{x_i : i \le s\}$ par hypothèse, et pour $e = s+1$, si $|W_e| > e$, on a $D_{g(e)} \not\subseteq \{x_i : i \le s\}$ nécessairement, car $D_{g(e)}$ possède alors $s+2$ éléments. Dans tous les cas, on aura bien la condition $(\star)$ pour la suite $(x_i)_{i \le s+1}$. Montrons à présent comment trouver $x_{s+1}$ à l'aide de la fonction $h$. L'ensemble $W_{v(s)}$ admet au plus $x_s + 1$ plus $1+2+3+\dots+s+2$ éléments, ce qui donne par la somme des termes d'une suite arithmétique $t_s = x_s + 1 + (s+2)(s+3)/2$. On définit alors $x_{s+1} = h(v(s), t_s)$. Par définition de $h$, $x_{s+1} \notin W_{v(s)}$. En particulier, $x_{s+1} > x_s$, et $(\star)$ est satisfait pour $s+1$.

(2) $\Rightarrow$ (1) : Soit $H \le_T X$ un ensemble effectivement immune. On considère $g: \mathbb{N} \to \mathbb{N}$ une fonction totale calculable telle que si $W_e \subseteq H$, alors $|W_e| < g(e)$. Nous allons montrer que $X$ calcule une fonction libre de point fixe. Soit $f: \mathbb{N} \to \mathbb{N}$ la fonction X-calculable telle que $W_{f(e)}$ est l'ensemble des $g(e)$ premiers éléments de $H$. Notons que $f$ est X-calculable, mais que l'ensemble $W_{f(e)}$ est un ensemble c. e. qui, en particulier, n'a pas besoin de $X$ pour son énumération : on peut voir les éléments à énumérer comme étant « codés en dur » dans $f(e)$. Montrons que $f$ est libre de point fixe. Soit $e \in \mathbb{N}$; si $W_{f(e)} = W_e$, alors $W_e \subseteq H$, mais $|W_e| = |W_{f(e)}| = g(e)$, ce qui contredit le choix de $H$ et $g$. Comme $X$ calcule une fonction libre de point fixe, alors par le théorème 2.5, $X$ calcule une fonction DNC. ■

Nous nous arrêterons là pour le moment. Nous verrons d'autres caractérisations de la notion de degrés DNC en rapport avec l'aléatoire algorithmique. Mentionnons pour finir une hiérarchie qui découle naturellement de la définition des degrés DNC.
**Définition 2.7.** Soit $f : \mathbb{N} \to \mathbb{N}$ une fonction telle que

$$2 \le f(n) \le f(n+1).$$

Un ensemble $X \subseteq \mathbb{N}$ est de degré $\text{DNC}_f$ si $X$ calcule une fonction $g$ telle que $g(n) < f(n)$ et $g(n) \ne \Phi_n(n)$ pour tout $n$. ♢

Un examen de la définition indique que plus la fonction $f$ croît lentement, plus il semble difficile pour un ensemble d'être $\text{DNC}_f$. C'est effectivement le cas, comme on peut le voir avec le théorème suivant, dû à Ambos-Spies, Kjos-Hanssen, Lempp et Slaman [6].

**Théorème 2.8**

Soit $f$ une fonction telle que $2 \le f(n) \le f(n+1)$. Il existe une fonction $g$ telle que $2 \le g(n) \le g(n+1)$ et avec $f < g$ pour laquelle $\text{DNC}_f \subseteq \text{DNC}_g$, c'est-à-dire qu'il existe un ensemble $X$ qui calcule une fonction $\text{DNC}_g$ mais qui ne calcule aucune fonction $\text{DNC}_f$.

Comme annoncé plus tôt, nous verrons de nombreux exemples de degrés non DNC et non calculables, mais il est informatif de s'assurer de leur existence par une construction directe.

**Exercice 2.9. (**) Montrer par la méthode des extensions finies qu'il existe des degrés $\Delta_2^0$ non DNC et non calculables. ◇

# 3. Critère de complétude d'Arslanov

Le critère de complétude d'Arslanov traduit d'une certaine manière une incompatibilité entre les degrés c. e. et DNC.

**Degré c. e.**

Un degré Turing est dit calculatoirement énumérable ou c. e. s'il contient un ensemble calculatoirement énumérable. Nous verrons dans le chapitre 13 que $0'$ est loin d'être le seul degré c. e.

Il est aisé de calculer une fonction DNC à l'aide du problème de l'arrêt, comme le montre la proposition 2.3. En revanche, le critère de complétude d'Arslanov prouve que $0'$ est le seul degré à la fois c. e. et DNC.

**Théorème 3.1 (Critère de complétude d'Arslanov [8])**

Soit $A \in 2^\mathbb{N}$ un ensemble c. e. Alors, $A$ est Turing complet ssi $A$ calcule une fonction DNC.
PREUVE. Par la proposition 2.3, si l'ensemble A est Turing complet, il calcule une fonction DNC. Montrons la réciproque. Soit $(A_s)_{s \in \mathbb{N}}$ une approximation c. e. de A, c'est-à-dire avec $\lim_{s \to \infty} A_s = A$, et $A_s \subseteq A_{s+1}$. Notons que si $A_s \upharpoonright_n = A \upharpoonright_n$, alors aussi pour tout $t > s$ on aura $A_t \upharpoonright_n = A \upharpoonright_n$.

Soit $\Phi$ une fonctionnelle totale sur l'oracle A et telle que $\Phi(A, n) \neq \Phi_n(n)$ pour tout $n$. Uniformément en $n$, on calcule le code $a_n$ de la fonction partielle qui sur toute entrée $k$ agit comme suit : cherche le plus petit $t$ tel que $\emptyset'[t](n) = 1$, puis si cela arrive et si $\Phi(A_t \upharpoonright_m, a_n)[t]$ s'arrête pour un certain $m \le t$, alors renvoie la valeur de $\Phi(A_t \upharpoonright_m, a_n)[t]$, et sinon diverge. Notons que le code $a_n$ est défini en fonction de $a_n$ lui-même, ce qui est rendu possible grâce au théorème du point fixe.

Nous prétendons que pour tout $n$, si jamais $\emptyset'(n) = 1$, alors le plus petit $t$ tel que $\Phi(A_t \upharpoonright_m, a_n)[t] \downarrow$ pour $m \le t$ tel que $A_t \upharpoonright_m = A \upharpoonright_m$, est strictement plus grand que le plus petit $t$ tel que $\emptyset'[t](n) = 1$. Supposons que ce ne soit pas le cas, c'est-à-dire il existe $n$ pour lequel $\emptyset'(n) = 1$ et pour lequel étant donné $t$ le plus petit entier tel que $\emptyset'[t](n) = 1$, on a également $\Phi(A_t \upharpoonright_m, a_n)[t] \downarrow$ pour $m \le t$ tel que $A_t \upharpoonright_m = A \upharpoonright_m$. Dans ce cas, par la procédure décrite plus haut, on aura $\Phi_{a_n}(a_n) = \Phi(A_t \upharpoonright_m, a_n)$, et donc $\Phi_{a_n}(a_n) = \Phi(A \upharpoonright_m, a_n)$, ce qui contredit le fait que $\Phi$ calcule une fonction DNC sur l'oracle A.

L'oracle A peut donc calculer $\emptyset'$ en cherchant simplement le plus petit temps de calcul $t$ tel que $A_t \upharpoonright_m = A \upharpoonright_m$ et $\Phi(A_t \upharpoonright_m, a_n)[t] \downarrow$ pour $m \le t$, et puis en regardant si $\emptyset'[t](n) = 1$. Si c'est le cas, alors $\emptyset'(n) = 1$. Sinon $\emptyset'(n) = 0$. ■

Le critère de complétude d'Arslanov connaît plusieurs extensions, notamment par Jockusch et al. [101]. Nous donnons l'une d'entre elles dans un exercice qui permettra de manipuler les principes de la preuve précédente.

**Exercice 3.2. (★★)** (Bienvenu et al. [16]). Une fonction $g$ est DNC relativement à $C$, noté DNC($C$), si $g(n) \neq \Phi_n(C, n)$ pour tout $n$. Soit $X \in 2^\mathbb{N}$ de degré DNC et soit $C$ un ensemble c. e. Montrer que soit $X \oplus C \ge_T \emptyset'$, soit $X$ est de degré DNC relativement à $C$.

Indication.– Soit $g$ une fonction DNC. Définir des codes $a_{n,m}$ tels que

$$ \Phi_{a_{n,m}}(a_{n,m}) = \Phi_m(C_s, m), $$

pour $s$ le plus petit tel que $n \in \emptyset'[s]$. Montrer que soit il existe $n$ tel que la fonction $m \mapsto g(a_{n,m})$ est DNC relativement à $C$, soit $g \oplus C$ calcule $\emptyset'$. ◇

Notons que l'exercice précédent implique le critère de complétude d'Arslanov, car si $X$ et $C$ sont de même degré, soit $C \ge_T \emptyset'$, soit $C$ est de degré DNC relativement à $C$, ce qui est impossible.
# 4. Fonctions hyperimmunes

Nous abordons maintenant une seconde famille de propriétés calculatoires, basées sur la capacité à calculer des fonctions à croissance rapide. Les fonctions exponentielles, ou même de tours d'exponentielles sont calculables, et n'apportent donc pas de puissance de calcul supplémentaire. Nous parlons ici de fonctions dont la vitesse de croissance rend difficile toute représentation mentale.

Nous avons déjà vu dans la section 4-7 que la capacité à croître plus vite que certaines fonctions permettait de calculer les ensembles $Δ_0^0$. Nous allons maintenant étudier la puissance de calcul liée aux fonctions qui ne sont dominées par aucune fonction calculable. L'étude de ces fonctions a été initiée par Martin et Miller [157].

**Définition 4.1.** Une fonction *g* domine une fonction *f* si $g(x) \ge f(x)$ pour tout $x \in \mathbb{N}$. Une fonction $f: \mathbb{N} \to \mathbb{N}$ est hyperimmune si elle n'est dominée par aucune fonction calculable. ◇

En particulier, les fonctions calculables étant stables par modifications finies, une fonction $f: \mathbb{N} \to \mathbb{N}$ est hyperimmune si pour toute fonction calculable $g: \mathbb{N} \to \mathbb{N}$, $f(x) > g(x)$ pour une infinité de valeurs $x$.

**Exercice 4.2.** Montrer qu'une fonction $f$ est hyperimmune si, et seulement si, il existe pour toute fonction totale calculable $g$ une infinité d'entiers $x$ tels que $f(x) > g(x)$. ◇

<figure><img src="image_55.png" /><figcaption>FIGURE 4.3 – Illustration d'une fonction hyperimmune : elle ne croît pas nécessairement très vite, mais pour toute fonction calculable $f$ elle se situe infiniment souvent au-dessus de $f$.</figcaption></figure>

Tout comme les degrés DNC, les degrés Turing des fonctions hyperimmunes sont clos par le haut. Un degré Turing est hyperimmune s'il contient une fonction hyperimmune, ou de manière équivalente si un de ses éléments calcule une fonction hyperimmune. L'appellation « fonction hyperimmune » provient de la correspondance suivante avec les ensembles hyperimmunes.
**Proposition 4.4.** Un ensemble infini $X$ est hyperimmune si, et seulement si, la fonction $p_X: \mathbb{N} \to \mathbb{N}$ qui à $n$ associe le $n$-ième élément de $X$ est hyperimmune. ★

**PREUVE.** ⇒. Soit $X$ un ensemble hyperimmune et soit $g: \mathbb{N} \to \mathbb{N}$ une fonction totale calculable. Montrons que $p_X$ n'est pas dominée par $g$. Soit $h$ la fonction donnée par $h(x) = g(x) + x + 1$, et soit $(F_n)_{n \in \mathbb{N}}$ le tableau c. e. que l'on définit par $F_n = [h^{(n)}(0), h^{(n+1)}(0)]$, où $h^{(n)}$ est la $n$-ième itération de $h$, avec $h^{(0)}$ la fonction identité. Par hyperimmunité de $X$, il existe $n$ tel que $F_n \cap X = \emptyset$. Cela signifie que $p_X(h^{(n)}(0)) \ge h^{(n+1)}(0) = h(h^{(n)}(0))$. En prenant $x = h^{(n)}(0)$, nous avons $p_X(x) \ge h(x) = g(x) + x + 1$, donc $p_X$ n'est pas dominée par $g$.

⇒. Supposons que $p_X$ soit une fonction hyperimmune. Raisonnons par l'absurde, en supposant que l'ensemble $X$ ne soit pas hyperimmune. Autrement dit, il existe un tableau c. e. $(F_n)_{n \in \mathbb{N}}$ tel que $F_n \cap X \neq \emptyset$ pour tout $n$. Alors, la fonction $g: \mathbb{N} \to \mathbb{N}$ définie par $g(n) = \max \cup_{i \le n} F_i$ est totale calculable, et domine $p_X$, contredisant l'hyperimmunité de $p_X$. ■

Il s'ensuit qu'un degré est hyperimmune si, et seulement si, il contient un ensemble hyperimmune.

**Exercice 4.5.** Montrer que les degrés hyperimmunes sont clos par le haut. Autrement dit, si $X$ calcule une fonction hyperimmune, alors le degré $Turing$ de $X$ contient une fonction hyperimmune. ◇

**Exercice 4.6.** Montrer par la méthode des extensions finies qu'il existe un ensemble de degré hyperimmune. ◇

L'existence de degrés non calculables et non hyperimmunes n'est pour le moment pas claire. Nous verrons dans la section suivante que de tels degrés existent bien, même si nous comprendrons plus tard que ce n'est pas donné, dans le sens où « beaucoup » d'ensembles sont de degrés hyperimmune (voir la proposition 10-3.35 et le théorème 19-3.4). De fait, il va falloir travailler pour en exhiber un qui ne le soit pas. Nous voyons en particulier dès à présent que la construction d'un degré non calculable et non hyperimmune ne peut pas se faire à l'aide de $\emptyset'$. En particulier, des constructions par extensions finies comme vues dans la section 4-8, qui sont toutes effectives en $\emptyset'$, ne pourront pas fonctionner.

**Proposition 4.7 (Martin et Miller [157]).** Tout ensemble $\Delta_2^0$ non calculable est hyperimmune. ★

**PREUVE.** Soit $A$ un ensemble $\Delta_2^0$ non calculable, et soit $A_0, A_1, \dots$ une approximation $\Delta_2^0$ de $A$. Rappelons que la fonction de calcul (Définition 4
-7.7) est définie comme la fonction $c_A : \mathbb{N} \to \mathbb{N}$ qui à $x$ associe le plus petit entier $n \ge x$ tel que $A_n \upharpoonright_x A \upharpoonright_x$. En particulier, $c_A \le T_A$. D'après la proposition 4-7.9, toute fonction dominant $c_A$ calcule $A$. Comme $A$ n'est pas calculable, $c_A$ n'est dominée par aucune fonction calculable, autrement dit $c_A$ est hyperimmune. ■

Nous passons à présent à l'existence de degrés non calculables et non hyperimmunes, que l'on dira *calculatoirement dominés*.

# 5. Degrés calculatoirement dominés

Par clôture des degrés hyperimmunes par le haut, un degré Turing n'est pas hyperimmune si toute fonction $f$ qu'il calcule est dominée par une fonction calculable $g$ (qui dépend de $f$).

**Définition 5.1.** Un ensemble $X$ est calculatoirement dominé si pour toute fonction $f \le T_A$ $X$ il existe une fonction calculable $g$ dominant $f$. Un degré Turing $\mathbf{d}$ est calculatoirement dominé$^a$ si tout $X \in \mathbf{d}$ est calculatoirement dominé. ◇

Notons que le fait d'être calculatoirement dominé est une propriété de faiblesses et est donc close par le bas dans les degrés Turing. De fait, la propriété inverse — être de degré hyperimmune — est une propriété de force.

L'exemple le plus simple de degré calculatoirement dominé est le degré Turing des ensembles calculables. Le but de cette section est de démontrer l'existence de degrés calculatoirement dominés différents de 0. Nous verrons en fait un peu plus tard (théorème 8-5.1) que les degrés calculatoirement dominés sont en quantité indénombrable : il est possible de construire une injection $f : 2^N \to 2^N$ telle que pour tout $X$, l'ensemble $f(X)$ est de degré calculatoirement dominé, et même telle que $f(X)$ et $f(Y)$ soient dans des degrés Turing différents pour $X \neq Y$ (exercice 8-5.3). Le concept au cœur de la construction qui va suivre est celui de f-arbre.

**Définition 5.2.** Un f-arbre est une fonction totale $T : 2^{<N} \to 2^{<N}$ telle que pour tous $\sigma, \tau \in 2^{<N}$, $\sigma \preceq \tau$ si, et seulement si, $T(\sigma) \preceq T(\tau)$. ◇

Soit $T$ un f-arbre. Notons que l'image de $T$ (Im $T$) n'est pas close par préfixe en général. Notons également que pour tout $\sigma \in 2^{<N}$, $T(\sigma 0)$ et $T(\sigma 1)$ sont deux chaînes incompatibles étendant $T(\sigma)$. Seule l'image d'un f-arbre $T$ est importante. La structure arborescente du domaine de $T$ induit de manière canonique celle de Im $T$. Le lecteur peut se reporter à la figure 5.4 pour une représentation graphique d'un f-arbre.

<footnote>a. En anglais, les terminologies « computably dominated » et « hyperimmune-free » coexistent.</footnote>
**Définition 5.3.** Soit $T$ un f-arbre. On appelle nœuds les éléments de $\text{Im } T$. Un chemin de $T$ est une suite $P \in 2^N$ dont une infinité de segments initiaux appartiennent à $\text{Im } T$. On notera $[T]$ l'ensemble des chemins de $T$. ♦

<figure><img src="image_56.png" /><figcaption>FIGURE 5.4 – Illustration d'un f-arbre $T$, dont le domaine est représenté par les chaînes en gris clair : $T(\epsilon) = 0$, $T(0) = 000$, $T(1) = 010$, ...</figcaption></figure>

La figure 5.4, ci-dessus, illustre le fait qu’un f-arbre $T$ induit une injection $f_T : 2^N \to 2^N$, calculable à l’aide du f-arbre : pour $X \in 2^N$, la suite $f_T(X)$ se calcule petit à petit comme étant $T(X|_1) \prec T(X|_2) \prec \dots$. De plus, par les propriétés d’un f-arbre, si $X \neq Y$, alors $f_T(X) \neq f_T(Y)$.

**Définition 5.5.** Un sous-f-arbre d’un f-arbre $T$ est un f-arbre $S$ tel que

$$ \mathrm{Im} S \subseteq \mathrm{Im} T. \quad \diamond $$

Il s'ensuit que si $S$ est un sous-f-arbre de $T$, alors $[S] \subseteq [T]$. Nous avons à présent les ingrédients nécessaires pour passer à la preuve du théorème annoncé.

**Théorème 5.6 (Martin et Miller [157])**

Il existe un degré $d > 0$ calculatoirement dominé.

**PREUVE.** Nous voulons construire un ensemble $A$ de degré calculatoirement dominé en respectant les contrats $(R_e)_{e \in N}$ et $(S_e)_{e \in N}$ suivants :

$R_e : W_e \neq A \quad S_e : \Phi_e^A \text{ total} \Rightarrow \Phi_e^A \text{ dominé par une fonction calculable.}$
Nous allons construire une suite infinie de f-arbres calculables $T_0, T_1, T_2, \dots$
tels que pour tout $e \in \mathbb{N}$,

(1) $T_{e+1}$ est un sous-f-arbre de $T_e$;

(2) $|T_e(\epsilon)| \ge e$;

(3) Pour tout chemin $P \in [T_{2e+1}]$, le contrat $\mathcal{R}_e$ est satisfait;

(4) Pour tout chemin $P \in [T_{2e+2}]$, le contrat $\mathcal{S}_e$ est satisfait.

**Satisfaction d'un contrat** $\mathcal{R}_e$. Donnons-nous un f-arbre calculable $T$. Comme $\sigma_0=T(0)$ et $\sigma_1=T(1)$ sont des chaînes incompatibles, il existe $i \in \mathbb{N}$ tel que $\sigma_0(i) \neq \sigma_1(i)$. Ainsi, soit $\sigma_0(i) \neq W_e(i)$, soit $\sigma_1(i) \neq W_e(i)$. Supposons que l'on soit dans le premier cas, l'autre étant symétrique. Alors, le sous-f-arbre $S$ de $T$ défini par $S(\rho) = T(0\rho)$ assure que pour tous les chemins $P \in [S]$, $\sigma_0 \le P$, donc $P \neq W_e$. De plus, $S$ est calculable en $T$, donc calculable.

**Satisfaction d'un contrat** $\mathcal{S}_e$. Soit $T$ un f-arbre calculable. Nous allons construire un sous-f-arbre calculable $S$ tel que soit $\Phi_e^P$ est partiel pour tout $P \in [S]$, soit $\Phi_e^P$ est total et dominé par une même fonction calculable pour tout $P \in [S]$. Notons qu'en plus de satisfaire le contrat $\mathcal{S}_e$, la fonctionnelle $\Phi_e^P$ sera soit partielle, soit totale quel que soit le chemin $P$. Les deux cas suivants se présentent.

Cas 1. Il existe un nœud $\sigma \in \text{Im } T$ et une entrée $x \in \mathbb{N}$ tels que $\Phi^\tau(x) \uparrow$ pour tout $\tau \in \text{Im } T$ tel que $\tau \ge \sigma$. Soit $\rho \in 2^{<\mathbb{N}}$ tel que $T(\rho) = \sigma$. Par suite, le sous-f-arbre $S$ de $T$ défini par $S(\mu) = T(\rho\mu)$ assure que pour tous les chemins $P \in [S]$, des segments initiaux $\tau$ de $P$ arbitrairement longs satisferont $\Phi^\tau(x) \uparrow$. Par la propriété de l'usage, il s'ensuit que $\Phi^P(x) \uparrow$.

Cas 2. Pour tout nœud $\sigma \in \text{Im } T$ et toute entrée $x \in \mathbb{N}$, il existe $\tau \in \text{Im } T$ tel que $\sigma \ge \tau$ et $\Phi^\tau(x) \downarrow$. Nous allons définir $S$, un sous-f-arbre calculable de $T$ tel que pour tout $\rho \in 2^{<\mathbb{N}}$, $\Phi_e^{S(\rho)}(|\rho|) \downarrow$. On calcule $S(\epsilon)$ comme étant le premier nœud de $\text{Im } T$ que l'on trouve tel que $\Phi_e^{S(\epsilon)}(0) \downarrow$. Supposons que l'on a calculé $S(\rho)$. Soit $\mu$ tel que $S(\rho) = T(\mu)$. Nous calculons $S(\rho 0)$ et $S(\rho 1)$ comme suit : pour chaque entier $i < 2$, $S(\rho i)$ est le premier nœud $\tau \in \text{Im } T$ que l'on trouve, avec $\tau \ge T(\mu i)$ et tel que $\Phi^\tau(|\rho| + 1) \downarrow$. L'algorithme qui recherche les nœuds $S(\rho 0)$ et $S(\rho 1)$ aboutira toujours, par l'hypothèse que nous sommes dans le cas 2. Par construction, $S$ est bien un f-arbre, et $\text{Im } S \subseteq \text{Im } T$. Plus encore, $\Phi_e^P$ est une fonction totale pour tout $P \in [S]$. Montrons que $\Phi_e^P$ est dominée par une fonction calculable pour tout chemin $P \in [S]$. Soit $g : \mathbb{N} \to \mathbb{N}$ définie par $g(n) = \max\{\Phi_e^{S(\rho)}(n) : |\rho| = n\}$. Alors, pour tous $n \in \mathbb{N}$ et $P \in [S]$, $\Phi_e^P(n) \le g(n)$. Le sous-f-arbre $S$ de $T$ satisfait bien le contrat $\mathcal{S}_e$.

Notons enfin pour satisfaire le point (2) ci-dessus que pour tout f-arbre $T$ calculable et tout $n$, il existe un sous-f-arbre $S$ tel que $S(\epsilon) \ge n$. En effet,
il suffit de fixer une chaîne $\rho$ de longueur $n$, et de définir $S(\mu) = T(\rho\mu)$.
Nous pouvons donc combiner les satisfactions des différents contrats et
cette dernière observation pour construire une suite de f-arbres $T_0, T_1, \dots$
satisfaisant les propriétés (1) (2) (3) et (4) données plus haut.

**Remarque**

Chaque f-arbre $T_e$ de la suite pris indépendamment est calculable, mais
la suite $T_0, T_1, \dots$ n'est pas elle-même calculable.

Afin de terminer la preuve, nous avons besoin du lemme suivant.

**Lemme 5.7.** L'intersection $\bigcap_e[T_e]$ contient exactement un élément. ★

PREUVE. Comme Im $T_{e+1} \subseteq$ Im $T_e$ et comme toute chaîne de Im $T_e$ est une extension de $T_e(\epsilon)$, il est clair que l'on a $T_0(\epsilon) \preceq T_1(\epsilon) \prec T_2(\epsilon) \prec \dots$

Par ailleurs, comme $|T_e(\epsilon)| \ge 3$, la suite $T_0(\epsilon) \preceq T_1(\epsilon) \prec T_2(\epsilon) \prec \dots$ converge vers une unique suite infinie $X \in 2^N$. Comme $X$ a une infinité de préfixes dans chaque $T_e$, alors $X \in [T_e]$ pour tout $e$, et donc $X \in \bigcap_e[T_e]$. ■

Soit $A$ l'élément de $\bigcap_e[T_e]$. Pour tout $e \in \mathbb{N}$, comme $A \in [T_{2e+1}]$, alors le contrat $\mathcal{R}_e$ est satisfait pour $A$, donc $W_e \neq A$. De plus, comme $A \in [T_{2e+2}]$, alors le contrat $S_e$ est satisfait pour $A$, donc si $\Phi_e^A$ est total, $\Phi_e^A$ est dominé par une fonction calculable. Il s'ensuit que $A$ est calculatoirement dominé et non calculable. ■

**Remarque**

Une analyse soigneuse de la construction précédente montre qu’il suf-
fit de l’oracle $\emptyset''$ pour calculer uniformément la suite $(T_e)_{e \in \mathbb{N}}$. En effet,
les seules parties non calculables sont les analyses de cas, qui sont des
propriétés $\Sigma_2^0$. Ainsi, il existe un degré $\mathbf{d} > 0$ à la fois $\Delta_3^0$ et calculatoi-
rement dominé. Comme nous l’avons vu avec la proposition 4.7, il n’est
pas possible d’abaisser cette borne à $\Delta_2^0$.

Nous retrouverons la structure des f-arbres dans le chapitre 14 pour montrer
l'existence de degrés Turing minimaux.

**Exercice 5.8. (★★)** Construire un f-arbre $T$, par la méthode des extensions finies, tel que tout $X, Y \in [T]$ sont dans des degrés Turing différents. ◇

Notons que nous avions annoncé l'existence d'une quantité indénombrable
de degrés calculatoirement dominés. Cela sera fait avec le théorème 8-5.1.
Nous donnons à présent quelques équivalences permettant de mieux cerner
cette notion.
**5.1. Réduction truth-table**

On suppose ci-après que les fonctionnelles considérées essayent de calculer
des ensembles d'entiers et non des fonctions, c'est-à-dire que si $\Phi(Y, n) \downarrow$
pour un certain oracle $Y$ et un certain entier $n$, alors $\Phi(Y, n) \downarrow \in \{0, 1\}$
(si $\Phi(Y, n) \downarrow \notin \{0, 1\}$, on considérera alors que la fonctionnelle diverge).

Soient une fonctionnelle $\Phi$ et un oracle $X$ tels que $\forall n \Phi(X, n) \downarrow \in \{0, 1\}$.
Étant donné un autre ensemble $Y \neq X$, il n'y a aucune raison pour which
l'on ait également $\forall n \Phi(Y, n) \downarrow$. Une fonctionnelle totale avec un oracle ne
l'est pas forcément avec les autres, et il ne devrait pas être très dur pour
le lecteur de construire de tels exemples. Mais de telles fonctionnelles sont-
elles nécessaires ? Si l'on suppose $X \geq_T Y$, peut-on toujours calculer $Y$ à
partir de $X$ via une fonctionnelle totale sur tous les oracles ? Nous allons
voir que ce n'est pas forcément le cas via une restriction de la notion de
réduction Turing.

**Définition 5.9.** Pour tous ensembles $X, Y \subseteq \mathbb{N}$, on dit que $X$ est *truth-table réductible* à $Y$, et l'on écrit $X \leq_{tt} Y$, s'il existe une fonctionnelle $\Phi$ telle que $\Phi(Y) = X$ et telle que $\Phi(Z)$ est totale pour tout oracle $Z$. On écrit $X \equiv_{tt} Y$ si $X \leq_{tt} Y$ et $Y \leq_{tt} X$. On écrit $X <_{tt} Y$ si $X \leq_{tt} Y$ et $Y \not\leq_{tt} X$. On appelle *degrés truth-table* les classes d'équivalences de la relation $\equiv_{tt}$. $\diamond$

Remarquons la notation $\Phi(Y) = X$ signifiant $\forall n \Phi(Y, n) = X(n)$. Nous verrons plusieurs définitions équivalentes à la réduction truth-table, à commencer par celle justifiant son nom, que l'on peut traduire en français par « réduction par table de vérité ».

**Définition 5.10.** Une réduction par table de vérité est donnée par une
suite calculable de paires $((C_{0,n}, C_{1,n})_{n \in \mathbb{N}})$ telle que pour tout $n$ l'en-
semble $C_{0,n} \cup C_{1,n} \subseteq 2^{<\mathbb{N}}$ contient exactement toutes les chaînes d'une
certaine taille $m_n$, et telle que $C_{0,n} \cap C_{1,n} = \emptyset$. L'ensemble $X$ calcule $Y$
via cette réduction si pour tout $n$ on a $Y(n) = i$ ssi $\sigma \in C_{i,n}$ pour un
préfixe $\sigma$ de $X$. $\diamond$

Les ensembles $C_{i,n}$ sont les « tables de vérité ». N'importe quel oracle $X$
admet un préfixe dans $C_{0,n} \cup C_{1,n}$. Si le préfixe appartient à $C_{0,n}$, alors $X$
calcule 0 sur l'entrée $n$ ; et, si le préfixe appartient à $C_{1,n}$, alors $X$ calcule 1
sur l'entrée $n$. Voyons à présent les différentes équivalences à la notion de
réduction truth-table.
**Théorème 5.11**

Soient $X, Y$ des ensembles. Les énoncés suivants sont équivalents.

(1) $Y \le_{tt} X$.

(2) $X$ calcule $Y$ via une réduction par table de vérité.

(3) Il existe une fonctionnelle $\Phi$ et une fonction $b: \mathbb{N} \to \mathbb{N}$ totale calculable telle que $\Phi(X, n)[b(n)] \downarrow= Y(n)$ pour tout $n$.

PREUVE. Montrons (1) ⇒ (2). Supposons $\Phi(X) = Y$ via une fonctionnelle $\Phi$ totale sur tous les oracles. Étant donné $n$, on cherche le plus petit temps de calcul $t_n$ tel que, pour un certain $m_n \le t_n$ et pour toute chaîne $\sigma \in 2^\mathbb{N}$ de taille $m_n$, on a $\Phi(\sigma, n)[t_n] \downarrow$. Afin de montrer qu'un tel temps de calcul $t_n$ existe forcément pour tout $n$, on doit anticiper un peu sur la définition 8-1.1 d'arbre et le lemme 8-1.4 de König à venir. Supposons par l'absurde que, pour un certain $n$, on ne puisse trouver $t_n$. Cela implique en particulier que, pour tout $m$, il existe une chaîne $\sigma$ de taille $m$ telle que $\forall t \Phi(\sigma, n)[t] \uparrow$. Par ailleurs, si $\forall t \Phi(\sigma, n)[t] \uparrow$ et $\tau \le \sigma$, alors aussi $\forall t \Phi(\tau, n)[t] \uparrow$. On peut donc construire un arbre infini $T$ tel que $\sigma \in T$ implique $\forall t \Phi(\sigma, n)[t] \uparrow$. D'après le lemme de König, $T$ contient un chemin infini $Y$, qui est donc tel que $\Phi(Y, n) \uparrow$, ce qui contredit le fait que $\Phi$ soit totale sur tous ses oracles. On peut donc à chaque étape trouver $t_n$ et $m_n \le t_n$, avec l'ensemble $C_{0,n}$ des chaînes de tailles $m_n$ sur lesquelles le calcul renvoie 0 en $t_n$ étapes, et l'ensemble $C_{1,n}$ des chaînes de tailles $m_n$ sur lesquelles le calcul renvoie 1 en $t_n$ étapes.

Montrons (2) ⇒ (3). Étant donné une réduction ≪ table de vérité ≫ donnée par la suite calculable $((C_{0,n}, C_{1,n})_{n \in \mathbb{N}})$, pour toute entrée $n$ on peut borner le temps de calcul que la fonctionnelle met pour s'arrêter sur $n$ avec n'importe quel oracle : il s'agit simplement du temps nécessaire pour produire le calcul de $\langle C_{0,n}, C_{1,n} \rangle$.

Montrons (3) ⇒ (1). Soit $\Phi$ une fonctionnelle, et soit $b: \mathbb{N} \to \mathbb{N}$ une fonction totale calculable telle que

$$ \Phi(Y, n)[b(n)] \downarrow= X(n), \quad \text{pour tout } n. $$

Alors, on construit la fonctionnelle $\Psi$ qui sur tous les oracles $Z$ et sur toute entrée $n$ lance le calcul de $\Phi(Z, n)$ en $b(n)$ étapes. Si le calcul renvoie une valeur en $b(n)$ étapes, alors $\Psi$ renvoie cette valeur, sinon $\Psi$ renvoie 0. Le résultat du calcul est le même entre $\Phi$ et $\Psi$ sur l'oracle $Y$, mais $\Psi$ est maintenant totale sur tous les oracles. ■

Nous montrons à présent que les ensembles $X$ pour lesquels $X \ge_T Y$ implique $X \ge_{tt} Y$ sont exactement les ensembles calculatoirement dominés.
**Théorème 5.12 (Jockusch [97], Martin (non publié))**

Un ensemble $X$ est calculatoirement dominé ssi $Y \leq_T X \Leftrightarrow Y \leq_{tt} X$ pour tout $Y \in 2^N$.

**PREUVE.** Supposons $X$ calculatoirement dominé. Supposons $X \geq_T Y$ via la fonctionnelle $\Phi$. Soit $f: \mathbb{N} \to \mathbb{N}$ telle que $\Phi(X, n)[f(n)] \downarrow= Y(n)$ pour tout $n$. Notons que $f$ est une fonction $X$-calculable. Il y a donc une fonction calculable $g > f$. On a ainsi $\Phi(X, n)[g(n)] \downarrow= Y(n)$. D'après le théorème 5.11, on a donc $X \geq_{tt} Y$.

Supposons maintenant que pour tout $Y$ on ait $Y \leq_T X \Leftrightarrow Y \leq_{tt} X$. Alors, également pour toute fonction $f: \mathbb{N} \to \mathbb{N}$, on a $f \leq_T X \Leftrightarrow f \leq_{tt} X$, via la représentation canonique de $f$ par une suite de $2^N$. Soit $f \leq_T X$; montrons que $f$ est dominée par une fonction calculable $g$. Par hypothèse, $f \leq_{tt} X$, donc par le théorème 5.11, il existe une fonctionnelle $\Phi$ et une fonction totale calculable $b: \mathbb{N} \to \mathbb{N}$ telle que $\Phi(X, n)[b(n)] \downarrow= f(n)$ pour tout $n$. On peut supposer sans perte de généralité que si $\Phi(X, n)[b(n)] \downarrow$, alors l'usage du calcul est inférieur à $b(n)$ (si ce n'est pas le cas, on peut ralentir le calcul pour que cela le soit), donc $\Phi(X \upharpoonright_{b(n)}, n)[b(n)] \downarrow$. Soit $g: \mathbb{N} \to \mathbb{N}$ la fonction qui pour une entrée $n$, exécute $\Phi(\sigma, n)[b(n)]$ pour tout $\sigma \in 2^{<N}$ de longueur $b(n)$, et renvoie le maximum des valeurs obtenues. En particulier,

$$g(n) \geq \Phi(X \upharpoonright_{b(n)}, n)[b(n)] = f(n).$$

La fonction $g$ domine $f$. Il s'ensuit que $X$ est de degré calculatoirement dominé. $\blacksquare$

Nous avons à présent trois notions de réduction : la réduction many-one, la réduction truth-table et la réduction Turing. La proposition suivante récapitule certains résultats vus jusqu'ici, qui attestent qu'aucune ne coïncide avec une autre.

**Proposition 5.13.** Pour tous $X, Y$, on a

$$X \leq_m Y \Rightarrow X \leq_{tt} Y \Rightarrow X \leq_T Y.$$

Aucune implication inverse n'est vraie dans le cas général. $\star$

**PREUVE.** Les implications sont claires. Montrons qu'aucune implication réciproque ne tient. L'ensemble $\mathbb{N} \setminus \emptyset'$ est $tt$-réductible à $\emptyset'$ mais non $m$-réductible à $\emptyset'$, car il serait alors $\Sigma_1^0$ d'après la proposition 5-4.3, et donc $\emptyset'$ serait calculable ce qui est faux.

L'existence d'ensembles $X, Y$ tels que $X \geq_T Y$ mais $X \not\geq_{tt} Y$ est une conséquence du théorème 5.12 et du fait que des degrés non calculatoirement dominés existent (par exemple $0'$). $\blacksquare$
# 6. Théorème de domination de Martin

Les fonctions hyperimmunes sont par définition les fonctions qui ne sont dominées par aucune fonction calculable. Il est naturel de se poser la question de la puissance de calcul des fonctions qui dominent toutes les fonctions calculables. Bien entendu, aucune fonction $f : \mathbb{N} \to \mathbb{N}$ ne domine toutes les fonctions calculables, car la fonction constante $f(0) + 1$ n'est pas dominée par $f$. On peut cependant affaiblir la propriété, et se poser la question de la puissance calculatoire d'une fonction $f : \mathbb{N} \to \mathbb{N}$ telle que pour toute fonction calculable $g : \mathbb{N} \to \mathbb{N}$, $f$ domine $g$ presque partout, c'est-à-dire partout sauf pour un nombre fini de valeurs.

**Notation**

On utilisera les notations $\forall^\infty m$ et $\exists^\infty m$ pour signifier respectivement $\exists n \forall m > n$ et $\forall n \exists m > n$. Ainsi, $\forall^\infty m$ signifie « pour presque tout $m$ », et $\exists^\infty m$ signifie « pour une infinité de $m$ ».

<figure><img src="image_57.png" /><figcaption>FIGURE 6.1 – *Illustration d'une fonction high, qui pour toute fonction calculable f, est toujours au-dessus de f à partir d'une certaine valeur*</figcaption></figure>

Le théorème de domination de Martin ((1) ⇔ (2) dans le théorème suivant [148]) donne une magnifique caractérisation des degrés Turing de ces fonctions. L'équivalence (2) ⇔ (3) montrée par Jockusch [98] est venue plus tard et présente elle aussi son intérêt. Rappelons qu'un ensemble $A$ est high si $A' \ge_T \emptyset''$ (voir la définition 4-10.1).

**Théorème 6.2**

Soit $A \subseteq \mathbb{N}$ un ensemble. Les énoncés suivants sont équivalents.

(1) $A$ est high.

(2) $A$ calcule une fonction $g : \mathbb{N} \to \mathbb{N}$ qui domine presque partout toutes les fonctions calculables. Cela signifie que pour toute fonction calculable $f$, on a $\forall^\infty n f(n) \le g(n)$.

(3) $A$ calcule une liste $(X_n)_{n \in \mathbb{N}}$ contenant (éventuellement avec répétitions) exactement les ensembles calculables.
PREUVE. Montrons (1) ⇒ (2). Supposons que $A$ soit high. On a donc une description $\Delta_2^0(A)$ de $\emptyset''$, c'est-à-dire une fonction $A$-calculable $f : \mathbb{N}^2 \to \mathbb{N}$ telle que $\lim_{s\to\infty} f(n,s) = \emptyset''(n)$ pour tout $n$. Notons qu'être le code d'une fonction totale est une propriété $\Pi_2^0$. On peut en particulier, en utilisant le fait que $\emptyset''$ soit $\Sigma_2^0$-complet (voir la proposition 5-5.3), calculer pour tout $e$ un code $a_e$ tel que $\emptyset''(a_e) = 0$ ssi $\Phi_e$ est une fonction totale.

On définit $g$ de la manière suivante : sur l'entrée $t$, pour toute fonctionnelle $\Phi_e$ pour $e \le t$, on cherche le plus petit temps de calcul $s \ge t$ tel que $f(a_e, s) = 1$ ou tel que $\Phi_e(t)[s] \downarrow$. Notons qu'un des deux événements arrive forcément : soit $\Phi_e$ est totale et donc $\Phi_e(t) \downarrow$, soit $\Phi_e$ est partielle et donc $\lim_{s\to\infty} f(a_e, s) = \emptyset''(a_e) = 1$. Dans le premier cas, on définit $v_{t,e} = 0$, et dans le second, $v_{t,e} = \Phi_e(t)$. On définit finalement $g(t) = \sum_{e\le t} v_{t,e}$.

Il est clair que pour toute fonction totale $\Phi_e$, à partir du plus petit $t \ge e$ tel que $f(a_e, s) = 0$ pour $s \ge t$, on aura $g(s) \ge \Phi_e(s)$ pour tout $s \ge t$. Donc, $g$ domine presque partout toutes les fonctions calculables.

Montrons (2) ⇒ (3). Supposons à présent que $A$ calcule une fonction $g$ qui domine presque partout toute fonction calculable. On utilise le fait que si $\Phi_e$ est totale à valeur dans $\{0,1\}$, alors la fonction calculable $t : \mathbb{N} \to \mathbb{N}$ qui sur $n$ renvoie le plus petit temps de calcul tel que $\Phi_e(n)[t(n)] \downarrow$, pour tout $n$, est dominée par $g$ presque partout.

Pour chaque fonctionnelle $\Phi_e$, on calcule l'ensemble $Y_e$ comme étant

$$Y_e(n) = \Phi_e(n)[g(n)] \quad \text{si} \quad \Phi_e(n)[g(n)] \downarrow \in \{0,1\}, \quad \text{et} \quad Y_e(n) = 0 \text{ sinon.}$$

La liste $(Y_e)_{e \in \mathbb{N}}$ contient donc, à modification finie près, exactement les ensembles calculables. Pour les obtenir tous, on calcule en fin de compte la suite $(X_n)_{n \in \mathbb{N}}$ comme étant toutes les modifications finies possibles des ensembles $Y_e$.

Montrons (3) ⇒ (1). Le lecteur peut s'aider de la figure 6.4 pour la compréhension de cette implication. Supposons que $A$ calcule une liste $(X_n)_{n \in \mathbb{N}}$ contenant (éventuellement avec répétitions) exactement les ensembles calculables. Soit $P = \{e : \forall x_1 \exists x_2 R(e, x_1, x_2)\}$ un ensemble $\Pi_2^0$ quelconque. Montrons que $P$ est $\Sigma_2^0(A)$. Pour cela, on définit uniformément pour tout $e$ une fonction partielle calculable $f_e : \mathbb{N} \to \{0,1\}$ telle que :

(a) $e \in P$ implique que $f_e$ est une fonction totale calculable;

(b) $e \notin P$ implique que $f_e$ est une fonction partielle qui ne peut pas être complétée en une fonction totale calculable.

Soit $e$ fixé. On décrit un processus uniforme en $e$. À l'étape de calcul $t$, pour toute valeur $n \le t$ et telle que $f_e$ ne n'arrête pas pour le moment sur $n$, on procède comme suit : si $\Phi_n(n)[t] \downarrow \ne 0$, on définit $f_e(n) = 0$.
Sinon, si $\Phi_n(n)[t] \downarrow= 0$, on définit $f_e(n) = 1$. Sinon, si pour tout $k \le n$ il existe $m_k \le t$ tel que $R(e, k, m_k)$, alors on définit $f_e(n) = 0$.

Le processus est clairement calculable. Montrons (a). Supposons $e \in P$. Alors, pour tout $n$, il existe un plus petit $t$ tel que pour tout $k \le n$ il existe $m_k \le t$ pour lequel $R(e, k, m_k)$. Quand cela arrive, alors $f_e(n)$ prend une valeur à l'étape $t$ si elle n'en a pas prise jusqu'ici. Donc, $f_e$ est total. Montrons à présent l'assertion (b). Supposons $e \notin P$. Soit $n$ le plus grand entier tel que pour tout $k \le n$ il existe $m_k$ pour lequel $R(e, k, m_k)$. Pour $m > n$, $f_e(m)$ s'arrête ssi $\Phi_m(m)$ s'arrête, auquel cas $f_e(m) \ne \Phi_m(m)$. Supposons par l'absurde que $f_e$ a une complétion calculable. Alors, par le lemme de remplissage (le lemme 3-5.1), elle a une complétion calculable de code $a > n$. Dans ce cas, $f_e(a) = \Phi_a(a)$, ce qui contredit la définition de $f_e$. On a donc (b).

Il s'ensuit que $P$ peut s'écrire comme un ensemble $\Sigma_2^0(A)$ de la manière suivante.

$$P = \{e : \exists n \ \forall m \ \forall t \ f_e(m)[t] \uparrow \lor f_e(m)[t] \downarrow = X_n(m)\}.$$

En effet, si $e \in P$, alors $f_e$ est calculable, et coïncide ainsi avec un certain $X_n$. À l'inverse, si $e \notin P$, alors $f_e$ n'a pas de complétion calculable, et donc pas de complétion dans $(X_n)_{n \in \mathbb{N}}$. Comme $P$ est $\Sigma_2^0(A)$ et $\overline{P}$ est par définition $\Sigma_2^0$, on a donc que $P$ est $\Delta_2^0(A)$, et $P$ est dès lors $A'$-calculable. Il suffit d'appliquer cela pour $P = \mathbb{N} \setminus \emptyset''$ pour obtenir que $\emptyset''$ est $\Delta_2^0(A)$, et donc $A'$-calculable. $\blacksquare$

L'implication (3) $\Rightarrow$ (1) du théorème 6.2 est loin d'être évidente. Nous espérons que le lecteur saura apprécier l'argument, dont la subtile complexité est caractéristique du travail de Jockusch. L'exercice suivant donne des caractérisations alternatives similaires, plus simples à démontrer.

**Exercice 6.3.** (★) Montrer les équivalences suivantes :

(1) A calcule une fonction qui domine presque partout toute fonction calculable;

(2) A calcule une suite $(f_n)_{n \in \mathbb{N}}$ contenant toutes les fonctions calculables de $\mathbb{N}$ vers $\mathbb{N}$;

(3) A calcule une suite $(X_n)_{n \in \mathbb{N}}$ ne contenant que des ensembles infinis, et contenant tous les ensembles calculables infinis. $\diamond$

Discutons un peu de la caractérisation (1) $\Leftrightarrow$ (2) du théorème 6.2, illustrée par la figure 6.1. Le fait de pouvoir calculer une fonction de $\mathbb{N}$ dans $\mathbb{N}$ à très forte croissance est susceptible de donner beaucoup de puissance de calcul. Ainsi, par exemple, comme nous l'avons vu, calculer une fonction qui borne le temps d'arrêt des programmes informatiques permet de calculer $\emptyset'$.
<table><thead><tr><th>$f_e$</th><th>$X_0$</th><th>$X_1$</th><th>$X_2$</th><th>...</th></tr></thead><tbody><tr><td>$f_e(0)$</td><td>$X_0(0)$</td><td>$X_1(0)$</td><td>$X_2(0)$</td><td></td></tr><tr><td>$f_e(1)$</td><td>$X_0(1)$</td><td>$X_1(1)$</td><td>$X_2(1)$</td><td></td></tr><tr><td>$\uparrow$</td><td>$X_0(2)$</td><td>$X_1(2)$</td><td>$X_2(2)$</td><td></td></tr><tr><td>$\uparrow$</td><td>$X_0(3)$</td><td>$X_1(3)$</td><td>$X_2(3)$</td><td></td></tr><tr><td>$f_e(4)$</td><td>$X_0(4)$</td><td>$X_1(4)$</td><td>$X_2(4)$</td><td></td></tr><tr><td>$\uparrow$</td><td>$X_0(5)$</td><td>$X_1(5)$</td><td>$X_2(5)$</td><td></td></tr><tr><td>$f_e(6)$</td><td>$X_0(6)$</td><td>$X_1(6)$</td><td>$X_2(6)$</td><td></td></tr><tr><td>$\uparrow$</td><td>$X_0(7)$</td><td>$X_1(7)$</td><td>$X_2(7)$</td><td></td></tr><tr><td>$\dots$</td><td>$\dots$</td><td>$\dots$</td><td>$\dots$</td><td></td></tr></tbody></table>

FIGURE 6.4 – Illustration de la preuve (3) ⇒ (1) du théorème 6.2 : si $e \notin P$, on construit une fonction partielle calculable $f_e: \mathbb{N} \to \{0,1\}$ qui n'a pas de complétion totale calculable. Dans l'illustration, la fonction $f_e$ ne peut être égale à aucun des ensembles $X_0, X_1, \dots$ sur toutes les valeurs pour les quelles elle est définie. En effet, la liste $(X_n)_{n \in \mathbb{N}}$ ne contient que des ensembles calculables. Dans le cas inverse, la fonction $f_e$ est totale calculable, et est donc égale à au moins un des ensembles $X_i$, puisque la liste $(X_n)_{n \in \mathbb{N}}$ contient tous les ensembles calculables.

Le théorème précédent indique qu'il y a un premier niveau entre les fonctions permettant de calculer l'arrêt simplement parce qu'elles croissent très vite, et les fonctions de croissance calculable : il existe d'après la proposition 4-10.2 des ensembles high ne calculant pas l'arrêt, et donc des fonctions de croissance « intermédiaire ». Nous verrons également que plus une fonction croît rapidement, plus elle a une puissance de calcul importante. Une fonction qui croît suffisamment vite pourra calculer $\emptyset''$, une qui croît encore plus vite pourra calculer $\emptyset'''$, etc. Nous verrons malgré tout avec le théorème 29-5.4 qu'il existe une limite à la puissance de calcul que confère une croissance rapide. La classe des ensembles calculables par n'importe quelle fonction qui croît « suffisamment » vite a une caractérisation précise et reste malgré tout dénombrable.

**Exercice 6.5. (★★)** La notion d'ensemble c. e. maximal fut introduite dans l'exercice 3-7.13. Un ensemble c. e. $X$ est maximal si $N \setminus X$ est infini, et si tout ensemble c. e. $Y \supseteq X$ est tel que $Y \setminus X$ est fini ou tel que $N \setminus Y$ est fini. Soit $X$ un ensemble c. e. maximal; montrer que $X$ est high. ◇
# 7. Degrés High ou DNC

Nous terminons ce chapitre par un résultat qui combine degré high et DNC, afin d'obtenir une caractérisation naturelle en termes de puissance de calcul : la possibilité de calculer une fonction qui diffère presque partout de toute fonction calculable.

**Théorème 7.1 (Kjos-Hanssen, Merkle et Stephan [113])**

Soit $X \in 2^\mathbb{N}$. Les énoncés suivants sont équivalents :

(1) $X$ est de degré high ou DNC;

(2) $X$ calcule une fonction qui est différente presque partout de toute fonction calculable.

**PREUVE.** Montrons (1) ⇒ (2). Supposons pour commencer que $X$ est high. Soit $g \leq_T X$ une fonction qui domine presque partout toute fonction calculable. Alors, également, $m \mapsto g(m) + 1$ est différente presque partout de toute fonction calculable. Supposons à présent que $X$ est DNC. Pour chaque $n$, on calcule le code $e_n$ tel que $W_{e_n}$ énumère toutes les valeurs $\Phi_e(n)$ pour $e \leq n$ pour lesquelles $\Phi_e(n) \downarrow$. D'après le théorème 2.6, $X$ calcule une fonction $h: \mathbb{N}^2 \to \mathbb{N}$ telle que pour tout $e, n \in \mathbb{N}$, si $|W_e| \leq n$, alors $h(e, n) \notin W_e$. Soit $f: \mathbb{N} \to \mathbb{N}$ la fonction $X$-calculable définie par $f(n) = h(e_n, n)$. On a alors $f(n) \notin W_{e_n}$ pour tout $n$. Ainsi, $f(n)$ est différent de $\Phi_0(n), \Phi_1(n), \dots, \Phi_n(n)$ pour tout $n$, donc $f$ diffère presque partout de toute fonction calculable (et même de toute fonction partielle calculable s'arrêtant sur une infinité de valeurs).

Montrons (2) ⇒ (1). Si $X$ est high, il n'y a rien à vérifier. Supposons donc que $X$ n'est pas high. Soit $g \leq_T X$ telle que $\Phi_e$ totale implique $\forall^\infty m g(m) \neq \Phi_e(m)$. Nous prétendons avoir également

$$ \forall^\infty e g(e) \neq \Phi_e(e). $$

Supposons par l'absurde le contraire. Soit $f$ la fonction $X$-calculable qui sur $n$ renvoie le plus petit temps de calcul $t$ tel que $g(m) = \Phi_m(m)[t] \downarrow$ pour un entier $m > n$. Comme $X$ est non high, il existe une fonction calculable $b$ telle que $\exists^\infty n b(n) \geq f(n)$. Notons que l'on peut supposer sans perte de généralité que $b(n) \leq b(n+1)$.

On définit à présent la fonction totale calculable $h$ par $h(n) = \Phi_n(n)[b(n)]$ si $\Phi_n(n)[b(n)] \downarrow$, et $h(n) = 0$ sinon. Supposons à présent $b(n) > f(n)$. Par définition de $f$, il existe une valeur $m > n$ telle que $\Phi_m(m)[f(n)] \downarrow = g(m)$, et donc telle que $\Phi_m(m)[b(n)] \downarrow = g(m)$. Comme $b(m) \geq b(n)$, on aura

$$ h(m) = \Phi_m(m)[b(m)] \downarrow = g(m). $$

Comme on peut recommencer l'argument pour des valeurs de $n$ arbitrairement grandes, on aura $h(m) = g(m)$ pour une infinité de $m$. Cela contredit
le fait que $g$ diffère presque partout de toute fonction calculable. Donc, nous avons $\forall\infty e g(e) \neq \Phi_e(e)$. Il suffit alors de modifier un nombre fini de valeurs de $g$ pour obtenir une fonction DNC. ■

Notons pour donner tout son éclat au théorème précédent qu'il est possible de construire des degrés DNC qui ne sont pas high (en combinant le corollaire 18-4.3 avec le corollaire 19-3.9 ou plus simplement en considérant le corollaire 8-6.6) tout comme des degrés high qui ne sont pas DNC (voir le corollaire 10-3.34).
Chapitre 8

Classes Π₁₀ et degrés PA

Nous nous sommes jusqu'à présent concentrés principalement sur l'étude des ensembles d'entiers naturels pris individuellement, ou de manière équivalente, des fonctions des entiers vers les entiers. Nous allons maintenant nous tourner vers l'étude de classes d'ensembles ou de fonctions, c'est-à-dire d'ensembles d'ensembles d'entiers.

Nous avons déjà vu de nombreuses classes d'ensembles, notamment la classe des ensembles de degré high {$X \in 2^N : X' \geq_T 0''$}, ou celle des ensembles de degré low {$X \in 2^N : X' \equiv_T 0'$}.

Ensemble vs classe

Afin de distinguer les ensembles d'entiers des sous-ensembles de l'es-
pace de Cantor, nous les appellerons respectivement « ensembles » et
« classes » quand nous sommes dans un contexte portant sur l'étude des
ensembles $X \in 2^N$ ou des classes $\mathcal{A} \subseteq 2^N$.

Les classes que nous considérerons seront définies par des prédicats, et
l'étude de la complexité de ces prédicats permettra de déduire des infor-
mations sur les éléments que la classe contient.

L'étude des classes va rapidement se montrer centrale dans l'étude des ensembles d'entiers. On commence ici par les classes de la complexité la plus simple possible : les ouverts et fermés effectifs du Cantor. L'étude de classes de complexité supérieure sera poursuivie dans le chapitre 17. Malgré la simplicité apparente des ouverts et fermés, nous verrons rapidement le large éventail de possibilités et la grande richesse qu'ils renferment.
<figure><img src="image_58.png" /><figcaption>FIGURE 1.2 – Illustration d'un arbre. La racine $\epsilon$ est la chaîne vide. Chaque nœud admet éventuellement un successeur gauche, un successeur droit, les deux — auquel cas il est branchant — ou aucun des deux — auquel cas c'est une feuille.</figcaption></figure>

# 1. Arbres binaires

Nous avons défini la notion de f-arbre afin de montrer l'existence d'un degré calculatoirement dominé non calculable (le théorème 7-5.6). Nous introduisons ici une notion similaire et d'une certaine manière plus primitive, à savoir tout simplement les arbres.

**Définition 1.1.** Un ensemble $T \subseteq 2^{<N}$ est un arbre si $T$ est clos par préfixe, c'est-à-dire pour tous $\sigma \in T$ et $\tau \le \sigma$, alors $\tau \in T$. $\diamond$

Étant donné un arbre $T \subseteq 2^{<N}$, on appelle un élément $\sigma \in T$ un nœud de l'arbre. Un nœud est *branchant* si $\sigma_0, \sigma_1 \in T$. Dans le cas inverse, il est *non branchant*. On considérera par une sorte de convention sur la représentation mentale que l'on peut avoir d'un arbre, qu'une extension $\sigma_0$ de $\sigma$ << va à gauche dans l'arbre >> alors qu'une extension $\sigma_1$ de $\sigma$ << va à droite >>. Si $\sigma_0 \in T$, alors $\sigma_0$ est un *successeur gauche* de $\sigma$. Si $\sigma_1 \in T$, alors $\sigma_1$ est un *successeur droit de* $\sigma$. Un nœud sans successeur sera appelé une *feuille*.

**Définition 1.3.** Soit $T \subseteq 2^{<N}$ un arbre. Un chemin à travers l'arbre $T$ est une suite $P \in 2^N$ telle que $P|_n \in T$ pour tout $n \in N$. On dénote par $[T]$ la classe des chemins de $T$. $\diamond$
Intuitivement, un chemin *P* peut être vu comme une suite d'instructions binaires, nous indiquant littéralement « un chemin » à suivre à travers l'arbre. Un bit à 0 dans le chemin nous indique de continuer notre parcours en suivant le successeur gauche et un bit à 1 nous indique de suivre le successeur droit. Nous ne considérons que des chemins infinis.

**Remarque**

Un chemin n’est pas représenté comme un ensemble de nœuds de l’arbre. Il existe cependant une bijection calculable entre un chemin *P* et l’ensemble {$P|_n : n \in \mathbb{N}$}. Représenter un chemin comme une suite binaire infinie est donc principalement un choix conventionnel qui s’avérera très utile par la suite.

Si $T$ est un arbre fini, c'est-à-dire qui n'a qu'un nombre fini de nœuds, alors $[T]$ est forcément l'ensemble vide. Qu'en est-il de la réciproque ? Il s'agit d'un outil central sur les arbres : le lemme de König, qui stipule que tout arbre infini à branchement fini admet un chemin infini. Notez que les arbres $T \subseteq 2^{<N}$ sont nécessairement 2-branchants. On a affaire dans ce cas au lemme de König faible.

**Lemme 1.4 (Lemme de König faible).** Soit $T \subseteq 2^{<N}$ un arbre tel que $|T| = \infty$. Alors, $[T]$ est non vide. ★

PREUVE. On construit un chemin $X$ par récurrence sur $n$. Comme $T$ est infini, par le principe des tiroirs il existe $i \in \{0,1\}$ et une infinité de nœuds $\sigma \in T$ qui étendent $i$ (c'est-à-dire avec $i \prec \sigma$). On définit $X(0) = i$. Supposons que $\tau = X(0)X(1)\dots X(n)$ soit défini avec $\tau \in T$ et tel qu'il y a une infinité de nœuds $\sigma \in T$ pour lesquels $\tau \le \sigma$. Par le principe des tiroirs, il existe $i \in \{0,1\}$ et une infinité de nœuds $\sigma \in T$ qui étendent $\tau i$. On définit $X(n+1) = i$.

Par récurrence sur $n$, on définit donc de cette manière un ensemble $X$ tel que $X|_n \in T$ pour tout $n$. ■

Le lemme de König peut paraître trivial au premier abord. Le lecteur, à l'intuition bien affûtée et à l'aise avec la manipulation d'objets infinis, se sera éventuellement demandé s'il y avait vraiment besoin de ranger cet énoncé dans un lemme. Nous allons voir que malgré les apparences, ce lemme n'est pas aussi trivial que cela. Bien que simple, il constitue un outil central, particulièrement intéressant de par son contenu calculatoire.
## 1.1. Arbres calculables

Un arbre $T \subseteq 2^{<N}$ est calculable si l'ensemble $T$ est calculable, autrement dit s'il existe une procédure pour décider si un nœud appartient à l'arbre ou non. Au cours de ce chapitre, nous allons tenter de répondre à la question suivante.

**Question 1.5.** Étant donné un arbre calculable infini, quelle est la puis-
sance de calcul nécessaire pour calculer un chemin infini de $T$ ? ★

La preuve du lemme de König fournit une construction claire : quand on a calculé un préfixe $\tau$ de notre chemin infini, on détermine le prochain bit comme étant 0 si l'arbre contient une infinité de nœuds qui étendent $\tau 0$ et comme étant 1 sinon. Le problème est qu'il n'est $a priori$ pas possible de savoir de manière calculable si une infinité de nœuds étendent $\tau 0$ : c'est une question pour laquelle l'arrêt des programmes informatiques semble nécessaire. Cela nous conduit à définir la notion de nœud extensible.

**Définition 1.6.** Un nœud $\sigma$ d'un arbre $T \subseteq 2^{<N}$ est *extensible* dans $T$ si l'ensemble $\{\tau \in T : \tau \supseteq \sigma\}$ est infini. ♢

Autrement dit, un nœud $\sigma$ est extensible dans un arbre si le sous-arbre des nœuds compatibles avec $\sigma$ est infini. Souvenons-nous de la notation $[\sigma]$ qui dénote la classe des ensembles $X$ ayant $\sigma$ comme préfixe. Par le lemme de König, un nœud $\sigma$ est extensible dans $T$ si et seulement si $[\sigma] \cap [T] \neq \emptyset$. Notons que dans tout arbre infini, la racine $\epsilon$ est un nœud extensible, et que si $\sigma$ est extensible, alors au moins un nœud parmi $\sigma 0$ et $\sigma 1$ l'est également. L'exercice suivant montre que les nœuds extensibles sont suffisants pour décrire l'ensemble des chemins d'un arbre.

**Exercice 1.7.** Soit $T \subseteq 2^{<N}$ un arbre, et soit $S$ l'ensemble des nœuds extensibles dans $T$. Montrer que $S$ est un arbre, et que $[T] = [S]$. ◇

Il s'ensuit de la définition de nœud extensible que les feuilles ne sont pas extensibles. En revanche, si l'ensemble des feuilles d'un arbre calculable est décidable, ce n'est pas en général le cas de l'ensemble des nœuds extensibles.

**Exercice 1.8.** Soit $T \subseteq 2^{<N}$ un arbre calculable infini ne contenant que des nœuds extensibles. Montrer alors que $T$ contient un chemin infini calculable. ◇

De manière générale, déterminer si un ensemble calculable est infini ou non demande l'oracle $\emptyset''$. Dans le cas des arbres, nous pouvons exploiter la clôture par préfixe, pour ramener la complexité de l'oracle à $\emptyset'$. La notation $2^n$ de la proposition suivante désigne l'ensemble des chaînes de taille $n$.
**Proposition 1.9.** Soit $T \subseteq 2^{<N}$ un arbre calculable. L'ensemble de ses nœuds extensibles est $\Pi_1^0$.

PREUVE. Les arbres étant clos par le bas, $\{\tau \in T : \tau \succeq \sigma\}$ est infini ssi $\forall n > |\sigma| \exists \tau \in 2^n$ tel que $\tau \succeq \sigma$ et $\tau \in T$, ce qui est un prédicat $\Pi_1^0$. Ainsi, l'ensemble des nœuds extensibles de $T$ est l'ensemble $\Pi_1^0$ suivant.

$$ \{\sigma \in T : \forall n > |\sigma| \exists \tau \in 2^n \text{ tel que } \tau \succeq \sigma \text{ et } \tau \in T\} $$

■

Par passage au complémentaire, l'ensemble des nœuds non extensibles d'un arbre calculable est $\Sigma_1^0$, ce qui fait que si un nœud est non extensible, on finira par s'en rendre compte au bout d'un temps fini. Nous allons voir comment utiliser la notion de nœud extensible pour créer des arbres calculables infinis n'ayant pas de chemin calculable. Dans la construction d'un arbre calculable, on doit pouvoir décider en un temps fini si un nœud y appartient ou non. Il est en revanche possible de reporter à plus tard la décision de rendre ou non un nœud extensible, en lui ajoutant par défaut des descendants au cours du temps, jusqu'à décider à un instant $t$ de cesser de lui en rajouter pour le rendre non extensible. Cette technique que l'on appelle « l'astuce du temps » permet de montrer le résultat suivant.

**Proposition 1.10.** Soit $T \subseteq 2^{<N}$ un arbre $\Pi_1^0$. Il existe un arbre calculable $S \subseteq 2^{<N}$ tel que $[T] = [S]$.

★

PREUVE. Soit $(T_n)_{n \in N}$ une approximation $\Pi_1^0$ de $T$, c'est-à-dire une suite uniformément calculable d'ensembles décroissante par la relation d'inclusion (avec $T_{n+1} \subseteq T_n$) telle que $\bigcap_n T_n = T$.

Soit $S = \{\sigma \in 2^{<N} : \forall \tau \preceq \sigma \tau \in T_{|\sigma|}\}$. L'ensemble $S$ est calculable. Montrons que $S$ est clos par préfixe. Soit $\sigma \in S$, et soit $\rho \preceq \sigma$. Par définition de $S$, $\forall \tau \preceq \sigma \tau \in T_{|\sigma|}$. Comme $|\rho| \le |\sigma|$, $T_{|\rho|} \supseteq T_{|\sigma|}$, donc $\forall \tau \preceq \sigma \tau \in T_{|\rho|}$. En particulier, pour tout $\tau \preceq \rho$, également $\tau \preceq \sigma$, donc $\tau \in T_{|\rho|}$. Ainsi, par définition de $S$, $\rho \in S$.

Montrons maintenant que $[S] = [T]$. Nous avons $P \in [S]$ ssi $\forall \sigma \prec P \sigma \in S$ ssi $\forall \sigma \prec P \forall \tau \preceq \sigma \tau \in T_{|\sigma|}$ ssi $\forall \tau \prec P \forall n \ge |\tau| \tau \in T_n$ ssi $\forall \sigma \prec P \sigma \in T$ ssi $P \in [T]$.

■

Ce chapitre porte principalement sur l'étude des classes d'ensembles correspondant aux chemins d'arbres calculables. Nous verrons avec la proposition 3.5 qu'il existe des arbres calculables infinis ne contenant aucun chemin calculable infini, puis nous déterminerons la puissance de calcul exacte qui est nécessaire au calcul d'un chemin dans n'importe quel arbre calculable infini. Cette étude constitue une des briques de base des mathématiques à rebours, que nous verrons dans la partie III.
## 2. Topologie sur l'espace de Cantor

La topologie est une branche des mathématiques qui formalise de manière abstraite les notions de limite et de continuité, et qui par extension étudie les propriétés d'objets géométriques invariantes par déformation continue. Le lecteur qui n'a jamais étudié cette branche peut se rassurer : nous n'avons besoin pour le développement des chapitres à venir que d'éléments très basiques de cette théorie, que nous présentons ici.

**Notation**

On notera $i^\infty$ la suite infinie qui répète le bit $i \in \{0, 1\}$.

### 2.1. Ouverts et fermés

Comme nous l'avons déjà mentionné, l'espace de Cantor $2^N$ est similaire à l'ensemble des réels de l'intervalle $[0, 1]$. Un élément $X \in 2^N$ peut aussi être vu comme le développement binaire du réel $0.X(0)X(1)X(2)\dots$, avec toutefois une différence subtile : les éléments $\sigma 10^\infty$ et $\sigma 01^\infty$ sont deux éléments distincts de $2^N$ mais correspondent au même réel. Cette différence mise à part, on peut voir $2^N$ comme un intervalle, et les sous-ensembles les plus simples de $2^N$ seront simplement les intervalles de la forme $[\sigma]$, que l'on appellera aussi *cylindre*.

**Notation**

Étant donné une chaîne $\sigma \in 2^{<N}$, on écrit $[\sigma]$ pour l'ensemble

$$ \{X \in 2^N : X \supseteq \sigma\}. $$

On appellera *cylindre* un ensemble de la forme $[\sigma]$.

Étant donné une chaîne $\sigma \in 2^{<N}$, on peut voir $[\sigma]$ comme un intervalle de suites binaires infinies : celles qui sont lexicographiquement comprises entre $\sigma 0^\infty$ et $\sigma 1^\infty$. Avec cette vision en tête, les classes dites *ouvertes* du Cantor sont simplement les réunions quelconques d'intervalles.

**Définition 2.1.** Les classes *ouvertes* du Cantor $2^N$ sont les réunions quelconques de cylindres, c'est-à-dire les ensembles de la forme $\bigcup_{\sigma \in W}[\sigma]$ pour un ensemble $W \subseteq 2^{<N}$. Les classes *fermées* sont les complémentaires des classes ouvertes. ◇

Le lecteur non habitué à ces concepts pourra, pour se faire la main, démontrer sur les définitions que les réunions finies de cylindres sont à la fois des ouverts et des fermés.
**Notation**

Étant donné un ensemble $W \subseteq 2^{<N}$, on écrira $[W]$ pour dénoter son
ouvert correspondant, c'est-à-dire la classe $\bigcup_{\sigma \in W}[\sigma]$.

Il est clair d'après la définition que les ouverts sont clos par réunion quel-
conque, et donc par passage au complémentaire que les fermés sont clos
par intersection quelconque. Nous introduisons ci-après un élément de vo-
cabulaire qui reviendra souvent dans la manipulation des ouverts et des
fermés.

**Notation**

Étant donné une réunion dénombrable d'ensembles $\bigcup_n \mathcal{B}_n$, on dira que la réunion est *croissante* si $\mathcal{B}_n \subseteq \mathcal{B}_{n+1}$ pour tout $n$. De la même manière, on dira qu'une intersection $\bigcap_n \mathcal{B}_n$ est *décroissante* si $\mathcal{B}_{n+1} \subseteq \mathcal{B}_n$ pour tout $n$.

La représentation mentale d'un ensemble ouvert devrait être à peu près
claire pour le lecteur : les réunions de briques simples que sont les cylindres.
Voici un exemple illustratif.

<figure><img src="image_59.png" /><figcaption>FIGURE 2.2 – *Illustration de l'ouvert* [01] ∪ [101] ∪ [1101] ∪ [11101] ∪ ...</figcaption></figure>

Nous montrons à présent que l'on peut considérer sans perte de généralité que les intersections d'ouverts sont décroissantes et les réunions de fermés croissantes (en particulier, car $\bigcap_n U_n = \bigcap_n (\bigcap_{m \le n} U_m)$ :

**Proposition 2.3.** Une intersection finie d'ouverts est un ouvert. Par passage au complémentaire, une réunion finie de fermés est fermée. ★

PREUVE. Soient $U_0, U_1 \subseteq 2^N$ deux classes ouvertes. Un ensemble $X$ appartient à $U_0 \cap U_1$ ssi il appartient à un cylindre $[\sigma_0] \subseteq U_0$ ainsi qu'à un cylindre $[\sigma_1] \subseteq U_1$. Donc, $U_0 \cap U_1 = \bigcup_{[\sigma_0] \subseteq U_0, [\sigma_1] \subseteq U_1} [\sigma_0] \cap [\sigma_1]$. $\blacksquare$

Les ensembles fermés s'avèrent plus délicats à décrire. Cela n'est pas forcément surprenant. En guise d'analogie, disons que l'on peut bien connaître son quartier, sans avoir une idée précise du reste du monde. La prise de conscience de cette complexité et la manière de l'appréhender figurent déjà dans les travaux de Cantor, par exemple au travers du fameux théorème de Cantor-Bendixson. Il existe toutefois une manière simple de représenter les fermés de $2^N$: en tant que chemins infinis d'un arbre.
**Proposition 2.4.** Une classe $\mathcal{P} \subseteq 2^\mathbb{N}$ est fermée si, et seulement si, il existe un arbre $T \subseteq 2^{<\mathbb{N}}$ tel que $\mathcal{P} = [T]$. ★

PREUVE. Soit $\mathcal{P}$ une classe fermée, et soit $\mathcal{U} = \bigcup_{\sigma \in W}[\sigma]$ son complémentaire, avec $W \subseteq 2^{<\mathbb{N}}$. On définit l'arbre $T \subseteq 2^{<\mathbb{N}}$ comme étant l'ensemble des chaînes $\sigma$ n'ayant aucun préfixe dans $W$. Par définition, $T$ est clos par préfixe, et est donc un arbre. Montrons $[T] = \mathcal{P}$. On a $X \in [T]$ ssi aucun préfixe $\sigma \prec X$ n'est dans $W$ ssi $X \notin \bigcup_{\sigma \in W}[\sigma]$ ssi $X \in \mathcal{P}$. Donc, $[T] = \mathcal{P}$.
Inversement, si $T \subseteq 2^{<\mathbb{N}}$ est un arbre, la classe $[T]$ de ses chemins est un fermé, car elle est le complémentaire de la classe $\bigcup_{\sigma \notin T}[\sigma]$. ■

À titre d'exemple, le lecteur peut consulter la figure 2.5, où se trouve l'arbre qui représente le complémentaire de l'ouvert décrit dans la figure 2.2.

<figure><img src="image_60.png" /><figcaption>FIGURE 2.5 – Illustration de l'arbre représentant le complémentaire dans $2^\mathbb{N}$ de l'ouvert</figcaption></figure>

[01] $\cup$ [101] $\cup$ [1101] $\cup$ [11101] $\cup \dots$

Les nœuds en gras correspondent aux cylindres constituant les briques de base de l'ouvert. Les triangles représentent un sous-arbre $\prec$ plein $\succ$ à partir du nœud où ils se trouvent.

## 2.2. Compacité

La *compacité* est une notion fondamentale de topologie. Elle est généralement définie via la propriété de Borel-Lebesgue, qui dans l'espace de Cantor se formule comme suit.

**Définition 2.6.** Une classe $\mathcal{P} \subseteq 2^\mathbb{N}$ a la propriété de Borel-Lebesgue $^a$ si pour toute collection d'ouverts $(O_n)_{n \in \mathbb{N}}$ telle que $\mathcal{P} \subseteq \bigcup_n O_n$, il existe un ensemble fini $F \subseteq \mathbb{N}$ tel que $\mathcal{P} \subseteq \bigcup_{n \in F} O_n$. On dira qu'une classe
possédant la propriété de Borel-Lebesgue est *compacte*.

a. Appelée aussi << propriété de Heine-Borel >>.

Nous montrons avec la proposition suivante que dans l'espace de Cantor, les classes compactes sont exactement les fermés, et le lecteur pourra constater en lisant la preuve que le lemme de König faible peut être vu comme une reformulation du fait que les classes fermées sont compactes.

**Proposition 2.7.** Une classe de $2^N$ est fermée si, et seulement si, elle a la propriété de Borel-Lebesgue. ★

PREUVE. Soit $\mathcal{P} \subseteq 2^N$ un fermé, et soit $(\mathcal{O}_n)_{n \in \mathbb{N}}$ une collection d'ouverts telle que $\mathcal{P} \subseteq \bigcup_n \mathcal{O}_n$, et soit $T \subseteq 2^N$ un arbre tel que $[T] = \mathcal{P}$. Soit $S \subseteq 2^N$ l'arbre des chaînes $\sigma \in T$ telles que $[\sigma] \not\subseteq \bigcup_{n<|\sigma|} \mathcal{O}_n$. Si l'arbre $S$ est fini, il existe une longueur $\ell$ telle que pour tout $\sigma \in T$ tel que $|\sigma| = \ell$,

$$[\sigma] \subseteq \bigcup_{n<\ell} \mathcal{O}_n.$$

Il s'ensuit que $[T] \subseteq \bigcup_{\sigma \in T, |\sigma|=\ell} [\sigma] \subseteq \bigcup_{n<\ell} \mathcal{O}_n$. Si $S$ est infini, par le lemme faible de König, $[S] \neq \emptyset$. Soit $P \in [S]$. Montrons que $P \notin \bigcup_n \mathcal{O}_n$ pour en déduire une contradiction, car $[S] \subseteq [T] \subseteq \bigcup_n \mathcal{O}_n$. Soit $i \in \mathbb{N}$. Par définition de $[S]$, pour tout $\ell$, on a $P \upharpoonright_{\ell} \in S$, et donc par définition de $S$ on a $[P \upharpoonright_{\ell}] \not\subseteq \bigcup_{n<\ell} \mathcal{O}_n$; en particulier, pour tout $\ell > i$, $[P \upharpoonright_{\ell}] \not\subseteq \mathcal{O}_i$. Comme $\mathcal{O}_i$ est un ouvert, il s'ensuit que $P \notin \mathcal{O}_i$.

Supposons à présent qu'une classe $\mathcal{B}$ admette la propriété de Borel-Lebesgue. Pour tout $X \notin \mathcal{B}$, soit $\mathcal{O}_X$ l'ouvert correspondant au complémentaire de la classe $\{X\}$ (il s'agit de la réunion des cylindres $[\sigma i]$ pour toute chaîne $\sigma$ et tout $i$ tel que $X(|\sigma|) \neq i$). En particulier, on a $\mathcal{B} = \bigcap_{X \notin \mathcal{B}} \mathcal{O}_X$. Notons que chaque $\mathcal{O}_X$ est une réunion de cylindres et que chaque cylindre est ouvert. Donc, par la propriété de Borel-Lebesgue, on peut trouver pour tout $X$ un ensemble fini de cylindres $F_X$ tel que $\mathcal{B} \subseteq \bigcup_{\sigma \in F_X} [\sigma] \subseteq \mathcal{O}_X$. En particulier, $\mathcal{B} = \bigcap_{X \notin \mathcal{B}} \bigcup_{\sigma \in F_X} [\sigma]$. Chaque réunion $\bigcup_{\sigma \in F_X} [\sigma]$ est une classe fermée en tant que réunion finie de cylindres. Comme une intersection arbitraire de fermés est une classe fermée, on en déduit que $\mathcal{B}$ est une classe fermée. ■

En pratique, nous utiliserons la conséquence suivante de la compacité : toute intersection dénombrable et décroissante de fermés non vides, est non vide, ce que nous démontrons ici.

**Proposition 2.8.** Soit $\mathcal{P}_0 \supseteq \mathcal{P}_1 \supseteq \dots$ une suite décroissante de fermés non vides. Alors $\bigcap_n \mathcal{P}_n$ est non vide. ★