une restreinte sur l'usage de son calcul lorsque celle-ci passe à l'état *t* et se termine, elle blesse toutes les stratégies qui n'ont pas encore atteint l'état *t*, et les fait revenir dans l'état *i*. Les stratégies ainsi blessées vont alors choisir de nouveaux éléments en dehors de toute restreinte. Notons que lorsqu'une stratégie entre dans l'état *t*, elle n'en sort plus. Les blessures étant causées uniquement par l'entrée d'une stratégie arrivant dans l'état *t*, chaque stratégie n'est blessée qu'un nombre fini de fois, et finira par entrer dans l'état *t*, ou restera bloquée dans l'état *e*.

**Satisfaction de tous les contrats** ($\mathcal{R}_e)_{e \in \mathbb{N}}$ et ($S_e)_{e \in \mathbb{N}}$. Un nouveau problème se pose lorsque l'on veut satisfaire une infinité de contrats ($\mathcal{R}_e)_{e \in \mathbb{N}}$ et ($S_e)_{e \in \mathbb{N}}$. Supposons que la stratégie pour $\mathcal{R}_e$ choisisse dans son état *i* un entier $x_{\mathcal{R}_e}$ et se lance dans l'exécution de $\Phi_e^A(x_{\mathcal{R}_e})$, mais n'a pas le temps d'atteindre la fin de l'exécution, car la stratégie pour un contrat $S_{d_0}$ voit sa propre exécution se terminer avant elle et pose une restreinte sur $x_{\mathcal{R}_e}$ pour préserver l'usage de son calcul. La stratégie pour $\mathcal{R}_e$ est alors blessée, et se retrouve à nouveau dans l'état *i* et choisis un nouvel entier $x_{\mathcal{R}_e}$ et re-commence l'exécution de $\Phi_e^A(x_{\mathcal{R}_e})$ pour son nouvel $x_{\mathcal{R}_e}$. Avant d'atteindre la fin de son calcul, par manque de chance, une autre stratégie $S_{d_1}$ atteint l'état *t*, et blesse encore la stratégie pour $\mathcal{R}_e$, et ainsi de suite à l'infini. La stratégie pour $\mathcal{R}_e$ changera alors infiniment souvent d'entier $x_{\mathcal{R}_e}$, et le contrat $\mathcal{R}_e$ ne sera jamais satisfait.

Pour résoudre ce problème, nous allons ordonner les stratégies. Soient $R_e$ la stratégie pour $\mathcal{R}_e$ et $S_e$ la stratégie pour $S_e$. On ordonne les stratégies comme suit :

$$R_0, S_0, R_1, S_1, R_2, S_2, \dots$$

en considérant qu'une stratégie est moins prioritaire que les stratégies à sa gauche, mais plus prioritaire que celles à sa droite. Par exemple, la stratégie pour $S_1$ est moins prioritaire que les stratégies pour $\mathcal{R}_0$ et $S_0$, mais plus prioritaire que les stratégies pour $\mathcal{R}_2, S_2$, et ainsi de suite. De la sorte, chaque stratégie est « en dessous » d'un nombre fini de stratégies, et « au-dessus » du reste.

**Remarque**

Dans la preuve du théorème de Friedberg et Muchnik, chaque contrat possède exactement une stratégie, ce qui rend le distinguo entre stratégie $R_e$ et contrat $\mathcal{R}_e$ inutile. L'ordre donné sur les stratégies induit ainsi un ordre sur les contrats. Cependant, dans les constructions suivantes, lorsque les contrats se verront attribuer plusieurs stratégies, il sera essentiel de donner un ordre total de priorité sur les stratégies et non sur les contrats.
La règle d'or que l'on établit est alors la suivante.

Les restreintes posées par une stratégie ne s'appliquent qu'aux stratégies de plus faible priorité. Ainsi, une stratégie ne peut être blessée que par les stratégies de plus forte priorité, et peut blesser toutes les stratégies de plus faible priorité.

En supposant qu'une stratégie ne pose qu'un nombre fini de restreintes avant d'atteindre son état terminal, et cesse d'agir au bout d'un moment si elle n'est pas blessée, une simple induction montre que chaque stratégie n'est blessée qu'un nombre fini de fois. Contrairement à la satisfaction d'un nombre fini de contrats simultanément, il se peut qu'un processus arrive à l'état $t$, mais soit ensuite blessé par une stratégie de plus forte priorité qui aura ignoré la restreinte posée. Heureusement, au bout d'un moment, la stratégie de plus forte priorité cessera de blesser la plus faible, qui finira par se stabiliser.

**Construction.** Formellement, la construction se fait par étapes $t=0,1,...$, et chaque étape est divisée en sous-étapes $s < t$. Initialement, toutes les stratégies sont dans l'état $i$. À l'étape $t \ge 0$ et la sous-étape $s < t$, on considère le contrat $R_e$ si $s = 2e$ et $S_e$ si $s = 2e + 1$.

Au début de la sous-étape $s = 2e$, la stratégie pour $R_e$ a les trois états possibles suivants.

(i) La stratégie choisit un entier $x_{R_e} \notin B_t$ qui n'a pas été restreint par une stratégie de plus grande priorité, et pose une restreinte dessus. Elle se retrouve alors dans l'état $e$.

(e) La stratégie exécute $\Phi_e^{A_t}(x_{R_e})[t]$. Si $\Phi_e^{A_t}(x_{R_e})[t] \downarrow$, alors elle pose une restreinte sur tous les bits ayant servi au calcul de $\Phi_s^{A_t}(x_{R_e})[t]$, et blesse toutes les stratégies de plus faible priorité en les faisant retourner à l'état $i$. Elle se retrouve alors dans l'état $t$. Si $\Phi_e^{A_t}(x_{R_e})[t] \uparrow$, la stratégie reste dans l'état $e$.

(t) La stratégie n'agit pas et reste dans cet état.

À la sous-étape $s = 2e+1$, on applique la même procédure pour $S_e$ mutatis mutandis, puis on passe à la sous-étape suivante, jusqu'à atteindre $t$, auquel cas on passe à l'étape $t+1$, et ainsi de suite.

Cela conclut la construction.
<figure><img src="image_91.png" /></figure>

**Vérification.** Tout d'abord, remarquons que la construction décrite plus haut est bien un processus calculable qui énumère deux ensembles A et B. En particulier, une fois un élément énuméré dans A ou B, on ne change pas d'avis et il y reste. Remarquons aussi que si une stratégie pour un contrat n'est plus blessée après une étape *r*, alors le contrat associé sera satisfait passivement ou activement à la fin de la construction. La difficulté réside dans le fait de montrer que pour tout contrat il existe bien un tel *r*.

Montrons par induction sur $e \in \mathbb{N}$ que les stratégies pour les contrats $R_e$ et $S_e$ blessent finiment souvent des stratégies de priorité inférieure. Supposons par hypothèse d'induction qu'il existe une étape $t$ après laquelle aucune des stratégies pour les contrats $R_d$ et $S_d$, avec $d < e$, ne blessent des stratégies de priorité inférieure. En particulier, à partir de l'étape $t$, la stratégie pour $R_e$ ne sera plus blessée, et soit reste désormais dans l'état d'exécution (état $e$), soit passe au bout d'un moment dans l'état de terminaison (état $t$) en ne blessant plus qu'une dernière fois les stratégies de priorité inférieure. Le même raisonnement s'applique à la stratégie pour le contrat $S_e$. Ainsi, chaque stratégie blesse finiment souvent les stratégies de priorité inférieure, et chaque contrat finira par être satisfait, passivement ou activement. Cela conclut la preuve du théorème 3.1. ■

**Remarque**

La preuve précédente était très détaillée afin de donner les intuitions de la méthode de priorité. Nous irons désormais plus directement vers la construction finale dans les autres preuves. Il est cependant souvent utile, lorsque l'on cherche à prouver un nouveau résultat à l'aide de la méthode de priorité, de procéder étapes par étapes, en cherchant à satisfaire un contrat, puis plusieurs simultanément, pour finir par les satisfaire tous, afin de mieux comprendre leurs interactions.
**Corollaire 3.2**

Il existe un ensemble c. e. A incalculable tel que $A \not\subset_T \emptyset'$.

PREUVE. Soient $A$ et $B$ deux ensembles c. e. tels qu'aucun des deux ne calcule l'autre. Alors, ils sont en particulier tous les deux incalculables. Par ailleurs, si $A$ pouvait calculer l'arrêt, il calculerait aussi $B$ du fait que tout ensemble c. e. est many-one réductible à l'arrêt. ■

Avant de nous attaquer à des constructions plus élaborées, se basant sur la technique des méthodes de priorités à blessure finie de Friedberg et Muchnik, nous en voyons ici une autre application simple.

**Théorème 3.3**

Il existe un ensemble c. e. incalculable de degré low.

PREUVE. Nous allons construire un ensemble c. e. $A$ par la méthode de priorité à blessure finie, ainsi qu'une fonction $\Gamma: \mathbb{N} \times \mathbb{N} \to \{0,1\}$ totale calculable stable satisfaisant les contrats $(\mathcal{R}_e)_{e \in \mathbb{N}}$ et $(S_e)_{e \in \mathbb{N}}$ :

$$ \mathcal{R}_e : W_e \neq \bar{A} \qquad S_e : A'(e) = \lim_{t} \Gamma(e, t). $$

Satisfaire tous les contrats $(\mathcal{R}_e)_{e \in \mathbb{N}}$ assure que l'ensemble $A$ n'est pas calculable, tandis que les contrats $(S_e)_{e \in \mathbb{N}}$ font en sorte que $A'$ (le problème de l'arrêt relativement à $A$) admet une approximation $\Delta_2^0$, ce qui, par le lemme de limite de Shoenfield (voir le lemme 4-7.2), assure que $A' \le_T \emptyset'$, et donc que $A$ est de degré low.

**Satisfaction d'un contrat** $\mathcal{R}_e$. Voici une stratégie pour satisfaire un contrat $\mathcal{R}_e$, indépendamment des autres contrats. Notre stratégie a trois états : initial (i), en exécution (e) et terminée (t). La stratégie suit les étapes suivantes en fonction de son état.

▷ État i. Choisir un entier $x_{\mathcal{R}_e} \notin A$, et poser une restreinte sur $x_{\mathcal{R}_e}$.

▷ État e. Exécuter $\Phi_e(x_{\mathcal{R}_e})$. Si l'exécution s'arrête à l'instant $t$, ajouter $x_{\mathcal{R}_e}$ à $A$, puis passer dans l'état $t$.

▷ État t. Le processus a terminé son exécution et reste dans cet état.

En supposant que la stratégie n'est blessée qu'un nombre fini de fois, elle pourra avoir deux issues possibles. Issue p : elle finira par rester dans l'état e, auquel cas, $\Phi_e(x_{\mathcal{R}_e}) \uparrow$ et $x_{\mathcal{R}_e} \notin A$, donc $W_e \neq \bar{A}$. Dans ce cas, le contrat $\mathcal{R}_e$ est dit satisfait passivement. Issue a : la stratégie atteindra l'état t, et s'arrêtera. Dans ce cas, $\Phi_e(x_{\mathcal{R}_e}) \downarrow$, $x_{\mathcal{R}_e} \in A$, et $\mathcal{R}_e$ est dit satisfait activement.
**Satisfaction d'un contrat** $S_e$. À l'étape $t$, nous allons définir la valeur de $\Gamma(x,t)$ pour tout $x < t$. La stratégie comporte deux états : en exécution (e) et terminée (t). Voici la démarche à suivre en fonction de chaque état de la stratégie.

▷ État e. Exécuter $\Phi_e^A(e)$. Tant que $\Phi_e^{A_t}(e)[t] \uparrow$, maintenir $\Gamma(e,t) = 0$. Si l'exécution s'arrête à l'instant $t$, restreindre l'usage de $\Phi_e^A(e)$ puis passer dans l'état t.

▷ État t. Définir $\Gamma(e,t) = 1$ désormais pour toute nouvelle étape t.

Les deux issues possibles de la stratégie sont les suivantes. Issue **p** : elle finira par rester dans l'état **e** d'exécution, auquel cas $\Phi_e^A(e) \uparrow$ et $\lim_t \Gamma(e,t) = 0$. Ainsi, $A'(e) = 0 = \lim_t \Gamma(e,t)$. Dans ce cas, le contrat $S_e$ est dit satisfait passivement. Issue **a** : la stratégie atteindra l'état **t**, et s'arrêtera. Dans ce cas, $\Phi_e^A(e) \downarrow$ et $\lim_t \Gamma(e,t) = 1$. Donc, $A'(e) = 1 = \lim_t \Gamma(e,t)$, et $S_e$ est dit satisfait activement.

**Construction.** La construction est globalement la même que celle du théorème 3.1. Les stratégies sont ordonnées $R_0, S_0, R_1, S_1, \dots$, par priorité décroissante. La construction se divise en étapes $t = 0, 1, \dots$ et chaque étape est elle-même divisée en sous-étapes $s < t$. Initialement, toutes les stratégies sont dans l'état **i**. À l'étape $t \ge 0$ et la sous-étape $s < t$, on considère le contrat $R_e$ si $s = 2e$ et $S_e$ si $s = 2e+1$. À la sous-étape $s = 2e$, on exécute la stratégie pour $R_e$ comme décrit ci-dessus en fonction de son état. Lorsqu'elle atteint l'état **t**, toutes les stratégies de priorité inférieure sont blessées et reviennent soit dans l'état **i** dans le cas des stratégies pour des contrats de type $R$, soit dans l'état **e** dans le cas des stratégies pour des contrats de type $S$. De la même manière, à la sous-étape $s = 2e+1$, on exécute la stratégie $S_e$ comme décrit ci-dessus, en blessant toutes les stratégies de priorité inférieure si l'on arrive à l'état de terminaison **t**.

**Vérification.** L'ensemble $\mathcal{A}$ produit est bien c. e., car le processus est calculable, et ne retire aucun élément de $\mathcal{A}$ une fois ajouté. On prouve aisément par induction sur $e \in \mathbb{N}$ que les stratégies pour les contrats $R_e$ et $S_e$ blessent finiment souvent des stratégies de priorité inférieure. Ainsi, chaque stratégie n'est blessée que finiment souvent, et finira par avoir un comportement limité. Il s'ensuit également que $\lim_t \Gamma(e,t)$ existe et est, par construction, égale à $A'(e)$. Cela conclut la preuve du théorème 3.3. ■

## 4. Méthode de priorité $\Sigma_2^0$

Dans les constructions précédentes à l'aide de la méthode de priorité, les blessures finies sont assurées de manière structurelle, c'est-à-dire que dans la structure même de la construction, les stratégies ne posent qu'un nombre
fini de restreintes lorsqu'elles ne sont pas blessées, et sont assurées par construction de n'être blessées qu'un nombre fini de fois. Le nombre de blessures peut même être borné calculatoirement : dans la construction de Friedberg et Muchnik, le *e*-ième processus est blessé au plus $2^e - 1$ fois.

Nous allons maintenant voir une élaboration de la méthode précédente, qui pourrait structurellement résulter en un nombre infini de blessures sur des stratégies, mais des hypothèses sur la construction vont assurer que cette situation n'arrive jamais. Techniquement, il s'agit donc d'une méthode de priorité à blessure finie, car chaque stratégie ne sera blessée qu'un nombre fini de fois. Cependant, cette élaboration peut être vue comme une version dégénérée de la méthode de priorité à blessure infinie, présentée dans la section suivante.

**Théorème 4.1 (Sacks)**

Pour tout ensemble c. e. incalculable B, il existe ensemble c. e. incalculable A qui ne calcule pas B.

PREUVE. Nous allons construire un ensemble c. e. A satisfaisant les contrats $(\mathcal{R}_e)_{e \in \mathbb{N}}$ et $(S_e)_{e \in \mathbb{N}}$ suivants :

$$ \mathcal{R}_e : W_e \neq \bar{A} \qquad S_e : \Phi_e^A = B \Rightarrow B \text{ est calculable.} $$

Satisfaire tous les contrats $(\mathcal{R}_e)_{e \in \mathbb{N}}$ assure que l'ensemble A n'est pas calculable, tandis que les contrats $(S_e)_{e \in \mathbb{N}}$ font en sorte que $B \not\subset_T A$. Le contrat $S_e$ aurait également pu être noté $W_e^A \neq \bar{B}$, mais sa formulation actuelle représente mieux la forme de l'argument utilisé pour le satisfaire.

**Satisfaction d'un contrat** $\mathcal{R}_e$. La satisfaction d'un contrat $\mathcal{R}_e$ est exactement la même que pour le théorème 3.3. Nous rappelons les actions de la stratégie en fonction de ses trois états.

▷ État i. Choisir un entier $x_{\mathcal{R}_e} \notin A$, et poser une restreinte sur $x_{\mathcal{R}_e}$.

▷ État e. Exécuter $\Phi_e(x_{\mathcal{R}_e})$. Si l'exécution s'arrête à l'instant $t$, ajouter $x_{\mathcal{R}_e}$ à A, puis passer dans l'état $t$.

▷ État t. Le processus est terminé.

Les deux issues de la stratégie sont toujours p et a.

**Satisfaction d'un contrat** $S_e$. La stratégie pour satisfaire $S_e$ est plus complexe et moins intuitive. Elle consiste à essayer de faire coïncider des segments initiaux de $\Phi^A$ et de $B$ de plus en plus longs, de manière calculable, en posant chaque fois des restreintes de plus en plus grandes sur A pour préserver l'usage de $\Phi^A$. À première vue, cette stratégie va donc causer une infinité de blessures aux stratégies de priorité inférieure.
Heureusement, l'ensemble $\mathbf{B}$ n'étant pas calculable, la procédure cessera de trouver de nouveaux segments initiaux de coïncidence, et satisfera ainsi le contrat $S_e$. Plus précisément, la stratégie possède un état initial $\mathbf{i}$, et une infinité d'états ($\mathbf{w}_n$)$_{n \in \mathbb{N}}$. Pendant l'exécution du processus, nous allons définir une fonction calculable $\Delta : \mathbb{N} \to \{0, 1\}$ censée coïncider avec la fonction caractéristique de $\mathbf{B}$. Soit $(B_t)_{t \in \mathbb{N}}$ une approximation c. e. de $\mathbf{B}$.

▷ État $\mathbf{i}$. Définir $\Delta$ comme la fonction de domaine vide, et passer à l'état $\mathbf{w}_0$.

▷ État $\mathbf{w}_n$. Attendre une étape $t \ge n$, où $\Phi_e^{A_t}[t] \upharpoonright_{n+1} = B_t \upharpoonright_{n+1}$. Si cela arrive, poser alors une restreinte sur l'usage de $\Phi_e^{A_t}[t] \upharpoonright_{n+1}$, définir en-suite $\Delta(n) = B_t(n)$, et passer enfin à l'état $\mathbf{w}_{n+1}$.

Ici, $\Phi_e^{A_t}[t] \upharpoonright_{n+1} = B_t \upharpoonright_{n+1}$ signifie que pour tout $x \le n$, $\Phi_e^{A_t}(x)[t] \downarrow \in \{0, 1\}$, et $\Phi_e^{A_t}(x)[t] = 1$ ssi $x \in B_t$ pour $x \le n$. La stratégie ne retourne à l'état $\mathbf{i}$ que lorsqu'elle est blessée. À ce moment-là, la fonction $\Delta$ est également réinitialisée. Cependant, en supposant que la stratégie est blessée un nombre fini de fois, la fonction ne sera réinitialisée que finiment souvent, et sera donc définie de manière calculable.

La stratégie possède une infinité d'issues : pour tout $n$, l'issue $p_n$ consiste à rester bloqué dans l'état $\mathbf{w}_n$. Si la stratégie ne sort jamais de cet état, alors $\Phi_e^{A_t}[t] \upharpoonright_{n+1} \ne B_t \upharpoonright_{n+1}$ pour tout $t$, donc $\Phi_e^A \ne B$, et le contrat $S_e$ est satisfait, car la prémisse de l'implication est fausse. La stratégie possède une dernière issue possible, d'ordre infinitaire, qui consiste à passer par tous les états $\mathbf{w}_n$. Nommons cette issue $\infty$. En utilisant l'hypothèse selon laquelle $\mathbf{B}$ n'est pas calculable, nous allons maintenant montrer que cette issue ne peut pas arriver.

**Lemme 4.2.** Si l'issue $\infty$ arrive, alors $\mathbf{B}$ est calculable.

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

**PREUVE.** Soit $e$ le plus petit entier tel que la stratégie pour $S_e$ passe par tous les états ($\mathbf{w}_n$)$_{n \in \mathbb{N}}$. Par induction, toutes les stratégies de priorité supérieure sont finiment blessées, et atteindront un état limite où elles ne blesseront plus la stratégie pour $S_e$. À partir de ce moment, la stratégie pour $S_e$ passera par tous les états ($\mathbf{w}_n$)$_{n \in \mathbb{N}}$ successivement. La fonction $\Delta$ définie par le processus est alors totale calculable. Montrons que $\Delta$ est la fonction caractéristique de $\mathbf{B}$. Supposons par l'absurde que $\Delta(n) \ne B(n)$, pour un $n \in \mathbb{N}$. Par définition de $\Delta$, $\Delta(n) = B_t(n) = \Phi_e^{A_t}(n)$ pour un $t \in \mathbb{N}$. Comme $\mathbf{B}$ est c. e., cette différence vient d'un élément qui apparaît dans $\mathbf{B}$, car aucun élément ne peut en sortir : $\Delta(n) = B_t(n) = \Phi_e^{A_t}(n) = 0$ et $n \in \mathbf{B}$. Soit $m$ suffisamment grand tel que $n \in B_m$. Par conséquent, à l'état $\mathbf{w}_m$, $\Phi_e^{A_t}(n)[t] = 0 \ne B_t(n)$ pour tout $t \ge m$, et $\Phi_e^{A_t}[t] \upharpoonright_{n+1}$ est donc différent de $B_t \upharpoonright_{n+1}$ pour tout $t \ge m$, et la stratégie n'atteindra jamais l'état $\mathbf{w}_{m+1}$. Contradiction ! La fonction $\Delta$ est donc la fonction caractéristique de $\mathbf{B}$, ce qui prouve que $\mathbf{B}$ est calculable.

<figure><img src="image_93.png" /></figure>
**Construction.** La construction globale est celle d'une méthode de priorité à blessure finie standard. Les stratégies sont ordonnées par priorité décroissante $R_0, S_0, R_1, S_1, ...$. La construction se divise alors en étapes $t = 0, 1, ..., $, et chaque étape est elle-même divisée en sous-étapes $s < t$. Initialement, toutes les stratégies sont dans l'état **i**. À l'étape $t \ge 0$ et la sous-étape $s < t$, on considère le contrat $R_e$ si $s = 2e$, et $S_e$ si $s = 2e + 1$. À la sous-étape $s = 2e$, on exécute la stratégie pour $R_e$ comme décrite ci-dessus en fonction de son état. Lorsqu'elle atteint l'état **e**, toutes les stratégies de priorité inférieure sont blessées, et reviennent dans l'état **i**. De la même manière, à la sous-étape $s = 2e + 1$, on exécute la stratégie pour $S_e$ suivant les étapes décrites ci-dessus. Chaque fois qu'elle passe à un état suivant $w_{n+1}$, toutes les stratégies de priorité inférieure sont blessées, et retournent à l'état **i**.

Le lecteur fera la vérification. Cela conclut la preuve du théorème 4.1. ■

Stratégie de préservation de Sacks

La stratégie pour satisfaire $S_e$ consiste à ne pas essayer de différencier
deux ensembles activement, mais au contraire, de préserver des segments
initiaux communs de plus en plus longs, pour rendre le processus effectif,
puis utiliser l'hypothèse de non-effectivité de l'un des ensembles pour
en déduire que ce processus devra échouer. Cette stratégie se retrouve
fréquemment dans ce genre de constructions. Elle est parfois appelée
*stratégie de préservation de Sacks*, en l'honneur de son auteur.

5. Méthode de priorité Π₂₀ (à blessure infinie)

Nous allons maintenant aborder une nouvelle élaboration de la méthode
de priorité, dite à blessure infinie. Comme son nom l'indique, certaines
stratégies vont agir infiniment souvent en posant des restreintes de plus
en plus grandes, causant des blessures infinies à des stratégies de priorité
inférieure. Nous allons donc commencer à avoir des stratégies condition-
nelles, adoptant des comportements différents en fonction des issues des
stratégies de priorité supérieure, tirant ainsi pleinement parti du forma-
lisme de « l'arbre des stratégies » que nous verrons bientôt.

Notre illustration de la méthode de priorité à blessure infinie concerne
l'existence de paires minimales de degrés c. e. Elle améliore le théorème
de Friedberg-Muchnik en la combinant avec la stratégie de préservation
de Sacks.

**Définition 5.1.** Deux degrés non calculables **a** et **b** forment une *paire minimale* si leur borne inférieure est **0**, autrement dit si pour tout ensemble **A** tel que $A \leq_T \mathbf{a}$ et $A \leq_T \mathbf{b}$, alors **A** est calculable. ◇
L'existence de paires minimales de degrés c. e. a été prouvée de manière indépendante par Lachlan [129] et Yates [234].

## Théorème 5.2 (Lachlan 1966, Yates 1966)

Il existe une paire minimale de degrés c. e.

PREUVE. Nous allons construire deux ensembles c. e. A et B satisfaisant les contrats suivants $(\mathcal{R}_e, \mathcal{S}_e, \mathcal{N}_e)_{e \in \mathbb{N}}$ :

$$ \mathcal{R}_e : W_e \neq \bar{A} \quad \mathcal{S}_e : W_e \neq \bar{B} \quad \mathcal{N}_e : \Phi_e^A = \Phi_e^B \Rightarrow \Phi_e^A \text{ est calculable.} $$

Les contrats $(\mathcal{R}_e)_{e \in \mathbb{N}}$ et $(\mathcal{S}_e)_{e \in \mathbb{N}}$ s'assurent que A et B ne soient pas calculables. Les contrats $(\mathcal{N}_e)_{e \in \mathbb{N}}$ forcent la borne inférieure des degrés de A et B à être 0.

## Astuce de Posner

À première vue, pour imposer que la borne inférieure $deg_T A$ et $deg_T B$ est 0, on s'attendrait à devoir satisfaire des contrats de la forme $(\mathcal{N}_{i,j})_{i,j \in \mathbb{N}}$ avec

$$ \mathcal{N}_{i,j} : \Phi_i^A = \Phi_j^B \Rightarrow \Phi_i^A \text{ est calculable.} $$

Cependant, si $\Phi_i^A = \Phi_j^B$, alors il est possible de créer une nouvelle fonctionnelle $\Phi_e$ qui codera en dur un entier $n$ tel que $A(n) \neq B(n)$, et exécutera $\Phi_i$ ou $\Phi_j$ en fonction de la valeur de son oracle à la position $n$. Ainsi, $\Phi_e^A = \Phi_i^A$ et $\Phi_e^B = \Phi_j^B$. Cette astuce, due à Posner, permet de simplifier les notations.

Satisfaction d'un contrat $\mathcal{R}_e$ ou $\mathcal{S}_e$. La satisfaction d'un contrat $\mathcal{R}_e$ ou $\mathcal{S}_e$ est exactement la même que pour le théorème 3.3. Nous rappelons dans le cas de $\mathcal{R}_e$ les actions de la stratégie en fonction de ses trois états :

* État i. Choisir un entier $x_{\mathcal{R}_e} \notin A$, et poser une restreinte sur $x_{\mathcal{R}_e}$.

* État e. Exécuter $\Phi_e(x_{\mathcal{R}_e})$. Si l'exécution s'arrête à l'instant $t$, ajouter $x_{\mathcal{R}_e}$ à A, puis passer dans l'état t.

* État t. Le processus est terminé.

Jusqu'ici, nous avons considéré que cette stratégie avait deux issues, en fonction de l'état dans lequel elle se stabilise. Ces deux issues sont de même nature finitaire, en ce qu'elles ne posent qu'un nombre fini de restreintes lorsqu'elles sont blessées finiment souvent. Nous les considérerons donc comme une seule issue f.

Satisfaction d'un contrat $\mathcal{N}_e$. La satisfaction d'un contrat $\mathcal{N}_e$ va suivre la stratégie de préservation de Sacks pour préserver des segments initiaux communs à $\Phi_e^A$ et $\Phi_e^B$ de plus en plus longs.
Cependant, contrairement au théorème 4.1, le processus ne va pas nécessairement échouer au bout d'un nombre fini d'étapes, car rien dans les hypothèses n'empêche cette égalité. Nous sommes donc dans un cas où l'issue infinitaire va pouvoir se produire, avec des restreintes de plus en plus longues, résultant en une blessure infinie. Comme dans le cas du théorème 4.1, la stratégie possède un état initial $i$, et une infinité d'états $(w_n)_{n \in \mathbb{N}}$. Dans ce qui suit, nous appellerons usage de $\Phi_e^{A_t}[t] \upharpoonright_{n+1}$ le maximum des usages de $\{\Phi_e^{A_t}(x)[t] : x \le n\}$. Pendant l'exécution de la stratégie, nous allons définir une fonction calculable $\Delta : \mathbb{N} \to \{0, 1\}$ telle que si $\Phi_e^A$ et $\Phi_e^B$ sont totaux et égaux, alors ils sont tous les deux égaux à $\Delta$.

▷ État $i$. Définir $\Delta$ comme la fonction de domaine vide, et passer à l'état $w_0$.

▷ État $w_n$. Attendre une étape $t \ge n$ où $\Phi_e^{A_t}[t] \upharpoonright_{n+1} = \Phi_e^{B_t}[t] \upharpoonright_{n+1}$. Si cela arrive, relâcher sa restreinte précédente, et poser une restreinte sur l'usage de $\Phi_e^{A_t}[t] \upharpoonright_{n+1}$ si $n$ est pair, et sur l'usage de $\Phi_e^{B_t}[t] \upharpoonright_{n+1}$ si $n$ est impair. Ensuite, définir $\Delta(n) = \Phi_e^{A_t}(n)[t]$, et passer à l'état $w_{n+1}$.

La stratégie a deux issues possibles. Issue $f$ (finitaire) : elle se retrouve bloquée dans l'état $w_n$ pour un $n$ donné; dans ce cas, soit $\Phi_e^A$ ou $\Phi_e^B$ est partiel, soit $\Phi_e^A \neq \Phi_e^B$. Issue $\infty$ (infinitaire) : la stratégie passe par tous les états $(w_n)_{n \in \mathbb{N}}$; dans ce cas, les deux ensembles coïncident, et infiniment souvent, la restreinte change de côté. Il nous reste encore à établir les égalités $\Delta = \Phi_e^A = \Phi_e^B$ pour en déduire que cet ensemble est calculable. L'idée sous-jacente de la preuve est très simple, mais elle est un peu lourde à formaliser. Nous allons donc l'illustrer par une figure (voir la figure 5.3) avant de prouver formellement le résultat à travers le lemme 5.4. Quelle que soit l'issue, le contrat $N_e$ est donc satisfait.

**Remarque**

Le choix du côté de la restreinte (A si la stratégie passe d'un état $w_n$ à $w_{n+1}$ avec $n$ pair, et B si $n$ est impair) n'intervient pas dans la preuve de la validité d'une stratégie $N_e$ indépendamment des autres. On aurait aussi bien pu garder toujours le même côté, ou bien même posser une restreinte des deux côtés, ce qui aurait considérablement simplifié la preuve de validité. Cependant, cette alternance de côtés devient nécessaire lorsque l'on cherche à satisfaire un contrat de type $\mathcal{R}$ ou $\mathcal{S}$ sous une stratégie pour $N_e$, comme nous le verrons par la suite.

**Lemme 5.4.** Si l'issue $\infty$ arrive, alors $\Delta = \Phi_e^A = \Phi_e^B$.

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

PREUVE. Soit $P(n, s)$ la proposition « Soit (1) $\Delta \upharpoonright_{n+1} = \Phi_{e^s}^A[s] \upharpoonright_{n+1}$ avec une restreinte sur son usage, soit (2) $\Delta \upharpoonright_{n+1} = \Phi_{e^s}^B[s] \upharpoonright_{n+1}$ avec une restreinte sur son usage. »
<figure><img src="image_95.png" /><figcaption>FIGURE 5.3 – Soit $t_n$ l'étape de passage à l'état $w_{n+1}$. Le rectangle gris entre l'étape $t_3$ et $t_4$ signifie que l'usage de $\Phi_e^{A_{t_3}}[t_3] \rfloor_4$ est restreint, et donc préservé jusqu'à l'étape $t_4$. Ainsi, $\Phi_e^{A_{t_3}}[t_3] \rfloor_4 = \Phi_e^{A_{t_4}}[t_4] \rfloor_4$. À chaque étape $t_n$, les segments initiaux de longueur $n+1$ des deux fonctionnelles sont égaux. Ainsi, $\Phi_e^{A_{t_4}}[t_4] \rfloor_5 = \Phi_e^{B_{t_4}}[t_4] \rfloor_5$. Nous avons donc</figcaption></figure>

$$ \Phi_e^{B_{t_3}}[t_3] \rfloor_4 = \Phi_e^{A_{t_3}}[t_3] \rfloor_4 = \Phi_e^{A_{t_4}}[t_4] \rfloor_4 = \Phi_e^{B_{t_4}}[t_4] \rfloor_4. $$

Même si l'usage de $\Phi_e^{B_{t_3}}[t_3] \rfloor_4$ peut être différent de celui de $\Phi_e^{B_{t_4}}[t_4] \rfloor_4$, car aucune restreinte n'est posée sur B entre les étapes $t_3$ et $t_4$, les quatre premières valeurs de sortie de la fonctionnelle sont préservées.

Pour tout $n$, soit $t_n$ l'étape à laquelle la stratégie passe dans l'état $w_{n+1}$. Nous allons montrer par induction sur les entiers $n$ et $s$ que pour tout $n \ge 0$ et $s \ge t_n$, la proposition $P(n, s)$ est vraie. Par convention, $t_{-1} = 0$, et pour tout $s \ge t_{-1}$, $P(-1, s)$ est vraie.

Soit $n \ge 0$. Montrons que si pour tout $s \ge t_{n-1}$, $P(n-1, s)$ est vraie, alors $P(n, t_n)$ est vraie. À l'étape $t_n$, $\Delta(n) = \Phi_e^{A_{t_n}}(n)[t_n] = \Phi_e^{B_{t_n}}(n)[t_n]$, et $\Phi_e^{A_{t_n}}[t_n] \rfloor_{n+1} = \Phi_e^{B_{t_n}}[t_n] \rfloor_{n+1}$. Comme $t_n \ge t_{n-1}$, par hypothèse d'induction, $P(n-1, t_n)$ est vraie, de sorte que l'on a soit $\Delta \rfloor_n = \Phi_e^{A_{t_n}}[t_n] \rfloor_n$, soit $\Delta \rfloor_n = \Phi_e^{B_{t_n}}[t_n] \rfloor_n$. Par suite, $\Delta \rfloor_{n+1} = \Phi_e^{A_{t_n}}[t_n] \rfloor_{n+1} = \Phi_e^{B_{t_n}}[t_n] \rfloor_{n+1}$. À cette étape-ci, la stratégie pose une restreinte sur $\Phi_e^{A_{t_n}}[t_n] \rfloor_{n+1}$ ou bien sur $\Phi_e^{B_{t_n}}[t_n] \rfloor_{n+1}$, donc $P(n, t_n)$ est vraie.

Soit $s > t_n$. Montrons que si $P(n, s-1)$ est vraie, alors $P(n, s)$ est vraie. Si la stratégie ne change pas d'état à l'étape $s$, alors elle garde sa restreinte, et par la propriété de l'usage, $P(n, s)$ reste vraie. Si la stratégie passe à un état $w_{p+1}$, alors par définition, $\Phi_e^{A_s}[s] \rfloor_{p+1} = \Phi_e^{B_s}[s] \rfloor_{p+1}$, or $p \ge n$, donc $\Phi_e^{A_s}[s] \rfloor_{n+1} = \Phi_e^{B_s}[s] \rfloor_{n+1}$.

Par $P(n, s-1)$, soit $\Delta \rfloor_{n+1} = \Phi_e^{A_{s-1}}[s-1] \rfloor_{n+1}$ avec une restreinte sur son usage, soit $(2) \Delta \rfloor_{n+1} = \Phi_e^{B_{s-1}}(n)[s-1] \rfloor_{n+1}$ avec une restreinte sur son
usage. Par la restreinte à l'étape $s-1$ et la propriété de l'usage,

$$ \text{soit } \Delta \lceil_{n+1} = \Phi_e^{A_s}[s] \lceil_{n+1}, \quad \text{soit } \Delta \lceil_{n+1} = \Phi_e^{B_s}[s] \lceil_{n+1}. $$

Il s'ensuit que $\Delta \lceil_{n+1} = \Phi_e^{A_s}[s] \lceil_{n+1} = \Phi_e^{B_s}[s] \lceil_{n+1}$. La stratégie pose une restreinte sur l'usage de $\Phi_e^{A_s}[s] \lceil_{p+1}$ ou $\Phi_e^{B_s}[s] \lceil_{p+1}$, donc $P(n, s)$ est vraie. Cela termine la preuve du lemme. ■

Notons que contrairement au théorème 4.1, l'issue infinitaire va vraiment se produire avec la stratégie pour $N_e$. Elle ne se combine donc pas aussi bien avec les stratégies pour $R_d$ et $S_d$. En effet, lorsque cette issue arrive, la stratégie pour $N_e$ va poser des restreintes de plus en plus longues, causant une blessure infinie. Nous allons donc devoir adapter la construction pour permettre aux autres contrats d'être satisfaits.

## Étapes d'exécution

Il n'est pas nécessaire d'exécuter les stratégies pour $R_e$, $S_e$ et $N_e$ à chaque étape pour satisfaire leurs contraintes respectives. Il suffit de les exécuter chacune pendant un nombre infini d'étapes, tout en maintenant leurs restreintes pendant les étapes intermédiaires.

Prenons l'exemple de la stratégie pour $R_e$. Si elle n'est exécutée qu'aux temps $t_0 < t_1 < \dots$, il se peut qu'elle « manque » la première étape $t$ entre $t_0$ et $t_1$ où $\Phi_e(x_{R_e})[t]$ s'arrête, ce qui l'empêche de passer dans l'état $t$ à cette étape. Cependant, à l'étape $t_1$, $\Phi_e(x_{R_e})[t_1]$ s'arrêtera également, et le passage à l'état $t$ aura quand même lieu. Le comportement limite de la stratégie pour $R_e$ ne dépend donc pas du choix des étapes.

Le cas de la stratégie pour $N_e$ est un peu plus subtil. Il se peut que la stratégie par défaut pour $N_e$ ait une issue infinitaire, mais que lorsqu'elle n'est exécutée qu'aux temps $t_0 < t_1 < \dots$, on ait

$$ \Phi_e^{A_t}[t_i] \lceil_{n+1} \neq \Phi_e^{B_t}[t_i] \lceil_{n+1}, $$

ce qui fait que la stratégie ne passera jamais à l'état $w_{n+1}$, ce qui correspond à l'issue finitaire. Heureusement, même dans ce cas, $N_e$ sera satisfait, tant que l'énumération des étapes $(t_i)_{i \in \mathbb{N}}$ est calculable pour que la fonction $\Delta$ le soit également.

## Satisfaction d'un contrat $R_d$ ou $S_d$ sous $N_e$. Supposons que l'on veuille satisfaire un contrat $R_d$ sous la stratégie pour $N_e$, c'est-à-dire avec la stratégie pour $N_e$ de priorité supérieure à celle pour $R_d$. Plusieurs solutions se présentent, en fonction de l'issue de la stratégie pour $N_e$.

* Issue f (finitaire). Dans ce cas, il suffit d'utiliser la stratégie standard pour $R_d$ présentée plus haut. En effet, la stratégie pour $N_e$ posera un
nombre fini de restreintes, ce qui fait que la stratégie pour $R_d$ sera blessée et réinitialisée un nombre fini de fois avant d'être satisfaite. Cette stratégie ne fonctionne pas si l'issue de la stratégie pour $N_e$ est infinitaire (issue $\infty$). En effet, dans ce cas, la stratégie pour $R_d$ sera blessée infiniment souvent, et pourrait ne jamais satisfaire $R_d$.

▷ Issue $\infty$ (infinitaire). Remarquons que dans ce cas, la restreinte posée par la stratégie pour $N_e$ alternera infiniment souvent de côté, et libérera donc l'autre côté, permettant à la stratégie pour $R_d$ d'être satisfaite. Nous allons donc n'exécuter la stratégie pour $R_d$ qu'aux étapes où la restreinte de la stratégie pour $N_e$ est retirée du côté $A$. L'issue de la stratégie pour $N_e$ étant infinitaire, la stratégie pour $R_d$ va être exécutée pendant un nombre infini d'étapes, et comme expliqué plus haut, un sous-ensemble infini d'étapes est suffisant pour satisfaire $R_d$. Cette stratégie pour $R_d$ ne fonctionne cependant pas si l'issue de la stratégie pour $N_e$ est finitaire, car il se peut qu'elle ne lève jamais sa restreinte et que la stratégie pour $R_d$ attende donc pour toujours.

Nous avons donc deux stratégies différentes pour satisfaire $R_d$ sous $N_e$, en fonction de l'issue de la stratégie pour $N_e$. Cette analyse de cas pose une difficulté : pour produire un ensemble c. e., il faut que la construction soit un processus calculable, or l'issue de $N_e$ ne peut pas être décidée en un temps fini. Nous ne pouvons donc pas savoir quelle stratégie choisir pour $R_d$. La solution consiste à lancer les deux stratégies pour $N_e$ en parallèle, cha-cune faisant une supposition sur l'issue. Celle faisant la bonne supposition pourra alors satisfaire $R_d$ sous $N_e$. Nous allons donc nous retrouver avec un arbre de stratégies, induit par les analyses de cas successives sur les issues des stratégies de type $N$. Nous détaillerons plus bas cette structure arborescente.

**Satisfaction d'un contrat** $N_d$ sous $N_e$. Les contrats de même nature sont souvent faciles à satisfaire simultanément, car leurs stratégies n'entrent généralement pas en conflit. Dans le cas de la satisfaction d'un contrat $N_d$ sous $N_e$, la difficulté n'est pas de satisfaire ces deux contrats simultanément, mais de laisser ensuite la place à un contrat de type $R$ ou $S$ d'être satisfait sous $N_d$. En effet, dans le pire des cas, les stratégies pour $N_e$ et $N_d$ seront toutes les deux infinitaires, et à chaque fois que la stratégie pour $N_e$ libérera ses restreintes du côté $A$, la stratégie pour $N_d$ posera les siennes, ce qui fait que le côté $A$ aura à tout moment des restreintes de plus en plus grandes, ne permettant pas aux stratégies de type $R$ d'être satisfaites en dessous. La solution consiste à « synchroniser » les stratégies pour $N_d$ et $N_e$. Plus précisément, la stratégie pour $N_d$ va être définie par analyse de cas en fonction de l'issue de $N_e$.

▷ Issue $f$ (finitaire). Dans ce cas, la stratégie pour $N_d$ est la stratégie standard présentée plus haut. En effet, les restreintes de la stratégie pour $N_e$
seront finitaires, et les autres contrats auront la possibilité d'être satis-
faits sous $\mathcal{N}_d$ en étant blessés finiment souvent par la stratégie de $\mathcal{N}_e$.

▷ Issue $\infty$ (infinitaire). Modifions la stratégie pour $\mathcal{N}_d$, comme suit. Cette stratégie ne sera exécutée que pendant des étapes où la stratégie pour $\mathcal{N}_e$ change ses restreintes de côté, autrement dit passe de l'état $\mathbf{w}_n$ à $\mathbf{w}_{n+1}$. Cela permet de s'assurer que lorsque la stratégie pour $\mathcal{N}_d$ change ses restreintes de côté, à la même étape, la stratégie pour $\mathcal{N}_e$ changera les siennes de côté. Enfin, il faut s'assurer que ces changements aillent du même côté. Pour cela, si la stratégie pour $\mathcal{N}_d$ est dans un état $\mathbf{w}_n$ avec $n$ un entier pair, autrement dit si ses restreintes sont du côté $B$, la stratégie pour $\mathcal{N}_d$ ne sera exécutée que pendant les étapes où la stratégie pour $\mathcal{N}_e$ passe d'un état $\mathbf{w}_m$ à $\mathbf{w}_{m+1}$ avec $m$ pair, pour que les deux stratégies mettent leur restreintes sur le côté $A$ simultanément. De la même manière, si la stratégie pour $\mathcal{N}_d$ est dans un état $\mathbf{w}_n$ avec $n$ un entier impair, elle s'exécutera pendant les étapes où la stratégie pour $\mathcal{N}_e$ passe d'un état $\mathbf{w}_m$ à $\mathbf{w}_{m+1}$ avec $m$ impair.

Comme dans le cas de la satisfaction d'un contrat $\mathcal{R}_d$ sous un contrat $\mathcal{N}_e$, nous avons donc des stratégies pour $\mathcal{N}_d$ différentes pour chaque issue de la stratégie pour $\mathcal{N}_e$. Nous allons donc lancer deux stratégies en parallèle, chacune supposant que son hypothèse est la bonne. Nous allons maintenant décrire l'arbre des stratégies.

**Arbre des stratégies.** Les contrats sont énumérés de la manière suivante.

$$
\mathcal{N}_0, \mathcal{R}_0, \mathcal{S}_0, \mathcal{N}_1, \mathcal{R}_1, \mathcal{S}_1, \dots
$$

Dans les constructions précédentes, chaque contrat se voyait attribuer une
unique stratégie, et l'ordre de priorité des stratégies suivait l'énumération
des contrats. Nous avons maintenant une structure arborescente de straté-
gies en fonction des issues des stratégies précédentes, comme ci-après : le
contrat $\mathcal{N}_0$ possède une unique stratégie $N_\epsilon$ (où $\epsilon$ est la chaîne vide). Le
contrat $\mathcal{R}_0$ admet deux stratégies $R_\infty$ et $R_f$, en fonction des issues $\infty$ et $f$
de la stratégie $\mathcal{N}_0$. Le contrat $\mathcal{S}_0$ possède également deux stratégies $S_{\infty f}$
et $S_{ff}$, en fonction des issues des stratégies plus hautes. Par exemple, $S_{\infty f}$
doit satisfaire le contrat $\mathcal{S}_0$ sous l'hypothèse que l'issue de $N_\epsilon$ est $\infty$ et
l'issue de $R_\infty$ est $f$.

De manière générale, nous pouvons définir un arbre $\mathcal{T} \subseteq \{\mathbf{f}, \infty\}^{<\mathbb{N}}$ de
chaînes dans l'alphabet $\{\mathbf{f}, \infty\}$, induit par la relation de préfixe, tel que
pour tout $\sigma \in \mathcal{T}$ et $i < |\sigma|$ tel que $i \neq 0 \bmod 3$, $\sigma(i) = \mathbf{f}$. À chaque
chaîne $\sigma \in \mathcal{T}$, si $|\sigma| = 3e$ on associe une stratégie $N_\sigma$ pour $\mathcal{N}_e$, si $|\sigma| = 3e+1$
on associe une stratégie $R_\sigma$ pour $\mathcal{R}_e$, et si $|\sigma| = 3e+2$ on associe une
stratégie $S_\sigma$ pour $\mathcal{S}_e$ (voir la figure 5.5). Pour simplifier les notations, nous
noterons $C_\sigma$ la stratégie dont l'indice est $\sigma$.
<figure><img src="image_96.png" /><figcaption>FIGURE 5.5 – Arbre des stratégies pour la construction d’une paire minimale. Les flèches pleines indiquent la structure d’arbre, mais également induisent un ordre partiel de priorité entre les stratégies. Les flèches en pointillés permettent de linéariser l’ordre partiel pour obtenir un ordre total entre les stratégies. Par exemple, toutes les stratégies du sous-arbre gauche de la stratégie $N_{\infty ff}$ sont plus faibles que $N_{\epsilon}$, $R_{\infty}$, $S_{\infty f}$ et $N_{\infty ff}$, mais sont plus fortes que toutes les autres stratégies.</figcaption></figure>

**Construction.** Au début de la construction, chaque stratégie est dans l'état initial i. À chaque étape t, nous allons définir un nœud courant, qui est une chaîne $\sigma_t \in \mathcal{T}$ de longueur t, représentant une approximation des issues à la fin de l'étape t. Plus précisément, $\sigma_t(i)$ représente l'approximation à l'étape t de l'issue de la stratégie $C_{\sigma_t|_i}$. Le nœud courant à l'étape t est défini par induction sur les sous-étapes $s < t$ comme suit.

Au début de la sous-étape i, on suppose $\sigma_t|_i$ défini. On exécute alors la stratégie $C_{\sigma_t|_i}$ au temps t comme décrit ci-dessus. Rappelons qu'il se peut que l'on n'exécute pas la stratégie $C_{\sigma_t|_i}$ pour des raisons de synchronisation avec les stratégies pour les contrats de type $\mathcal{N}$. Dans ce cas, la stratégie reste dans son état et garde ses contraintes inchangées. À la fin de la sous-étape t, on définit $\sigma_t(i) = \infty$ si $i \equiv 0 \mod 3$, et la stratégie $N_{\sigma_t|_i}$ a changé d'état à l'étape t. Dans tous les autres cas, $\sigma_t(i) = f$, car les stratégies de type $\mathcal{R}$ et $\mathcal{S}$ n'ont que l'issue finitaire possible, et si $i \equiv 0 \mod 3$, et $N_{\sigma_t|_i}$ ne vient pas de changer d'état, nous supposons que son issue est finitaire.

**Vrai chemin.** Nous pouvons maintenant définir le vrai chemin de $\mathcal{T}$, qui est le chemin le long duquel les issues sont les vraies. Plus précisément, le vrai chemin de $\mathcal{T}$ est la suite infinie $P \in \Lambda^\mathbb{N}$ (avec $\Lambda = \{\infty, f\}$, où $\infty$ est plus petit que $f$) définie inductivement sur i par

$$P(i) = \liminf\{o \in \Lambda : \exists^{\infty} t (P|_i)^o o \le \sigma_t\}.$$
Intuitivement, les stratégies le long du vrai chemin vont être celles qui feront les bonnes hypothèses sur les issues des stratégies précédentes. Elles seront blessées finiment souvent par une stratégie de plus grande priorité, et réussiront à satisfaire leur contrat. Nous allons maintenant définir un ordre de priorité sur les stratégies pour que les stratégies le long du vrai chemin soient finiment blessées.

**Ordre de priorité.** Soit $\Lambda = \{\infty, f\}$ l'ensemble des issues possibles. Musnissons cet ensemble d'un ordre de priorité $<_p$ en considérant que $\infty <_p f$, ce qui signifie que l'issue $\infty$ est prioritaire par rapport à $f$. Cet ordre va induire un ordre total $(\mathcal{T}, <_p)$ (et donc un ordre total de priorité sur les stratégies) comme suit : $\sigma <_p \tau$ si $\sigma \preceq \tau$, ou si $i$ est la première position où les deux chaînes diffèrent, et $\sigma(i) <_p \tau(i)$. Un exemple visuel de cet ordre est donné dans la figure 5.5. Notons que, contrairement aux méthodes de priorité à blessure finie, les stratégies sont généralement en dessous d'une infinité de stratégies de priorité supérieure. Par exemple, la stratégie $R_{\infty\mathcal{F}\mathcal{F}}$ est en dessous de $N_\epsilon, R_\infty, S_{\infty f}, N_{\infty\mathcal{F}\mathcal{F}}, R_{\infty\mathcal{F}\infty}, S_{\infty\mathcal{F}\infty\mathcal{F}}, \dots$

**Remarque**

On serait tenté de définir un ordre de priorité tel que chaque stratégie n'ait qu'un nombre fini de stratégies prioritaires, par exemple en définissant les priorités par un parcours en largeur des nœuds de l'arbre. Le problème suivant se pose cependant.

Supposons que la stratégie $N_\epsilon$ ait pour issue $\infty$. La stratégie $R_f$ faisant la mauvaise hypothèse selon laquelle l'issue de $N_\epsilon$ a une issue finitaire, elle sera blessée et réinitialisée à chaque changement d'état de $N_\epsilon$. Elle pourra donc potentiellement un nombre infini de restreintes, et empêchera donc toutes les stratégies de priorité inférieure de fonctionner normalement. Il est donc essentiel que toutes les stratégies le long du vrai chemin de l'arbre soient prioritaires par rapport à $R_f$, afin d'ignorer ses restreintes. La stratégie pour $R_f$ doit donc être sous une infinité de stratégies prioritaires.

**Vérification.** Notons tout d'abord que, par définition, les stratégies le long du vrai chemin $P$ (stratégies $C_\sigma$ pour $\sigma < P$) sont exécutées à une infinité d'étapes. Bien qu'une stratégie soit en général en dessous d'une infinité de stratégies, nous allons montrer que les stratégies le long du vrai chemin sont blessées finiment souvent, ce qui est la condition nécessaire pour les satisfaire. Le lemme suivant est une propriété que l'on attend généralement d'un argument de priorité $\Pi_2^0$.

**Lemme 5.6.** Soit $P$ le vrai chemin, et soit $\alpha < P$. Alors, $\alpha \leq_p \sigma_t$ pour un nombre co-fini d'étapes $t$. \*
PREUVE. Par induction sur la longueur $n$ de $\alpha$. Si $n=0$, alors $\alpha = \epsilon$, et par définition, $\epsilon \leq_p \sigma_t$ pour tout $t$. Soit $n > 0$. Par hypothèse d'induction, il existe un seuil $t_0$ tel que $\alpha \upharpoonright_{n-1} \leq_p \sigma_t$ pour tout $t \geq t_0$. Soit

$$S = \{t \geq t_0 : \sigma_t <_p \alpha\}.$$

Supposons par l'absurde que $S$ est infini.

Notons que pour tout $t \in S$, comme $\alpha \upharpoonright_{n-1} \leq_p \sigma_t$ et $\sigma_t <_p \alpha$, on a forcément $\alpha \upharpoonright_{n-1} \leq \sigma_t$ avec $\sigma_t(n-1) <_p \alpha(n-1)$. Autrement dit, $\sigma_t(n-1) = \infty$ et $\alpha(n-1) = \mathbf{f}$ et $\forall t \in S$ ($\alpha \upharpoonright_{n-1} \frown \infty \leq \sigma_t$. Ainsi, $(\alpha \upharpoonright_{n-1}) \frown \infty \leq P$, contredisant l'hypothèse $\alpha \frown \leq P$. Cela conclut la preuve du lemme. ■

Seules les stratégies le long de $\sigma_t$ sont exécutées à l'étape $t$. Ainsi, pour toute stratégie $C_\alpha$ le long du vrai chemin $P$, il existe un seuil $t_0$ après lequel seules les stratégies de plus faible priorité ou des stratégies le long du vrai chemin vont être exécutées. Nous pouvons donc prouver par induction sur $n$ que la stratégie $C_{P \upharpoonright_n}$ ne sera blessée que finiment souvent, et aura l'issue $P(n)$. Tout contrat étant représenté par une stratégie le long du vrai chemin, les contrats seront tous satisfaits. Cela conclut la preuve du théorème 5.2. ■

## Degrés cappables

Nous avons vu deux manières de créer des degrés Turing incomparables. La première (voir la proposition 4-8.1) consiste à créer deux ensembles somultanément, tandis que la seconde (voir la proposition 4-8.2) part d'un ensemble non calculable, et crée un deuxième ensemble de degré incomp comparable avec le premier. Il est naturel de se demander s'il est possible, dans le cas des paires minimales de degrés c. e., de partir d'un ensemble c. e. non calculable arbitraire, et le compléter avec un autre ensemble c. e. pour former une paire minimale. Ce n'est pas le cas, comme l'ont prouvé Yates [234] et Lachlan [129].

**Définition 5.7.** Un degré c. e. $\mathbf{a} > \mathbf{0}$ est dit *cappable* s'il existe un degré $\mathbf{b} > \mathbf{0}$ tel que $\mathbf{a}$ et $\mathbf{b}$ forment une paire minimale. Sinon, $\mathbf{a}$ est dit *non cappable*. ◇

Notons que le terme « cappable » vient de l'anglais « cap » et « able », et n'a en particulier rien à avoir avec l'adjectif « capable ». Ambos-Pies et al. [5] ont obtenu une surprenante caractérisation des degrés non cappables, à l'aide des ensembles promptement simples.
**Définition 5.8.** Un ensemble co-infini c. e. $A$ est *promptement simple* s'il existe une énumération c. e. calculable $A_0 \subseteq A_1 \subseteq \dots$ et une fonction calculable $f: \mathbb{N} \to \mathbb{N}$ telles que

$$ W_e \text{ infini} \Rightarrow \exists^{\infty} x, s \ (x \in W_e[s] \ \& \ W_e[s-1] \ \& \ x \in A_{f(s)}). \diamond $$

Autrement dit, un ensemble co-infini $A$ est promptement simple s'il est non seulement co-immune, mais plus encore, cette co-immunité doit être réalisée en faisant infiniment souvent entrer des éléments dans $A$ peu de temps après qu'ils apparaissent dans $W_e$.

Un degré c. e. est *promptement simple* s'il contient un ensemble promptement simple.

**Théorème 5.9 (Ambos-Spies, Jockusch, Shore, et Soare [5])**

Les degrés non cappables sont précisément les degrés promptement simples.

En particulier, la preuve montrant qu’un degré est cappable s’il n’est pas promptement simple est obtenue avec une variation du théorème 5.2.
<figure><img src="image_97.png" /></figure>
Chapitre 14

Structure des degrés Turing

L'étude des degrés Turing a été menée conjointement avec celle de sa *structure*, en tant qu'ordre partiel. Gerald E. Sacks est sans aucun doute l'un des principaux protagonistes de cette aventure.

Sacks entame dans sa jeunesse des études d'ingénieur à l'université de Cornell, qu'il interrompt à mi-parcours pour s'engager trois ans durant dans l'armée. C'est à ce moment qu'il met la main sur une copie de *Introduction to Metamathematics* de Kleene, qui le passionne [35]. À son retour à la vie civile, il oriente alors la suite de ses études vers les mathématiques. Barkley Rosser, éminent logicien qui fut étudiant avec Kleene auprès de Church, accepte de le

prendre comme étudiant en thèse. Sacks deviendra dans les années soixante l'un des pionniers de la calculabilité moderne. Il participera notamment comme nous le verrons aux premières études sur la structure des degrés Turing, et outre son travail, il deviendra célèbre pour le grand nombre de ses étudiants qui deviendront des logiciens de premier plan, parmi les-quels on peut citer Harvey et Sy Friedman, Léo Harrington, Richard Shore, Théodore Slaman et Stephen Simpson. Nous verrons que les trois derniers

<figure><img src="image_98.png" /><figcaption>Gerald Sacks, 1933-2019</figcaption></figure>
membres de cette liste ont pris une part très active dans l'étude de la
structure des degrés Turing.

Posons sans plus tarder le vocabulaire que nous utiliserons.

Notation

On notera ($\mathcal{D}, \leq$) la structure d'ordre partiel des degrés Turing.

On écrira $\mathbf{a} \leq \mathbf{b}$ pour deux degrés $\mathbf{a}, \mathbf{b} \in \mathcal{D}$ si $A \leq_T B$ pour tout élément $A \in \mathbf{a}$ et tout élément $B \in \mathbf{b}$, et l'on écrira $\mathbf{a} < \mathbf{b}$ si $\mathbf{a} \leq \mathbf{b}$ et $\mathbf{b} \nleq \mathbf{a}$. Afin d'être tout à fait clairs, rappelons le vocabulaire d'usage des ordres partiels : étant donné un ensemble partiellement ordonné $A$ et un sous-ensemble $B \subseteq A$, un majorant (resp. minorant) de $B$ est un élément de $A$ plus grand (resp. plus petit) que tous les éléments de $B$. Un majorant (resp. minorant) de $B$ est minimal (resp. maximal) si aucun autre majorant de $B$ n'est plus petit que lui (resp. aucun autre minorant de $B$ n'est plus grand que lui). Enfin, un majorant (resp. minorant) de $B$ est une borne supérieure (resp. borne inférieure) si elle est plus petite que tout majorant de $B$ (resp. plus grande que tous les minorants de $B$). On montre sans peine qu'une borne supérieure (resp. inférieure) quand elle existe est unique.

La littérature sur le sujet étant exclusivement en anglais, nous mettons
l'accent sur le fait que l'anglais *upper bound* et *lower bound* ne correspond
pas au français « borne supérieure » et « borne inférieure », mais plutôt
à majorant et minorant. L'anglais utilise à la place *least upper bound* et
*greatest lower bound* pour borne supérieure et borne inférieure.

1. Degrés minimaux

Un des tout premiers résultats obtenus sur la structure des degrés Turing concerne les segments initiaux de $\mathcal{D}$, et notamment l'existence de degrés dits *minimaux*.

**Définition 1.1.** Un degré Turing **d** est *minimal* s'il est différent de 0 —
le degré calculable — et s'il n'existe pas de degré **e** tel que 0 < **e** < **d**. ♢

Autrement dit, un ensemble $X \in 2^N$ est de degré minimal s'il est non calculable et si pour toute fonctionnelle $\Phi$ telle que $\Phi(X, n) \downarrow \in \{0, 1\}$ pour tout $n$, soit l'ensemble $\{n : \Phi(X, n) \downarrow= 1\}$ est calculable, soit il permet de calculer $X$.

La preuve de l'existence d'un degré minimal est une des premières utilisa-
tions du forcing en calculabilité, via le forcing de Sacks, que nous avons vu
dans la section 11-3.
## 1.1. Existence

L'existence de degrés minimaux, due à Spector [215], fut au départ faite par forcing avec des f-arbres $T: 2^{<N} \to 2^{<N}$ calculables uniformes, c'est-à-dire des f-arbres tels que pour toute taille $n$ il existe une unique chaîne $\tau_n$ telle que, pour toute chaîne $\sigma$ de taille $n$ et tout $i \in \{0, 1\}$, on a

$$T(\sigma i) = T(\sigma)i\tau_n.$$

On peut aussi voir les chemins de ces f-arbres comme étant toutes les possibilités de complétion d'un ensemble $X$ sur lequel une infinité de bits ne sont pas spécifiés.

La restriction de Spector présente son intérêt pour l'étude plus générale de segments initiaux dans les degrés Turing, mais pour ce qui est des degrés minimaux (c'est-à-dire des segments initiaux de taille 2), Shoenfield [198] a remarqué que le forcing de Sacks calculable, plus simple à manipuler, est suffisant.

**Définition 1.2.** Soit $\Gamma$ une fonctionnelle Turing.

(1) Deux chaînes $\sigma, \tau \in 2^{<N}$ forment une $\Gamma$-scission s'il existe un entier $n$ tel que $\Gamma^\sigma(n) \downarrow \neq \Gamma^\tau(n) \downarrow$.

(2) Un f-arbre $T: 2^{<N} \to 2^{<N}$ est $\Gamma$-scindé si pour tout $\sigma \in 2^{<N}$, les deux chaînes $T(\sigma 0)$ et $T(\sigma 1)$ forment une $\Gamma$-scission.

(3) Un f-arbre $T$ est $\Gamma$-uni si aucune paire de chaînes $\sigma, \tau \in \text{Im} T$ ne forme une $\Gamma$-scission. ◇

On considérera pour cette section les fonctionnelles $\Gamma$ comme étant des fonctions partielles de $2^N$ vers $2^N$. Dans ce contexte particulier, on notera alors $\text{dom} \Gamma$ — le domaine de définition de $\Gamma$ — comme étant la classe

$$\{X \in 2^N : \forall n \Gamma(X, n) \downarrow \in \{0, 1\}\}.$$

Étant donné $X \in \text{dom} \Gamma$, on écrira $\Gamma(X)$ pour l'ensemble

$$\{n \in \mathbb{N} : \Gamma(X, n) \downarrow = 1\},$$

et l'on parlera de la totalité de $\Gamma$ vis-à-vis de $2^N$, et non pas vis-à-vis de ses entrées pour un oracle fixé.

Le lemme clef dans la construction d'un degré minimal dit que pour toute fonctionnelle $\Gamma$ et tout f-arbre calculable, il existe un sous f-arbre calculable sur lequel $\Gamma$ est partout définie et injective, ou sur lequel $\Gamma$ est une fonction constante, restreinte à son domaine de définition dans le sous f-arbre.

**Lemme 1.3.** Pour tout f-arbre calculable $T: 2^{<N} \to 2^{<N}$ et toute fonctionnelle Turing $\Gamma$, il existe un sous f-arbre calculable $S$ de $T$ qui est soit $\Gamma$-scindé, soit $\Gamma$-uni. ★
### PREUVE.
Deux cas se présentent.

Cas 1. Il existe une chaîne $\sigma \in 2^{<\mathbb{N}}$ telle pour tous $\rho, \tau \succeq \sigma$, les chaînes $T(\rho)$ et $T(\tau)$ ne forment pas de $\Gamma$-scission. Soit $S$ le sous-f-arbre calculable donné par $S(\mu) = T(\sigma\mu)$. Alors, $S$ est un sous-f-arbre $\Gamma$-uni de $T$.

Cas 2. Pour toute chaîne $\sigma \in 2^{<\mathbb{N}}$, il existe des extensions $\rho, \tau \succeq \sigma$ telles que $T(\rho)$ et $T(\tau)$ forment une $\Gamma$-scission. On calcule alors $S$ comme suit. On définit $S(\epsilon) = T(\epsilon)$. Supposons que l'on ait calculé $S(\sigma) = T(\mu)$ pour des chaînes $\sigma, \mu \in 2^{<\mathbb{N}}$. On cherche alors des chaînes $\rho_0, \rho_1 \succeq \mu$ telles que $T(\rho_0)$ et $T(\rho_1)$ forment une $\Gamma$-scission. Par hypothèse, la recherche aboutit nécessairement. On définit alors $S(\sigma 0) = T(\rho_0)$ et $S(\sigma 1) = T(\rho_1)$. Notons que comme $T(\rho_0)$ et $T(\rho_1)$ forment une $\Gamma$-scission, en particulier, ces deux chaînes sont incomparables.

Ainsi, $S$ est bien un f-arbre, et $\text{Im}\,S \subseteq \text{Im}\,T$. Par construction, $S$ est $\Gamma$-scindé. ■

L'intérêt d'obtenir des f-arbres $\Gamma$-unis ou $\Gamma$-scindés se trouve dans le lemme suivant.

**Lemme 1.4.** Soient $T$ un f-arbre calculable et $\Gamma$ une fonctionnelle.

(1) Si $T$ est $\Gamma$-uni, alors pour tout $X \in \text{dom}\,\Gamma \cap [T]$ l'élément $\Gamma(X)$ est calculable.

(2) Si $T$ est $\Gamma$-scindé, alors pour tout $X \in \text{dom}\,\Gamma \cap [T]$ on a $X \leq_T \Gamma(X)$. ⋆

### PREUVE.
(1) Supposons que $T$ soit $\Gamma$-uni. Soit $X \in \text{dom}\,\Gamma \cap [T]$. Alors, pour connaître le $n$-ième bit de $\Gamma(X)$, il suffit de chercher $\sigma \in \text{Im}\,T$ tel que $\Gamma(\sigma, n) \downarrow = i$ pour $i \in \{0, 1\}$. Le $n$-ième bit de $\Gamma(X)$ est alors égal à $i$.

(2) Supposons que $T$ soit $\Gamma$-scindé, et soit $X \in \text{dom}\,\Gamma \cap [T]$. Soit $Y = \Gamma(X)$. Pour calculer $X$ à partir de $Y$, on procède comme suit : comme $T(0)$ et $T(1)$ forment une $\Gamma$-scission, il existe $i \in \{0, 1\}$ tel que $\Gamma(T(i), n)$ soit différent de $Y(n)$, pour un certain $n$. On peut trouver $i$ de manière calculable en $Y$. Le bon préfixe de $X$ est alors nécessairement $T(1 - i)$. Supposons que l'on ait calculé un préfixe $\sigma \prec X$ et une chaîne $\tau$ telle que $\sigma = T(\tau)$. Comme $T(\tau 0)$ et $T(\tau 1)$ forment une $\Gamma$-scission, il existe $i \in \{0, 1\}$ tel que $\Gamma(T(\tau i), n)$ soit différent de $Y(n)$, pour un certain $n$. On peut trouver $i$ de manière calculable en $Y$. Le bon préfixe de $X$ est alors nécessairement $T(\tau(1 - i))$. En procédant de la sorte, on calcule alors des préfixes de $X$ de plus en plus grands à partir de $Y = \Gamma(X)$. ■

Nous avons à présent tous les ingrédients nécessaires pour montrer l'existence de degrés minimaux.
**Théorème 1.5 (Spector [215])**

Tout ensemble suffisamment générique pour le forcing de Sacks est de degré minimal.

PREUVE. Soit $(\mathbb{P}, \leq) \text{ le forcing de Sacks calculable. Notons d'abord que,}$
d'après l'exercice 11-3.3, si $G \in 2^N$ est suffisamment générique pour ce
forcing, alors il n'est pas calculable.

Soit $\Gamma$ une fonctionnelle Turing. D'après le lemme 1.3, l'ensemble des conditions $c \in \mathbb{P}$ telles que $c$ est $\Gamma$-scindé ou $c$ est $\Gamma$-uni est dense. D'après le lemme 1.4, dans le premier cas, pour tout $G \in [c]$, la fonctionnelle $\Gamma$ est définie sur $G$ et $\Gamma(G) \geq_T G$. Dans le second cas, d'après le lemme 1.4, pour tout $G \in [c]$, si la fonctionnelle $\Gamma$ est définie sur $G$, alors $\Gamma(G)$ est calculable.

Donc, si $G$ est suffisamment générique pour le forcing de Sacks, il est de degré minimal. $\blacksquare$

**Corollaire 1.6**

Il existe une classe parfaite d'ensembles, tous dans des degrés minimaux distincts.

PREUVE. On peut d'abord montrer qu'il existe un arbre parfait de degrés minimaux. Il suffit de procéder comme dans la preuve du théorème 8-5.1, afin de << dupliquer >> la construction d'un degré minimal. Avec le formalisme du forcing, soit $(D_n)_{n \in \mathbb{N}}$ une suite d'ensembles denses de conditions du forcing de Sacks, suffisante pour forcer un ensemble à être de degré minimal. On choisit $c_\epsilon \in D_0$, puis pour toute chaîne $\sigma$ de taille $n$, en supposant $c_\sigma \in D_n$ défini, on définit $c_{\sigma_0} \le c_\sigma$ et $c_{\sigma_1} \le c_\sigma$ de telle manière à ce que $[c_{\sigma_0}] \cap [c_{\sigma_1}] = \emptyset$. On pourra également faire en sorte que le premier nœud branchant de $c_{\sigma_i}$ étende strictement le premier nœud branchant de $c_\sigma$ pour $i \in \{0, 1\}$. L'arbre final est donné par l'ensemble des chaînes $\tau$ telles qu'il existe $X \in 2^N$ pour lequel $\tau \in \bigcap_{\sigma< X} c_\sigma$.

Une fois que l'on a un arbre parfait ne contenant que des degrés minimaux,
on peut se reporter à l'exercice 8-5.4 pour en extraire un sous-arbre parfait
ne contenant que des degrés deux à deux incomparables. $\blacksquare$

**1.2. Calcul d'un degré minimal**

Une analyse fine du niveau d'effectivité nécessaire pour mener à bien le théorème 1.5 montre qu'il existe un degré minimal $\emptyset''$-calculable. Il est en fait possible d'améliorer considérablement ce résultat, en remarquant que l'utilisation de f-arbres calculables n'est pas absolument nécessaire.
**Arbre c. e.**

Un f-arbre c. e. est une fonction partielle $T : 2^<N \to 2^<N$ telle que pour tout $\sigma$ tel que $T(\sigma) \downarrow$, soit $T(\sigma 0) \uparrow$ et $T(\sigma 1) \uparrow$, soit $T(\sigma 0) \downarrow \succeq T(\sigma)$ et $T(\sigma 1) \downarrow \succeq T(\sigma)$ avec $T(\sigma 0)$ et $T(\sigma 1)$ incomparables.

L'utilisation de f-arbres c. e. Γ-scindés ou Γ-unis permet de faire des constructions de degrés minimaux demandant moins de puissance de calcul. Il s'agit alors de constructions effectives qui ne relèvent plus à proprement parler du forcing. Nous listons sans les démontrer trois résultats importants qui utilisent ce nouveau type d'arbre pour calculer plus facilement des ensembles de degrés minimaux. Par « plus facilement », il faut comprendre « avec peu de puissance de calcul », les preuves étant elles au contraire, plus complexes...

**Théorème 1.7 (Sacks [185])**

Il existe un degré minimal sous $\emptyset'$.

Notons que, d'après la proposition 7-4.7, le résultat de Sacks implique l'existence d'un degré minimal de degré hyperimmune. Ce résultat a par la suite été amélioré par Yates [235], et indépendamment par Cooper [40].

**Théorème 1.8 (Yates [235], Cooper [40])**

Soit X un ensemble c. e. non calculable. Alors, X calcule un ensemble G de degré minimal.

Notons qu'un degré minimal ne peut en revanche jamais être c. e. : il s'agit d'une utilisation sophistiquée de la fameuse méthode des priorités, que nous avons vue dans le chapitre 13, et qui permet de montrer que tout ensemble c. e. non calculable A calcule un autre ensemble c. e. non calculable B qui ne le calcule pas A (voir le théorème 5.1 pour le résultat dans toute sa généralité).

Pour finir, signalons que Groszek et Slaman ont montré que tout degré PA pouvait calculer un degré minimal, via le remarquable résultat suivant.

**Théorème 1.9 (Groszek et Slaman [78])**

Tout degré PA calcul un degré minimal. Plus précisément, il existe une classe $\Pi_1^0$ non vide dont tous les membres sont soit de degré minimal, soit calculent un degré c. e. non calculable.

**Exercice 1.10. (*)** Montrer que toute classe $\Pi_1^0$ non vide contient un ensemble de même degré qu'un ensemble c. e. En déduire qu'il n'existe aucune classe $\Pi_1^0$ non vide ne contenant que des éléments de degrés minimaux. ◇
La possibilité de construire des degrés minimaux << complexes >> a également été très étudiée. Le principal résultat dans cette direction est le suivant.

**Théorème 1.11 (Kumabe [125])**

*Il existe un degré minimal qui est aussi DNC.*

Kumabe a d'abord montré l'existence d'un degré minimal et DNC, dans un article très complexe, qui ne fut jamais publié. La preuve fut ensuite retravaillée par Kumabe et Lewis [125], et la présentation en a par la suite été simplifiée par Khan et Miller [111], qui l'ont récrite sous le formalisme du forcing, via le *forcing avec arbres touffus*. L'exercice suivant montre qu'un degré minimal ne peut en revanche jamais être DNC₂.

**Exercice 1.12.** (⋆) Montrer qu'il existe une classe Π₀¹ non vide d'ensembles X ⊕ Y tels que X est de degré PA et Y et de degré PA relativement à X. En déduire qu'aucun ensemble PA n'est de degré minimal (le lecteur pourra consulter la proposition 24-2.4 pour une itération de ce résultat). ◇

**1.3. Relativisation : couverture minimale**

La construction d'un degré minimal avec le forcing sur les f-arbres se relativise à tout degré Turing dans le sens suivant.

**Définition 1.13.** Soient **a** et **b** des degrés Turing. On dit que **b** est une couverture minimale de **a** si **b** > **a** et s'il n'existe pas de degré **c** tel que **a** < **c** < **b**.

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

Autrement dit, **b** est une couverture minimale de **a** si c'est un élément minimal dans le cône des degrés Turing strictement au-dessus de **a**. La relativisation du théorème 1.5 montre le théorème suivant.

**Théorème 1.14**

*Tout degré Turing a une couverture minimale.*

*PREUVE.* Soit $A \subseteq \mathbb{N}$ un ensemble quelconque. L'objectif est de construire un ensemble $B >_T A$ tel que tout ensemble $C$ calculable par $B$ est soit $A$-calculable, soit tel que $A \oplus C \geq_T B$. Ainsi, si $B \geq_T C >_T A$, on aura bien $C \geq_T B$.

Il suffit de considérer une variante du forcing de Sacks, pour lequel nos f-arbres sont cette fois-ci $A$-calculables, et tels que chacun de leurs chemins calcule $A$. On pourra se restreindre par exemple aux f-arbres $A$-calculables tels que $A$ est encodé dans les bits pairs de chaque chemin du f-arbre.
Il suffit alors de répéter la preuve du théorème 1.5 avec ce nouvel ordre partiel, en remarquant la différence suivante : étant donné $T$ un f-arbre $\Gamma$-scindé, pour tout $X \in [T]$, on a à présent besoin de $A$ pour retrouver $X$ à partir de $\Gamma(X)$ : il nous faut en effet la connaissance de $T$. C'est la raison pour laquelle on aura $A \oplus \Gamma(X) \geq_T X$ et pas $\Gamma(X) \geq_T X$. ■

Notons qu'une couverture minimale **b** de **a** n'exclut pas l'existence de degrés **c** < **b** incomparables avec **a**. Cela nous amène à définir une notion de couverture plus forte.

**Définition 1.15.** Soient **a** et **b** deux degrés Turing. On dit que **b** est une couverture minimale forte de **a** si **b** > **a** et, si pour tout degré Turing **c** < **b**, on a **c** ≤ **a**. ◇

Comme déjà noté dans la preuve du théorème 1.14, la version relativisée du théorème 1.5 ne prouve pas l'existence d'une couverture minimale forte pour tout degré Turing, et pour cause : certains degrés n'admettent pas de couverture minimale forte, même si ce sera le cas pour beaucoup d'entre eux.

Ishmukhametov [95] a établi une élégante caractérisation des degrés c. e. admettant une couverture minimale forte.

**Théorème 1.16 (Ishmukhametov [95])**

Un ensemble c. e. $A \subseteq \mathbb{N}$ admet une couverture minimale forte si, et seulement si, toute fonction $A$-calculable $f: \mathbb{N} \to \mathbb{N}$ est bornée pour $n$ suffisamment grand par la fonction $n \mapsto \min\{s \in \mathbb{N} : \emptyset[f[s]]_n = \emptyset'[:n]\}$.

Une caractérisation générale des degrés admettant une couverture minimale forte est pour le moment inconnue, même si de nombreux résultats partiels ont été établis (voir Lewis [143]).

## 2. Nature de $\mathcal{D}$

À quoi ressemble l'ordre partiel ($\mathcal{D}$, ≤) ? Concernant sa taille d'abord, nous avons vu dans le présent ouvrage plusieurs constructions d'arbres parfaits dont chaque chemin est dans un degré Turing différent (voir par exemple l'exercice 7-5.8, l'exercice 8-5.3 ou l'exercice 8-5.4). Cela nous donne une injection de $2^\mathbb{N}$ dans $\mathcal{D}$. À l'aide de l'axiome du choix, on peut choisir un représentant dans chaque degré Turing, ce qui donne une injection de $\mathcal{D}$ dans $2^\mathbb{N}$. La cardinalité de $\mathcal{D}$ est donc $|2^\mathbb{N}|$, celle de $2^\mathbb{N}$. Notons que l'on ne peut pas nécessairement choisir un représentant dans chaque degré Turing
si l'on ne dispose pas de l'axiome du choix, et il n'en reste pas moins que
< moralement > $|2^N|$ est la cardinalité de $D$.

Étant donné un élément **a** ∈ **D**, l'ensemble des éléments sous **a** est au plus dénombrable puisqu'un ensemble ne peut calculer qu'une quantité dénombrable d'éléments. La cardinalité des éléments au-dessus de **a** est en revanche celle de $2^N$ : étant donné $A \in \mathbf{a}$, on peut facilement créer un arbre parfait dont les chemins sont tous de la forme $A \oplus X$ pour $X \in 2^N$, et tous dans des degrés Turing différents.

L'utilisation de la jointure Turing nous amène à la considération suivante :
étant donné deux ensembles $A$ et $B$, l'ensemble $A \oplus B$ calcule à la fois $A$
et $B$, et tout ensemble calculant à la fois $A$ et $B$ calcule $A \oplus B$. En termes
de degrés, cela implique que toute paire de degrés $a, b$ possède une borne
supérieure. Il y a donc un minimum de structure dans cet ordre partiel,
pour lequel nous introduisons le concept suivant.

**Définition 2.1.** Un treillis est un ensemble partiellement ordonné dans lequel toute paire d'éléments *a*, *b* admet une borne supérieure, notée *a* ∪ *b*, et une borne inférieure, notée *a* ∩ *b*. Un demi-treillis supérieur (resp. inférieur) est un ensemble ordonné pour lequel toute paire d'éléments admet une borne supérieure (resp. inférieure). ◇

Le paragraphe qui précède cette définition conduit au théorème ci-après,
lequel figure dans l'article fondateur de l'étude de la structure des degrés
Turing.

**Théorème 2.2 (Kleene et Post [118])**

L'ordre partiel ($\mathcal{D}, \leqslant$) est un demi-treillis supérieur de cardinalité $|2^N|$, avec un plus petit mais pas de plus grand élément, tel que chaque élément admet un ensemble au plus dénombrable d'éléments en dessous de lui et un ensemble de cardinalité $|2^N|$ d'éléments au-dessus de lui.

On calque parfois le vocabulaire des degrés Turing sur celui des ensembles qu'ils contiennent : étant donné deux degrés **a** et **b**, on dira que la borne supérieure **a** ∪ **b** de **a** et **b** est la jointure de **a**, **b**. Notons que dans un demi-treillis supérieur, toute suite finie d'éléments admet également une borne supérieure. En particulier, pour un ensemble fini de degrés **a**₁, ..., **a**ₙ, on la notera **a**₁ ∪ ... ∪ **a**ₙ, et elle sera le degré de la jointure A₁ ⊕ ... ⊕ Aₙ, pour des représentants quelconques Aᵢ ∈ **a**ᵢ.

Que se passe-t-il pour les ensembles dénombrables de degrés ? Le théorème suivant implique que si un tel ensemble est clos par jointure — c'est-à-dire que **a** ∪ **b** est dans notre ensemble pour tous **a**, **b** dans notre ensemble — et n'a pas d'élément maximal, alors il n'a jamais de borne supérieure.
### Théorème 2.3 (Sacks [188])

Tout ensemble dénombrable de degrés clos par jointure et sans élément maximal admet des majorants minimaux, en quantité $|2^N|$.

IDÉE DE LA PREUVE. Notons d'abord qu'un majorant d'un ensemble dénombrable de degrés $(a_n)_{n \in \mathbb{N}}$, est aussi majorant de

$$a_0 \le a_0 \cup a_1 \le a_0 \cup a_1 \cup a_2 \le \dots$$

Comme $(a_n)_{n \in \mathbb{N}}$ n'a pas d'élément maximal et qu'il est clos par jointure, on peut donc considérer sans perte de généralité que notre ensemble de degrés est tel que $a_n < a_{n+1}$. Pour tout $n$, soit $A_n$ un représentant de $a_n$.

Il suffit à présent d'élaborer sur le forcing de Sacks (voir la section 1) permettant de créer la couverture minimale d'un degré. On commence avec un f-arbre $A_0$-calculable dont tous les chemins calculent $A_0$. Une condition de forcing sera un f-arbre $A_n$-calculable dont tous les chemins calculent $A_n$ (pour un certain $n$). On étend une telle condition de forcing $T: 2^{<N} \to 2^{<N}$ au f-arbre $Q$ tel que $\mathrm{Im} Q \subseteq \mathrm{Im} T$ consiste en les chemins qui encodent $A_{n+1} \oplus X$ pour tout $X \in 2^N$. Formellement, pour toute chaîne $\sigma$ et tout $i \in \{0,1\}$, $Q(\sigma i) = T(A_{n+1} \upharpoonright_{|\sigma i|} \oplus \sigma i)$. Comme $A_{n+1} \ge T A_n$, alors $A_{n+1}$ peut calculer $T$, et donc retrouver $A_{n+1} \oplus X$ à partir du chemin de $Q$ qui encode $A_{n+1} \oplus X$ dans $T$.

La manière de faire une couverture minimale ne change pas, et la technique décrite dans la section 1 s'applique de la même manière. L'ensemble générique $G$ obtenu calculera chaque ensemble $A_n$, et sera tel que tout ce qui est calculé par $G$ et qui peut calculer chaque ensemble $A_n$ peut aussi calculer $G$.

Pour obtenir des majorants minimaux en quantité $|2^N|$, on peut construire un arbre parfait de majorants minimaux en subdivisant la construction en deux, puis chaque sous-construction en deux, etc., comme dans la preuve du théorème 8-5.1. ■

Un ensemble dénombrable de degrés clos par jointure et sans élément maximal a donc toujours deux majorants minimaux distincts, et l'on peut donc en déduire le corollaire suivant.

### Corollaire 2.4

Un ensemble dénombrable de degrés clos par jointure et sans élément maximal n'a jamais de borne supérieure.

Notons que pour une suite d'ensembles $(A_n)_{n \in \mathbb{N}}$, l'ensemble $\bigoplus_{n \in \mathbb{N}} A_n$ (voir la définition 10-3.24) n'est en général par un majorant minimal, comme en témoigne l'élégant résultat suivant.
**Théorème 2.5 (Enderton et Putnam [56], Sacks [190])**

Il existe un majorant minimal de $(\emptyset^{(n)})_{n \in \mathbb{N}}$ dont le double saut est dans le même degré Turing que celui de $\bigoplus_n \emptyset^{(n)}$.

**IDÉE DE LA PREUVE.** Pour une direction, il suffit de remarquer que le double saut de tout majorant de $(\emptyset^{(n)})_{n \in \mathbb{N}}$ permet de calculer $\bigoplus_n \emptyset^{(n)}$. Soit $B$ un majorant et soit $f$ une fonction calculable telle que $f(X') = X$ pour toute $X$ (voir l'exercice 4-6.4 pour plus de détails sur une telle fonction). À l'aide du double saut du majorant $B$, on cherche un code de fonctionnelle $e_1$ tel que $f(\Phi_{e_1}(B)) = \emptyset$, puis un code de fonctionnelle $e_2$ tel que $f(\Phi_{e_2}(B)) = \Phi_{e_1}(B)$, etc.

Pour l'autre direction, il suffit de voir que la construction d'une borne supérieure de $(\emptyset^{(n)})_{n \in \mathbb{N}}$ est effective à l'aide de $\bigoplus_n \emptyset^{(n)}$, et force à chaque étape une fonctionnelle $\Phi_e$ à être partielle ou bien totale sur tous les éléments de l'arbre considéré : on ne fait donc pas que calculer le générique résultant $G$, mais on peut aussi déterminer l'ensemble des codes de fonctionnelles totales sur $G$. Le double saut de $G$ se réduit à cet ensemble (voir l'exercice 5-7.2). ■

Nous répondons pour finir cette section à la question qui taraude peut-être le lecteur depuis le début de ce chapitre : la structure $(\mathcal{D}, \leq)$ est-elle un treillis ? Nous allons voir que non, et nous introduisons pour cela la notion de paire exacte.

**Définition 2.6.** Les degrés $\mathbf{a}, \mathbf{b}$ forment une paire exacte pour un ensemble de degrés $C \subseteq \mathcal{D}$ si $\mathbf{a}$ et $\mathbf{b}$ bornent chacun tous les degrés de $C$, et si chaque degré à la fois sous $\mathbf{a}$ et $\mathbf{b}$ est aussi borné par un degré de $C$. ♦

**Théorème 2.7**

Tout ensemble dénombrable de degrés $C$ clos par jointure admet une paire exacte.

**PREUVE.** Soit $(\mathbf{a}_n)_{n \in \mathbb{N}}$ un ensemble de degrés Turing clos par jointure. Pour tout $n$, soit $A_n$ un représentant de $\mathbf{a}_n$. L'idée est de construire deux ensembles $G_0 = \bigoplus_n X_n^0$ et $G_1 = \bigoplus_n X_n^1$ tels que chaque colonne $X_n^i$ pour $i \in \{0,1\}$ est égale à l'ensemble $A_n$, sauf pour un nombre fini de bits. Il est clair que de tels ensembles $G_0, G_1$ permettent de calculer tous les $A_n$. Il faut à présent les construire via un forcing adapté de telle manière à ce que si $G_0$ et $G_1$ calculent le même ensemble, alors cet ensemble est calculable par $A_0 \oplus A_1 \oplus \cdots \oplus A_m$ pour un certain $m$.

Nos conditions de forcing sont constituées de triplets

$$ (\sigma_0, \sigma_1, n), \text{ où } \sigma_0, \sigma_1 \in 2^{<\mathbb{N}} \text{ et } n \in \mathbb{N}. $$
Le paramètre *n* sert à contrôler les extensions possibles de nos conditions. On a ($\sigma_0, \sigma_1, n$) $\ge$ ($\tau_0, \tau_1, m$) pour deux conditions de forcing si $\sigma_0 \le \tau_0$, si $\sigma_1 \le \tau_1$, et si $n \le m$ avec la restriction que $\forall \langle k, a \rangle$ tel que $|\sigma_i| \le \langle k, a \rangle < |\tau_i|$ pour $k \le n$, on doit avoir $\tau_i(\langle k, a \rangle) = A_k(a)$. Étant donné un ensemble de conditions ($\sigma_0^0, \sigma_1^0, n_0$) $\ge$ ($\sigma_0^1, \sigma_1^1, n_1$) $\ge$ ($\sigma_0^2, \sigma_1^2, n_2$) $\ge \dots$, le générique $G_0$ sera le point limite de $\sigma_0^0 \le \sigma_0^1 \le \sigma_0^2 \le \dots$ et de générique $G_1$ sera le point limite de $\sigma_1^0 \le \sigma_1^1 \le \sigma_1^2 \le \dots$. Notons que la restriction sur les extensions possibles garantit que tant que la suite $n_0 \le n_1 \le n_2 \le \dots$ est non bornée, chaque *n*-ième colonne de $G_i$ sera bien égale à $A_n$, sauf pour un nombre fini de bits.

Pour toute paire de fonctionnelles $\Phi_{e_0}, \Phi_{e_1}$, on va forcer

$$ \Phi_{e_0}(G_0) = \Phi_{e_1}(G_1) = X \implies X \le T A_0 \oplus \dots \oplus A_n, \text{ pour un certain } n. $$

Notons que si $G_0$ et $G_1$ bornent le même degré il existe nécessairement deux fonctionnelles telles que $G_0$ et $G_1$ calculent le même ensemble dans ce degré. Une telle construction atteint donc bien nos objectifs.

On se donne une condition de forcing ($\sigma_0, \sigma_1, n$) et deux fonctionnelles $\Phi_{e_0}$ et $\Phi_{e_1}$. On cherche deux chaînes $\tau_0, \tau_1$ telles que ($\tau_0, \tau_1, n$) est une extension valide de ($\sigma_0, \sigma_1, n$), et telles que $\Phi_{e_0}(\tau_0, x) \downarrow \neq \Phi_{e_1}(\tau_1, x) \downarrow$ pour un certain $x$. Si cette recherche aboutit, on prend alors ($\tau_0, \tau_1, n$) comme extension de ($\sigma_0, \sigma_1, n$). Sinon, cela signifie que sur tout $x$, les calculs $\Phi_{e_0}(\tau_0, x)$ et $\Phi_{e_1}(\tau_1, x)$, quand ils s'arrêtent, renvoient la même valeur pour toute extension valide ($\tau_0, \tau_1, n$) $\le$ ($\sigma_0, \sigma_1, n$).

Notons que par définition de ce qu'est une extension valide de ($\sigma_0, \sigma_1, n$), il est possible de les énumérer à l'aide de $A_0 \oplus \dots \oplus A_n$. Si pour tout $x$ il existe une extension valide ($\tau_0, \tau_1, n$) telle que $\Phi_{e_0}(\tau_0, x) \downarrow$ ou $\Phi_{e_1}(\tau_1, x) \downarrow$ alors on peut calculer via $A_0 \oplus \dots \oplus A_n$ l'unique élément $Z$ ainsi potentiellement calculable par n'importe quel générique $G_0$ via $\Phi_{e_0}$ ou par n'importe quel générique $G_1$ via $\Phi_{e_1}$. Sinon, au moins un des deux calculs $\Phi_{e_0}(G_0, x)$ ou $\Phi_{e_1}(G_1, x)$ sera partiel sur un certain $x$.

Si donc $G_0, G_1$ sont suffisamment génériques pour ce forcing, pour toutes fonctionnelles $\Phi_{e_0}, \Phi_{e_1}$, on aura

$$ \Phi_{e_0}(G_0) = \Phi_{e_1}(G_1) = X \implies X \le T A_0 \oplus \dots \oplus A_n, \text{ pour un certain } n. $$

Il s'ensuit que $G_0, G_1$ est une paire exacte pour les degrés $(a_n)_{n \in \mathbb{N}}$.

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

On peut à présent en déduire que $(D, \le)$ n'est pas un treillis.

## Théorème 2.8 (Kleene et Post [118])

Le demi-treillis supérieur $D$ n'est pas un treillis : il y a des degrés $a, b$ qui n'ont pas de borne inférieure.
PREUVE. Il suffit de considérer un ensemble de degrés $c_0 < c_1 < c_2 < \dots$ nécessairement clos par jointure. Cet ensemble de degrés admet donc une paire exacte **a**, **b**. Une telle paire exacte n'a pas de borne inférieure puisque tout degré à la fois sous **a** et **b** est également sous un degré $c_n$, pour un certain $n$. ■

## 3. Universalité de $\mathcal{D}$

Nous voyons dans cette section que ($\mathcal{D}$, $\leqslant$) présente une certaine universalité, en ce sens que tous les ordres partiels peuvent se plonger dans $\mathcal{D}$, sauf ceux qui ne peuvent y prétendre pour des raisons de cardinalité.

**Définition 3.1.** Un ordre partiel $(A, \leqslant)$ se plonge dans $(\mathcal{D}, \leqslant)$ s'il existe une injection $f: A \to \mathcal{D}$ telle que $a \leqslant b$ ssi $f(a) \leqslant f(b)$. $\diamond$

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

La structure ($\mathcal{D}$, $\leqslant$) contient donc en elle tous les ordres partiels qui ne sont pas plus gros qu'elle. Cette affirmation, qui sera rendue précise, est en fait un peu fausse : il reste une question ouverte à ce sujet, que nous mentionnerons bientôt. Notons que cela ne nous renseigne pas nécessairement sur la complexité calculatoire de $\mathcal{D}$. Considérons par exemple l'ordre calculable partiel $\leqslant_R \subseteq \mathbb{Q}^2 \times \mathbb{Q}^2$ défini par $(p_1, p_2) \leqslant_R (q_1, q_2)$ si $p_1 \leqslant q_1$ et $p_2 \leqslant q_2$ pour $p_1, p_2, q_1, q_1 \in \mathbb{Q}$. Il n'est pas très difficile de montrer que tout ordre partiel dénombrable se plonge dans $(\mathbb{Q}^2, \leqslant_R)$. La construction d'un plongement se fait sans difficulté, en construisant l'injection de manière gloutonne élément par élément sans jamais violer à chaque étape finie les contraintes d'un plongement. La structure $(\mathbb{Q}^2, \leqslant_R)$ n'est pas calculatoirement complexe, mais elle est suffisamment riche en termes de possibilités pour contemnir tous les ordres partiels.

Nous utiliserons à plusieurs reprises l'existence d'ensembles dit calculatoirement indépendants.

**Définition 3.2.** Des ensembles $(X_n)_{n \in \mathbb{N}}$ sont calculatoirement indépendants si $X_i \not\leq_T \bigoplus_{j \neq i} X_j$ pour tout $i \in \mathbb{N}$. $\diamond$

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

L'existence d'ensembles calculatoirement indépendants ne présente pas de difficultés particulières et l'on peut se référer à l'exercice 10-3.25 pour voir que si $G = \bigoplus_n G_n$ est un ensemble 1-générique, alors les ensembles $(G_n)_{n \in \mathbb{N}}$ sont calculatoirement indépendants.

### 3.1. Plongements dans $\mathcal{D}$

Voyons tout de suite ce qui fut annoncé, sous la forme d'un premier théorème.
**Théorème 3.3 (Sacks [188])**

Tout ordre partiel dénombrable se plonge dans les degrés Turing.

PREUVE. Nous avons vu dans l'introduction de cette section que tout ordre partiel dénombrable peut se plonger dans la structure $(\mathbb{Q}^2, \leq_R)$ définie par $(p_1, p_2) \leq_R (q_1, q_2)$ si $p_1 \leq q_1$ et $p_2 \leq q_2$.

Il suffit alors de montrer que $(\mathbb{Q}^2, \leq_R)$ se plonge dans $(\mathcal{D}, \leq)$. Soit $(X_n)_{n \in \mathbb{N}}$ une suite d'ensembles calculatoirement indépendants, et soit $(a_n)_{n \in \mathbb{N}}$ une énumération calculable des éléments de $\mathbb{Q}^2$. Le plongement $f$ assigne à l'élément $a_n$ le degré Turing de l'ensemble $\bigoplus_{a_m \leq_R a_n} X_m$. On vérifie sans peine $a_n \leq_R a_m$ ssi $f(a_n) \leq f(a_m)$. ■

Sacks a par la suite cherché à étendre son résultat à de plus gros ordres partiels. Après tout, $(\mathcal{D}, \leq)$ admet pour cardinalité $|2^\mathbb{N}|$. On ne peut bien sûr pas attendre de tout ordre partiel de cardinalité $|2^\mathbb{N}|$ qu'il se plonge dans $(\mathcal{D}, \leq)$ : si un élément dans un ordre partiel a une quantité indénombrable de prédécesseurs, il n'y a aucun espoir de construire un plongement de cet ordre vers $\mathcal{D}$ puisque chaque élément de $\mathcal{D}$ n'en a qu'une quantité dénombrable. On doit donc respecter cette restriction, mais y en a-t-il d'autres ? Nous avons besoin ici d'anticiper un peu sur les ordinaux qui seront introduits dans le chapitre 27, et en particulier sur l'ordinal $\omega_1$, le plus petit ordinal infini non dénombrable. Sacks a obtenu les résultats suivants.

**Théorème 3.4 (Sacks [186])**

N'importe quel ordre partiel avec une des propriétés suivantes peut se plonger dans les degrés Turing :

1. l'ordre est de cardinalité $|2^\mathbb{N}|$, et chaque élément a une quantité finie de prédécesseurs;

2. l'ordre est de cardinalité $|\omega_1|$, et chaque élément a une quantité au plus dénombrable de prédécesseurs;

3. l'ordre est de cardinalité $|2^\mathbb{N}|$, et chaque élément a une quantité au plus dénombrable de prédécesseurs, ainsi qu'une quantité d'au plus $\omega_1$ successeurs.

En particulier, si l'on fait l'hypothèse du continu, à savoir $|\omega_1| = |2^\mathbb{N}|$, le théorème de Sacks est optimal : tout ordre partiel de cardinalité $|2^\mathbb{N}|$, et où chaque élément a une quantité au plus dénombrable de prédécesseurs, peut se plonger dans les degrés Turing. Mais, si l'on n'utilise pas l'hypothèse du continu, la question est toujours ouverte.

**Question 3.5.** Peut-on plonger dans $(\mathcal{D}, \leq)$ tout ordre partiel de cardinalité $|2^\mathbb{N}|$, où chaque élément a une quantité dénombrable de prédécesseurs ?★
Si nous ne présentons pas ici la preuve de Sacks, nous en voyons néanmoins deux ingrédients, via la notion de chaîne et d'anti-chaîne.

**Définition 3.6.** Un ensemble de degrés Turing linéairement ordonné est une *chaîne*. Un ensemble de degrés Turing deux à deux incomparables est une *anti-chaîne*.

**Proposition 3.7 (Sacks [188]).**

(1) Chaque chaîne dénombrable peut être étendue dans les degrés Turing. En particulier, toute chaîne maximale est de cardinalité $\omega_1$.

(2) Chaque anti-chaîne de cardinalité inférieure à $|2^N|$ peut être étendue dans les degrés Turing. En particulier, toute anti-chaîne maximale est de cardinalité $|2^N|$.

PREUVE.

(1) Si la chaîne possède un plus grand élément, on peut considérer son saut Turing. Sinon, on peut considérer le degré de la jointure Turing d'un représentant de chacun de ses éléments.

(2) Soit $D$ l'ensemble des degrés minimaux. Par le corollaire 1.6, $D$ est de cardinalité $|2^N|$. Soit $C$ une anti-chaîne de degrés Turing de cardinalité inférieure à $|2^N|$. Chaque élément de $C$ a une quantité au plus dénombrable d'éléments en dessous de lui. Ainsi, la clôture par le bas de $C$ a la même cardinalité que $C$. Il doit donc exister un élément de $d \in D$ qui n'est calculé par aucun élément de $C$. Comme $d$ est un degré minimal, il ne peut borner aucun élément de $C$. On en déduit que $C \cup \{d\}$ est une anti-chaîne.

## 3.2. Extension de plongements de $\mathcal{D}$

La notion de plongement peut être considérée comme faible, en particulier car elle ne dit rien sur les relations qu'entretiennent les degrés dans l'image d'un plongement, avec les degrés qui ne sont pas dans cette image. Une manière de pallier cette faiblesse est de considérer un plongement déjà existant d'une structure $(C, \leq)$ vers les degrés Turing, et d'essayer de voir dans quelle mesure ce plongement peut se prolonger à une extension de l'ordre partiel sur $C$. Une telle chose n'est bien entendue pas toujours possible : si des éléments $a_0, a_1, b \in C$, avec $a_0 < b, a_1 < b$ et $a_0, a_1$ incomparables, sont envoyés sur des degrés $a_0, a_1$ et $a_0 \cup a_1$, alors un tel plongement ne pourra se prolonger à aucun majorant $c < b$ de $a_0, a_1$. On introduit pour cela la notion d'extension consistante.
**Définition 3.8.** Soit $C$ un demi-treillis supérieur et soit $D \supseteq C$. Alors, $D$ est une extension consistante de $C$ si :

(1) pour $a, b < d$ avec $a, b \in C$ et $d \in D \setminus C$, on a $a \cup b < d$;

(2) aucun élément de $D \setminus C$ n'est sous un élément de $C$.

Notons que, comme $C$ est un demi-treillis supérieur, $a \cup b \in C$ pour
tous $a, b \in C$. ◇

**Théorème 3.9 (Kleene et Post [118])**

Soit $C$ un demi-treillis supérieur fini, et soit $D$ une extension consistante
finie de $C$. Alors, tout plongement $f$ de $(C, \leqslant)$ dans $(\mathcal{D}, \leqslant)$ peut être
étendu en un plongement de $(D, \leqslant)$ dans $(\mathcal{D}, \leqslant)$.

PREUVE. Soit $f$ un plongement de $(C, \leqslant)$ dans $(\mathcal{D}, \leqslant)$. On notera $\mathbf{a}$ l'image de $a \in C$ par $f$. Soit $a \in D \setminus C$ minimal dans $D \setminus C$. Comme $D$ est une extension consistante, alors $C$ peut être partitionné en une liste d'éléments $(b_i)_{i \leqslant n}$ et $(c_i)_{i \leqslant m}$ telle que $b_0 \cup \dots \cup b_n < a$, telle que $a$ est incomparable avec chaque $c_i$ et telle que $b_0 \cup \dots \cup b_n$ n'est au-dessus d'aucun $c_i$. Il suffit alors de construire un degré Turing $\mathbf{a}$ tel que $b_0 \cup \dots \cup b_n < \mathbf{a}$ et tel que $\mathbf{a}$ soit incomparable avec chaque $c_i$.

En utilisant le fait que $\mathbf{b}_0 \cup \dots \cup \mathbf{b}_n$ n'est au-dessus d'aucun $\mathbf{c}_i$, on construit facilement par extensions finies un degré $\mathbf{d}$ tel que $\mathbf{d} \cup \mathbf{b}_0 \cup \dots \cup \mathbf{b}_n$ ne soit au-dessus d'aucun $\mathbf{c}_i$ et tel que $\mathbf{b}_0 \cup \dots \cup \mathbf{b}_n$ ne soit pas au-dessus de $\mathbf{d}$. Le plongement se prolonge alors en envoyant $a$ sur $\mathbf{d} \cup \mathbf{b}_0 \cup \dots \cup \mathbf{b}_n$. Par minimalité du choix de $a$, l'ensemble $D - \{a\}$ est à présent une extension consistante de la clôture de $C \cup \{a\}$ en demi-treillis supérieur. On peut donc recommencer jusqu'à assignation de chaque élément de $D$. ■

Nous verrons avec le lemme 4.2 que la réciproque du théorème fonctionne :
il est nécessaire d'être une extension consistante pour que tout plongement
soit extensible. Le théorème précédent peut être étendu comme suit.

**Théorème 3.10 (Sacks [186])**

Soit $C$ un demi-treillis supérieur dénombrable, et soit $f$ un plongement de $(C, \leqslant)$ dans $(\mathcal{D}, \leqslant)$. Soit $D$ une extension consistante et dénombrable de $C$. Alors, $f$ peut être étendu en un plongement de $(D, \leqslant)$ dans $(\mathcal{D}, \leqslant)$.

**3.3. Segments initiaux de D**

Une autre manière de renforcer l'étude des plongements possibles, est de
considérer les plongements sur des *segments initiaux* de $\mathcal{D}$
**Définition 3.11.** Un segment initial de $\mathcal{D}$ est un ensemble de degrés clos par le bas. Un segment final est un ensemble de degrés clos par le haut. $\diamond$

Un plongement sur un segment initial nous donne une information complète sur tous les degrés qui se trouvent en dessous de ceux de l'image du plongement. Par exemple, la construction d'un degré minimal nous indique que l'ordre $a < b$ de deux éléments $a,b$ peut se plonger sur un segment initial de $\mathcal{D}$. L'existence d'un degré minimal avec une couverture minimale forte (voir la définition 1.15) nous indique que l'ordre $a < b < c$ de trois éléments $a,b,c$ peut se plonger sur un segment initial de $\mathcal{D}$. En élaborant sur la construction des degrés minimaux, Lachlan et Lebeuf ont obtenu le remarquable résultat suivant.

**Théorème 3.12 (Lachlan et Lebeuf [133])**

Un ordre partiel dénombrable se plonge sur un segment initial de $(\mathcal{D}, \leqslant)$ si, et seulement si, c'est un demi-treillis supérieur avec un plus petit élément.

La preuve de Lachlan et Lebeuf se fait petit à petit, l'étape la plus difficile étant de le montrer pour tout demi-treillis supérieur fini avec un plus petit élément. Il s'agit d'une modification non triviale de la construction de degrés minimaux. Considérons par exemple l'ordre partiel en diamant donné par $a \leqslant b_1$, $a \leqslant b_2$, $b_1, b_2 \leqslant c$ et $b_1, b_2$ incomparables. Il s'agit alors de construire deux degrés minimaux $\mathbf{b}_1, \mathbf{b}_2$, tels que $\mathbf{b}_1 \cup \mathbf{b}_2 = \mathbf{c}$, et tels que $\mathbf{b}_1, \mathbf{b}_2$ sont les seuls degrés non calculables se trouvant sous $\mathbf{c}$. Une telle construction repose sur un forcing avec des f-arbres calculables dits *uniformes*, comme expliqué dans la section 1.1. On peut par exemple construire avec un tel forcing un ensemble $X = X_0 \oplus X_1$ tel que $X_0$ et $X_1$ sont incomparables et minimaux, et tel que tout ce qui est calculé par $X$ est soit sous $X_0$, soit sous $X_1$, soit peut recalculer $X$. La preuve détaillée peut être consultée dans [169] ou [138].

Notons que le théorème de Lachlan et Lebeuf donne une caractérisation complète des idéaux Turing de la forme $\mathcal{D}(\leqslant \mathbf{a})$ pour un certain degré $\mathbf{a}$ (i.e. l'ensemble des éléments qui se trouvent sous $\mathbf{a}$) : il s'agit des demi-treillis supérieurs au plus dénombrables ayant un plus petit et un plus grand élément. En fait, ce théorème peut être poussé un peu plus loin.

**Théorème 3.13 (Abraham et Shore [2])**

Un ordre partiel de cardinalité $|\omega_1|$ est isomorphe à un segment initial de $(\mathcal{D}, \leqslant)$ ssi c'est un demi-treillis supérieur avec un plus petit élément, et dans lequel chaque élément a une quantité au plus dénombrable de prédécesseurs.
En particulier, si l'on fait l'hypothèse du continu, cela caractérise complètement les segments initiaux possibles de ($\mathcal{D}$, $\leq$). Si l'on ne fait pas l'hypothèse du continu, alors les choses se compliquent.

**Théorème 3.14 (Groszek et Slaman [77])**

Il existe un modèle de ZFC, dans lequel il existe un ordre partiel indénombrable avec un plus petit élément et pour lequel chaque élément a un nombre fini de prédécesseurs, qui ne peut se plonger comme segment initial de ($\mathcal{D}$, $\leq$).

# 4. Théorie du premier ordre de $\mathcal{D}$

Nous abordons à présent la complexité de $\mathcal{D}$. La question qui nous intéresse est la suivante : étant donné un énoncé du premier ordre qui porte sur les degrés Turing, peut-on décider si ce dernier est vérifié ou non ? Le langage que nous pouvons utiliser est uniquement constitué des relations $\leq$, $<$ ou $=$, mais il sera possible d'étendre ce langage à tout ce qui est définissable avec $\leq$, $<$ ou $=$. Par exemple $0$, le degré minimal, est définissable comme étant l'unique degré qui satisfait la formule $F(\mathbf{x}) = \forall \mathbf{y} \ \mathbf{x} \leq \mathbf{y}$. On peut alors par exemple exprimer l'existence d'un degré minimal de la manière suivante : $\exists \mathbf{x} (0 < \mathbf{x} \land \forall \mathbf{y} \ \mathbf{x} \leq \mathbf{y} (\mathbf{y} = 0 \lor \mathbf{y} = \mathbf{x}))$. Le fait que $0$ soit définissable par la formule $F(\mathbf{x})$ permet de s'en passer dans une formule équivalente :

$$ \exists \mathbf{z} (F(\mathbf{z}) \land \exists \mathbf{x} (\mathbf{z} < \mathbf{x} \land \forall \mathbf{y} \ \mathbf{x} \leq \mathbf{y} (\mathbf{y} = \mathbf{z} \lor \mathbf{y} = \mathbf{x}))) $$

C'est bien entendu plus long, et l'on s'autorisera donc ces extensions de langage. On utilisera notamment la fonction à deux arguments $\cup$ qui nous donne la jointure de deux degrés, et qui est elle aussi définissable par la formule

$$ F(\mathbf{x}, \mathbf{y}, \mathbf{z}) = \mathbf{x} \leq \mathbf{z} \land \mathbf{y} \leq \mathbf{z} \land \forall \mathbf{a} \ ((\mathbf{x} \leq \mathbf{a} \land \mathbf{y} \leq \mathbf{a}) \to \mathbf{z} \leq \mathbf{a}). $$

On vérifie sans peine que pour tout $\mathbf{a}, \mathbf{b} \in \mathcal{D}$, le degré $\mathbf{a} \cup \mathbf{b}$ est l'unique degré $\mathbf{z}$ tel que $F(\mathbf{a}, \mathbf{b}, \mathbf{z})$.

Revenons à présent à notre question : étant donné un énoncé sur les degrés Turing, peut-on décider si ce dernier est vrai ou faux ? La question est $\mathbf{a}$ *priori* d'une grande complexité si on l'aborde directement : un énoncé du type $\exists \mathbf{a}$ revient à un énoncé du type « existe-t-il un ensemble $X$ tel que $\mathbf{a}$. Il s'agit d'une quantification du second ordre, c'est-à-dire portant non pas sur les entiers, mais sur les ensembles d'entiers. Ce genre de quantification sera abordé en détail dans la partie IV. Les énoncés avec des quantifications sur les entiers étant déjà indécidables, il y a fort à parier que ce soit aussi le cas pour les énoncés sur les degrés Turing. On peut néanmoins montrer que si la formule est du type $\forall \exists$ ou du type $\exists \forall$, on peut alors décider si elle est vrai ou fausse. Cela constitue notre premier théorème sur le sujet.
**Théorème 4.1 (Lerman [138] (théorème 4.4) et Shore [199])**

La théorie $Π_2^0$ de $(\mathcal{D}, \leq)$, c'est-à-dire l'ensemble des énoncés $Π_2^0$ vrais dans $(\mathcal{D}, \leq)$, est décidable.

Pour montrer le théorème précédent, il suffit essentiellement de voir que la réciproque du théorème 3.9 est vraie.

**Lemme 4.2.** Soit $C$ un demi-treillis supérieur fini, et soit $D$ une extension finie de $C$. Alors, $D$ est une extension consistante si, et seulement si, tout plongement $f$ de $(C, \leq)$ dans $(\mathcal{D}, \leq)$ peut être étendu en un plongement de $(D, \leq)$ dans $(\mathcal{D}, \leq)$. $\star$

**PREUVE.** Le théorème 3.9 nous donne une direction du lemme. Supposons à présent que $D$ ne soit pas une extension consistante de $C$. Si un élément de $d \in D$ est tel que $a, b \leq d$ mais $a \cup b \not\leq d$, il suffit de considérer un plongement qui associe $a \cup b$ à $a \cup b$. Il sera alors impossible d'étendre un tel plongement à $D$. Supposons à présent qu'un degré de $D$ se trouve sous un degré de $C$. Par le théorème 3.12, il existe un plongement de $C$ sur un segment initial de $\mathcal{D}$. Là encore, un tel plongement ne pourra pas être étendu à un degré inférieur à un degré de $C$. $\blacksquare$

Nous avons à présent l'ingrédient nécessaire pour montrer le théorème 4.1 :

**PREUVE DU THÉORÈME 4.1.** Soit un énoncé de la forme

$$ \forall c_1, \dots, \forall c_n \exists d_1, \dots, d_m F(c_1, \dots, c_n, d_1, \dots, d_m), $$

où $F$ est une combinaison booléenne de formules atomiques. Soit $C$ l'ensemble fini des modèles possibles de demi-treillis supérieurs générés par les $c_i$ et compatibles avec les conditions données par $F$. Si $C$ est vide, alors la formule n'est pas satisfaite, sans même considérer la partie de $F$ mentionnant les $d_i$. Sinon, pour tous les modèles de $C$, on vérifie si ce modèle peut être complété de manière compatible avec les conditions données par $F$, et de telle manière à ce que les $d_i$ en soient une extension consistante. Si tel est le cas, la formule est vraie, et sinon elle est fausse. $\blacksquare$

Il s'agit là de la limite de ce qui est décidable. Lachlan [130] a montré que la théorie $Π_3^0$ ne l'était plus.

**Théorème 4.3 (Schmerl — voir corollaire 4.6 de [138])**

La théorie $Π_3^0$ de $(\mathcal{D}, \leq)$ est indécidable.

À quel point la théorie de $(\mathcal{D}, \leq)$ est-elle complexe ? Peut-on par exemple la décider à l'aide du saut Turing, ou encore à l'aide de la réunion disjointe
de toutes les itérations finies du saut Turing ? Nous allons voir que non :
la théorie de ($\mathcal{D}$, $\leq$) est de complexité *maximale*. Qu'entendons-nous par
là ? Considérons $T_2$, la théorie du second-ordre de ($\mathbb{N}$, $\times$, $+, 0, 1$), c'est-à-dire
l'ensemble des formules du second ordre qui sont vraies dans $\mathbb{N}$. On rappelle
qu'une formule du second ordre est de la forme $\forall X \exists Y \dots F(X, Y, \dots)$ où
les variables $X, Y, \dots$ sont des ensembles d'entiers, et où $F$ est une formule
du premier ordre, paramétrée par ces ensembles.

La théorie $T_2$ est donc l'ensemble des formules du second ordre qui sont
vraies dans $\mathbb{N}$. Si l'on a accès à $T_2$, on peut savoir si une formule de la
théorie du premier ordre de ($\mathcal{D}$, $\leq$) est vraie : les quantifications $\exists a$ et $\forall a$
peuvent se remplacer par des quantifications sur les éléments de $2^\mathbb{N}$ et,
à l'aide du théorème 9-3.4 relativisé aux paramètres du second ordre —
lequel permet de transformer un prédicat $\Sigma_n^0(X, Y, \dots)$ en une formule $\Sigma_n$
de l'arithmétique—, on peut transformer une formule du premier ordre $F$
de ($\mathcal{D}$, $\leq$) en une formule de second ordre équivalente $F^*$ de ($\mathbb{N}$, $\times$, $+, 0, 1$).
Simpson a montré que l'inverse était vrai aussi : via un codage ingénieux, il
est possible de transformer une formule de l'arithmétique du second ordre
en une formule équivalente de ($\mathcal{D}$, $\leq$).

Insistons avant d'aller plus loin sur la complexité *extrême* de $T_2$. Nous étudierons dans la partie IV tous les détails de la complexité de $T_2$ restreinte aux formules $\Pi_1^1$, c'est-à-dire restreinte aux formules au sein desquelles les quantifications du second ordre sont toutes universelles. Nous verrons que cette théorie a déjà un degré Turing considérablement élevé comparé à $\emptyset'$ ou même à toutes les itérations finies de $\emptyset'$. Ce degré Turing est néanmoins bien défini, et il est *absolu* dans le sens où la valeur de vérité d'une formule $\Pi_1^1$ sera la même dans les modèles transitifs de la théorie des ensembles partageant les mêmes ordinaux calculables (voir la partie IV pour une définition formelle). À partir du niveau de complexité $\Pi_2^1$ des formules, ce sens devient plus flou. La valeur de vérité de ce genre de formule restera toutefois inchangée dans tous les modèles transitifs de la théorie des ensembles qui partagent cette fois non pas les même ordinaux calculables, mais les même ordinaux dénombrables. Sous réserve d'accepter l'absoluité des ordinaux dénombrables, la vérité des formules $\Pi_2^1$ est elle aussi absolue. Le degré Turing du niveau $\Pi_2^1$ de $T_2$ est quant à lui plus élevé que tous les degrés Turing abordés dans le présent livre (il s'agit en quelque sorte du supremum de tous les singletons $\Pi_1^1$, dont nous verrons la définition dans la section 30-4). La valeur de vérité d'une formule $\Pi_3^1$ pourra quant à elle différer entre deux modèles de ZFC qui partagent les mêmes ordinaux, et le sens qu'il y a à dire qu'une telle formule est *vraie* ou *fausse* s'évanouit ici encore un peu plus. Quant au degré Turing de la théorie $\Pi_3^1$ de $T_2$, de là où nous sommes, c'est-à-dire le monde des choses calculables, depuis lequel
nous observons la structure de l'univers, même les meilleurs télescopes ne permettent pas de le voir : il est tout simplement trop éloigné de nous.

Voilà donc la complexité de la théorie des degrés Turing ! Nous livrons ci-après la preuve moderne du théorème de Simpson, qui diffère de celle qui fut originellement produite, et qui présente son intérêt propre. Le résultat de Simpson découle du théorème suivant, où $n \in \mathbb{N}$.

**Théorème 4.4 (Slaman et Woodin [206])**

Tout sous-ensemble dénombrable $R \subseteq \mathcal{D}^n$ de $n$-uplets de degrés Turing est uniformément définissable dans $(\mathcal{D}, \leq)$ avec un nombre fini de paramètres. Formellement, il existe une formule $F(x_1, ..., x_n, y_1, ..., y_m)$ telle que, pour tout $R \subseteq \mathcal{D}^n$, il existe des paramètres $\mathbf{p}_1, ..., \mathbf{p}_m \in \mathcal{D}$ pour lesquels $(\mathbf{a}_1, ..., \mathbf{a}_n) \in \mathcal{D}$ si, et seulement si, $F(\mathbf{a}_1, ..., \mathbf{a}_n, \mathbf{p}_1, ..., \mathbf{p}_m)$ est vrai dans $(\mathcal{D}, \leq)$.

Voyons tout de suite comment utiliser le théorème 4.4 pour montrer le théorème de Simpson : il suffit de coder un modèle standard de l'arithmétique dans les degrés Turing.

**Théorème 4.5 (Simpson [201])**

La théorie du premier ordre des degrés Turing est many-one équivalente à celle de l'arithmétique du second ordre.

*PREUVE.* Nous avons déjà vu dans les paragraphes précédents comment transformer un énoncé de $(\mathcal{D}, \leq)$ en un énoncé équivalent de l'arithmétique du second ordre. Voyons à présent comment faire l'inverse.

L'idée est de coder un modèle standard de $(\mathbb{N}, +, \times, 0, 1)$ dans les degrés Turing. Un tel modèle sera codé par un ensemble fini de paramètres codant pour un ensemble $N$ de degrés Turing qui représentent $\mathbb{N}$, avec un degré spécifique représentant 0 et un autre représentant 1. Les relations $+$ et $\times$ sont elles aussi codées par un ensemble fini de paramètres.

Il est possible de créer une formule de $\mathcal{D}$ qui vérifie si un ensemble fini de paramètres code bien pour le modèle standard de l'arithmétique : il s'agit simplement de vérifier les axiomes de l'arithmétique de Robinson (voir la section 9-2.3), lesquels sont en nombre fini, et de vérifier ensuite que tout sous-ensemble du modèle possède un plus petit élément. On peut se reporter au théorème 9-3.13 pour voir que ces conditions sont nécessaires et suffisantes pour vérifier que l'on a bien affaire au modèle standard des entiers. La quantification universelle ≪ tout sous-ensemble du modèle possède un plus petit élément » peut être remplacée par une quantification universelle sur les degrés Turing utilisés comme paramètres pour coder des sous-ensembles de $N$ (notre ensemble de degrés qui représente $\mathbb{N}$).
Étant donné une formule $F$ de l'arithmétique du second ordre, on peut finalement la transformer en une formule équivalente $F^*$ dans $\mathcal{D}$, en remplaçant les quantifications sur les ensembles par des quantifications sur les paramètres codant pour ces ensembles. La formule du second ordre de l'arithmétique sera donc interprétée dans $\mathcal{D}$ par la formule : il existe des paramètres codant pour un modèle standard de l'arithmétique, tel que $F^*$ est vérifiée dans ce modèle. ■

Passons à présent au codage de Slaman et Woodin. Le lemme qui suit constitue la partie difficile de la preuve. Il repose sur un forcing qui peut sembler relativement simple dans son principe, mais dont l'exécution s'avère délicate et demande pas mal d'astuce pour être menée à bien.

**Lemme 4.6 (Slaman et Woodin [206]).** Toute anti-chaîne dénombrable dans les degrés Turing est uniformément définissable avec trois paramètres. ★

**PREUVE.** Soit $(\mathbf{a}_n)_{n \in \mathbb{N}}$ une anti-chaîne dans les degrés Turing, et soit $\mathbf{b}$ un majorant de cette anti-chaîne. Nous allons définir deux degrés $g_0, g_1$ tels que pour tout degré $\mathbf{y} \le \mathbf{b}$ ne majorant aucun $\mathbf{a}_i$, alors $g_0 \cup \mathbf{y}$ et $g_1 \cup \mathbf{y}$ ont une borne inférieure, et cette borne inférieure est $\mathbf{y}$. En d'autre termes, tout degré à la fois sous $g_0 \cup \mathbf{y}$ et sous $g_1 \cup \mathbf{y}$ doit aussi être sous $\mathbf{y}$. À l'inverse, il existera pour tout $i$ un degré à la fois sous $g_0 \cup \mathbf{a}_i$ et sous $g_1 \cup \mathbf{a}_i$ qui ne sera pas sous $\mathbf{a}_i$. Il s'ensuit que chaque $\mathbf{a}_i$ sera un élément minimal satisfaisant la formule

$$F(\mathbf{x}) = \mathbf{x} \le \mathbf{b} \wedge \exists \mathbf{c} \ (\mathbf{c} \not\le \mathbf{x} \wedge \mathbf{c} \le g_0 \cup \mathbf{x} \wedge \mathbf{c} \le g_1 \cup \mathbf{x}).$$

En particulier, les degrés $\mathbf{a}_i$ seront exactement les degrés $\mathbf{x}$ satisfaisant la formule $F(\mathbf{x}) \wedge \forall \mathbf{y} \le \mathbf{x} \neg F(\mathbf{y})$. Le fait que les $\mathbf{a}_i$ forment une anti-chaîne est utilisé uniquement pour les définir comme solutions minimales de $F$, mais n'intervient plus par la suite.

Nous utiliserons pour la construction des degrés $g_0$ et $g_1$ le fait suivant : tout degré Turing contient un ensemble $X$ calculable en n'importe quel sous-ensemble infini de $X$. On peut le voir de la manière suivante : étant donné un ensemble $Y$ quelconque, on définit $X$ comme étant l'ensemble des préfixes $\sigma < Y$, via un codage des chaînes finies par des entiers.

Soit $B$ un représentant de $\mathbf{b}$ et, pour tout $n$, soit $A_n$ un représentant de $\mathbf{a}_n$ calculable en n'importe lequel de ses sous-ensembles infinis. Nous allons définir deux ensembles $G_0, G_1$ tels que pour tout $i$ il existe $C \not\le_T A_i$ tel que $C \le_T G_0 \oplus A_i$ et $C \le_T G_1 \oplus A_i$, et tel que pour tout $Y \le_T B$ et tout $D$ tel que $D \le_T G_0 \oplus Y$ et $D \le_T G_1 \oplus Y$, alors $Y \ge_T D$ ou bien $Y \ge_T A_j$ pour un certain $j$.

On procède à cet effet via un forcing qui présente des similarités avec celui du théorème 2.7.
Soit $\mathbb{P}$ l'ensemble de conditions de la forme $(\sigma_0, \sigma_1, n)$ pour $\sigma_0, \sigma_1 \in 2^{<\mathbb{N}}$, avec $|\sigma_0| = |\sigma_1|$ et $n \in \mathbb{N}$. L'entier $n$ sert à restreindre les extensions possibles, la chaîne $\sigma_0$ est utilisée pour le premier générique $G_0$ et la chaîne $\sigma_1$ pour le deuxième générique $G_1$. Tout comme dans la preuve du théorème 2.7, on peut voir $G_0$ et $G_1$ comme étant construits par colonne. L'entier $n$ indique que la construction sera dorénavant restreinte sur les $n$ premières colonnes : pour une colonne $k \le n$, si $a \notin A_k$, il n'y a alors aucune restriction pour le bit $\langle k, a \rangle$ des deux génériques. Si en revanche $a \in A_k$, alors le bit $\langle k, a \rangle$ des deux génériques doit être identique (sans nécessairement être égal à $A_k(a)$).

Formellement, $(\sigma_0, \sigma_1, n) \succeq (\tau_0, \tau_1, m)$ si $\sigma_0 \preceq \tau_0$, si $\sigma_1 \succeq \tau_1$, si $n \le m$, et si de plus la condition suivante est vérifiée : pour tout $k \le n$, alors pour tout $a \in A_k$ tel que $|\sigma_i| \le \langle k, a \rangle < |\tau_i|$, les valeurs $\tau_0(\langle k, a \rangle)$ et $\tau_1(\langle k, a \rangle)$ doivent être les mêmes.

Considérons $G_0, G_1$ deux ensembles suffisamment génériques pour ce forcing. Pour chaque $A_n$, et pour $a \in A_n$ suffisamment grand, on aura

$$G_0(\langle n, a \rangle) = G_1(\langle n, a \rangle),$$

par définition de ce qu'est une extension valide dans ce forcing. En particulier ; les ensembles $X_0^n, X_1^n \subseteq A_n$ définis par $X_i^n(a) = 0$ si $a \notin A_n$, et $X_i^n(a) = G_i(\langle n, a \rangle)$ sinon, sont les mêmes sauf pour un nombre fini de bits, et sont donc tous les deux calculés par $G_0 \oplus A_n$ et $G_1 \oplus A_n$.

Montrons que si $G_0, G_1$ sont suffisamment génériques, alors aucun $A_n$ ne peut calculer les ensembles $X_0^n, X_1^n$ ainsi définis. Étant donné une condition $\langle \sigma_0, \sigma_1, n \rangle$, on peut prendre n'importe quelle extension pour le côté $\sigma_0$, ce qui force alors certains bits de l'extension pour l'autre côté. En considérant le fait qu'il y a nécessairement des sous-ensembles infinis de $A_n$ non calculables en $A_n$, on peut nécessairement trouver une extension $\tau_0 \succeq \sigma_0$ telle que pour une fonctionnelle $\Phi_e$ donnée, $\Phi_e(A_n)$ ne produise jamais la restriction de $\tau_0$ qui sera faite pour en faire un préfixe de $X_0^n$ — soit parce que $\Phi_e(A_n)$ sera partielle, soit parce qu'elle produira une chaîne incompatible avec le préfixe de $X_0^n$ ainsi forcé. Comme $X_1^n$ coïncide avec $X_0^n$ sauf sur un nombre fini de bits, alors $A_n$ ne calculera pas non plus $X_1^n$. Cela nous donne la première partie de ce que l'on cherche à montrer : pour tout $A_n$, il existe un ensemble calculable en $G_0 \oplus A_n$ et en $G_1 \oplus A_n$, mais pas en $A_n$.

Il reste à montrer que pour tout $Y \leqslant_T B$ tel que $Y$ ne calcule aucun $A_n$, si $G_0 \oplus Y$ et $G_1 \oplus Y$ calculent un même ensemble $C$, alors $Y \geqslant_T C$. Soit alors $p = (\sigma_0, \sigma_1, n)$ une condition et soient $\Phi_{e_0}, \Phi_{e_1}$ une paire de fonctionnelles. On sépare dans un premier temps la chaîne $\sigma_0$ de notre condition $p$. S'il existe $x$ et $\tau_0 \succeq \sigma_0$ tels que pour tout $\rho_0 \succeq \tau_0$ on a $\Phi_{e_0}(Y \oplus \rho_0, x) \uparrow$, on considère alors une chaîne $\tau_1$ telle que la condition $(\tau_0, \tau_1, n)$ forme une extension valide, pour laquelle on aura forcé la partialité de $\Phi_{e_0}(Y \oplus G_0)$.
Supposons à présent que pour tout $x$ et pour tout $\tau_0 \succeq \sigma_0$ il existe $\rho_0 \succeq \tau_0$ tel que $\Phi_{e_0}(Y \oplus \rho_0, x) \downarrow$. Supposons dans un premier temps qu'il existe une extension $\tau \succeq \sigma_0$ telle que, pour toutes extensions $\rho_0, \rho_1 \succeq \tau$ et pour tout $x$, on ait $\Phi_{e_0}(Y \oplus \rho_0, x) \downarrow = a$ et $\Phi_{e_0}(Y \oplus \rho_1, x) \downarrow = b$ impliquent $a = b$. Alors, on ne peut produire qu'un unique ensemble via $\Phi_{e_0}(Y \oplus G_0)$ pour un générique $G_0$ quelconque, et cet ensemble est calculable alors en $Y$. On force donc $\Phi_{e_0}(Y \oplus G_0)$ à calculer quelque chose qui est déjà calculable en $Y$. Supposons finalement que, pour tout $\tau \succeq \sigma_0$, il existe $\rho_0, \rho_1 \succeq \tau$ et $x$ tels que $\Phi_{e_0}(Y \oplus \rho_0, x) \downarrow \neq \Phi_{e_0}(Y \oplus \rho_1, x) \downarrow$. Le lemme suivant s'avère utile.

**Lemme 4.7.** Pour tout $\tau \succeq \sigma$, il existe $x$ et deux extensions $\rho_0, \rho_1 \succeq \tau$ qui diffèrent sur seulement un bit et tels que

$$ \Phi_{e_0}(Y \oplus \rho_0, x) \downarrow = a \neq \Phi_{e_0}(Y \oplus \rho_1, x) \downarrow = b. $$

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

**PREUVE.** Il suffit de trouver deux extensions de $\tau$ de même taille et incompatibles sur un certain $x$. Soient $i_0, \dots, i_k$ les bits sur lesquelles ces extensions different. On inverse le bit $i_0$ dans la première extension, et on l'étend pour obtenir une valeur $a_0$ pour $x$. Si $a_0 \neq a$, on a terminé. Sinon, on inverse à son tour $i_1$ dans cette nouvelle extension, que l'on étend encore pour obtenir une valeur $a_1$, et ainsi de suite. Si chaque valeur $a_1 = a_2 = \dots = a_{k-1}$, alors $a_{k-1} \neq b$, et notre chaîne diffère maintenant d'un seul bit de celle qui a produit $b$. ■

On se sert du lemme précédent pour calculer à l'aide de $Y$ une suite de quadruplets $(\tau_{0,m}, \tau_{1,m}, i_m, x_m)_{m \in \mathbb{N}}$ avec $i_m < i_{m+1}$ telle que, pour tout $m$, les chaînes $\tau_{0,m}, \tau_{1,m}$ different sur exactement le bit $i_m$ et soient incompatibles sur $x_n$. La suite de bits $(i_m)_{m \in \mathbb{N}}$ est une suite infinie et $Y$-calculable. Rappeons que notre condition de forcing est de la forme $(\sigma_0, \sigma_1, n)$. S'il existe $i_m$ tel que $i_m = \langle k, a \rangle$ pour $k > m$, cela entraîne que pour toute extension $\tau'$ de $\sigma_1$ telle que $\langle \tau_{0,m}, \tau', n \rangle$ est une extension valide, alors $\langle \tau_{1,m}, \tau', n \rangle$ en est aussi une, car il n'y a aucune contrainte sur le bit $i_m$. On peut donc trouver une extension de $\tau'$ de $\sigma_1$ qui force une valeur pour $x_n$ (à supposer que l'on ne puisse pas forcer la partialité de ce côté là), et l'on prend l'extension $\tau_{0,m}$ ou $\tau_{1,m}$ de $\sigma_0$ qui force une valeur différente. On force donc $\Phi_{e_0}(Y \oplus G_0)$ et $\Phi_{e_1}(Y \oplus G_1)$ à être différents.

Si à présent il n'existe pas $i_m = \langle k, a \rangle$ pour $k > m$, alors il doit exister par le principe des tiroirs un certain $k \leqslant m$ pour lequel une infinité de $i_m$ est de la forme $\langle k, a \rangle$. Aussi n'est-il pas possible d'avoir $A_k(a) = 1$ pour chacun de ces $i_m$, car on aurait alors un sous-ensemble infini de $A_k$ et $Y$-calculable, or par hypothèse tout sous-ensemble infini de $A_k$ calcule $A_k$, et $Y$ ne calcule pas $A_k$. Il doit donc exister $\tau_{0,m}, \tau_{1,m}$ et $i_m = \langle k, a \rangle$ tel que $A_k(a) = 0$. Là encore, toute extension $\tau'$ de $\sigma_1$ qui est compatible avec $\tau_{0,m}$ le sera aussi avec $\tau_{1,m}$, car il n'y a aucune contrainte sur le bit $i_m$. On peut alors trouver
une extension $\tau'$ de $\sigma_1$ qui force une valeur sur $x_m$ — à moins que l'on ne puisse forcer la partialité de ce côté là— et choisir une extension parmi $\tau_{0,m}$ et $\tau_{1,m}$ qui force une autre valeur sur $x_m$. Cela conclut la preuve. ■

Et voilà. La preuve du lemme ne fut pas sans difficulté, mais nous sommes à présent presque au bout de nos peines. Montrons finalement que tout sous-ensemble dénombrable de $\mathcal{D}^n$ peut être codé dans les degrés Turing.

**PREUVE DU THÉORÈME 4.4.** Dans ce qui suit, les variables en majuscule dénotent des ensembles ou suites de degrés Turing. Soit un ensemble dénombrable de $n$-uplets $R \subseteq \mathcal{D}^n$. Soit $\mathbf{b}$ un majorant sur l'ensemble des degrés concernés par $R$ (c'est-à-dire sur la réunion des projections de $R$ sur chaque coordonnée), et soit $(\mathbf{x}_i)_{i \in \mathbb{N}}$ une liste de tous les degrés sous $\mathbf{b}$. Notons que $\mathbf{b}$ n'est qu'un majorant, et que certains $\mathbf{x}_i$ peuvent donc ne pas être des degrés du $n$-uplet $R$.

On trouve alors une anti-chaîne $(c_i^k)_{k \le n, i \in \mathbb{N}}$ telle que $B = (c_i^k \cup \mathbf{x}_i)_{k \le n, i \in \mathbb{N}}$ forme un ensemble de degrés calculatoirement indépendants (on montre sans peine qu'une telle anti-chaîne existe, par extensions finies). Pour $k \le n$ fixé, soit $C_k = (c_i^k)_{i \in \mathbb{N}}$. On définit finalement

$$S = \{ \mathbf{c}_{i_1}^1 \cup \mathbf{x}_{i_1} \cup \dots \cup \mathbf{c}_{i_n}^n \cup \mathbf{x}_{i_n} : (\mathbf{x}_{i_1}, \dots, \mathbf{x}_{i_n}) \in R \}.$$

Comme $B$ est calculatoirement indépendant, il existe pour tout $\mathbf{a} \in S$ un $n$-uplet de degrés $\mathbf{b}_1, \dots, \mathbf{b}_n \in B$, unique à l'ordre près, tel que

$$\mathbf{a} = \mathbf{b}_1 \cup \dots \cup \mathbf{b}_n.$$

Par ailleurs, l'indépendance calculatoire de $B$ garantit également que pour le degré $\mathbf{b}_1$ il existe un unique $i \le n$ tel que $\mathbf{b}_1 = \mathbf{c}_m^i \cup \mathbf{x}_m$ pour un certain $m$, et ce $m$ est lui aussi unique. Il en va de même pour $\mathbf{b}_2, \mathbf{b}_3, \dots$, ce qui permet de définir $R$ de la manière suivante : $(\mathbf{x}_1, \dots, \mathbf{x}_n) \in R$ si

$$\mathbf{x}_1 \le \mathbf{b} \wedge \dots \wedge \mathbf{x}_n \le \mathbf{b} \wedge \exists \mathbf{y}_1 \in C_1 \dots \exists \mathbf{y}_n \in C_n (\mathbf{x}_1 \cup \mathbf{y}_1) \cup \dots \cup (\mathbf{x}_n \cup \mathbf{y}_n) \in S.$$

Comme chaque $C_i$ et comme $S$ sont des anti-chaînes, elles sont définissables d'après le lemme 4.6. Une telle formule est donc définissable dans les degrés Turing. ■

Slaman et Woodin ont utilisé leur technique de codage comme point de départ à une étude complexe de la *rigidité* des degrés Turing. Une structure est dite *rigide* si elle n'admet pas d'automorphisme autre que l'identité, c'est-à-dire dans le cas des degrés, de bijection on triviale $f: \mathcal{D} \to \mathcal{D}$ telle que $\mathbf{a} \le \mathbf{b} \leftrightarrow f(\mathbf{a}) \le f(\mathbf{b})$. Par exemple, la structure $(\mathbb{R}, +, \times, \le)$ des réels est une structure rigide. Étant donné un automorphisme $f: \mathbb{R} \to \mathbb{R}$, on doit avoir $f(0) + f(1) = f(1)$ et donc $f(0) = 0$, puis $f(1) = f(1) \times f(1)$
et donc $f(1) = 1$. En utilisant $f(n + 1) = f(n) + 1$, on montre que $f$ est nécessairement l'identité sur $\mathbb{N}$, et l'on montre la même chose sur $\mathbb{Q}$ en jouant de la multiplication. Comme $f$ conserve les carrés, $f$ est croissante. On utilise alors pour terminer le fait que tout nombre réel est limite d'une paire de suites adjacentes de nombres rationnels, si bien que $f$ est forcément l'identité sur $\mathbb{R}$.

Peut-on faire quelque chose de similaire dans les degrés Turing ou bien
peut-on << échanger >> deux degrés **a** et **b**, et étendre cet échange de manière
consistante en un automorphisme sur $\mathcal{D}$ ? La question reste pour le moment
ouverte, même si Slaman et Woodin en ont, comme on va le voir derechef,
considérablement réduit les possibilités.

**Théorème 4.8 (Slaman et Woodin [207])**

Tout automorphisme sur les degrés Turing est l'identité sur $\mathcal{D}(\ge 0'')$.

Slaman et Woodin utilisent ce résultat pour montrer dans le même article
que la fonction de double saut est définissable dans les degrés Turing. Ce
résultat sera étendu plus tard par Shore et Slaman.

Théorème 4.9 (Shore et Slaman [200])

Le saut *Turing* est définissable dans les degrés *Turing*, sans paramètres.

Ce résultat peut alors à son tour être utilisé pour montrer que tout automorphisme sur les degrés Turing est l'identité sur $\mathcal{D}(\ge 0')$.

La question suivante reste toutefois ouverte.

**Question 4.10.** Existe-t-il un automorphisme autre que l'identité sur les degrés Turing ? ★

**5. Structure des degrés c. e.**

Un autre champ de recherche important dans les degrés Turing consiste à
en restreindre l'étude à un sous-ensemble. Dans cet ordre d'idée, l'étude
de la structure ($\mathcal{R}, \leqslant$) des degrés c. e. est certainement la plus développée.
Nous faisons ici un résumé rapide des principaux résultats les concernant.

Commençons tout de suite par l'impressionnant théorème de densité de
Sacks, qui se montre au terme de ce qui est certainement l'une des méthodes
de priorité à blessure infinie les plus complexes.
**Théorème 5.1 (Sacks (1964))**

L'ordre $(\mathcal{R}, \leq)$ est dense : étant donné des ensembles c. e. $A <_T B$, il existe un ensemble c. e. $C$ tel que $A <_T C <_T B$.

La structure des degrés c. e. apparaît donc bien différente de celle des degrés Turing. Il y a tout de même des similarités : on vérifie ainsi sans problème que toute paire d'éléments admet une borne supérieure, l'ensemble $A \oplus B$ étant c. e. si $A$ et $B$ sont tous les deux c. e. Tout comme dans les degrés Turing, on peut montrer — en élaborant sur la construction de deux degrés incomparables — qu'il existe un ensemble dénombrable de degrés c. e. calculatoirement indépendants [164]. Tout comme pour les degrés Turing, on peut en déduire que tout ordre partiel dénombrable se plonge dans les degrés c. e., ce qui montre comme l'a remarqué Sacks que la théorie $\Pi_1^0$ des degrés c. e. est décidable.

**Théorème 5.2 (Sacks [188])**

La théorie $\Pi_1^0$ des degrés c. e. est décidable.

Étant donné une formule existentielle sur les degrés c. e., il suffit de vérifier si elle est compatible avec les axiomes d'un ordre partiel. Si tel est le cas elle est vraie, sinon elle est fausse.

Tout comme pour les degrés Turing, la question du plongement n'est pas vraiment satisfaisante en soi. Une question plus intéressante est celle du plongement de treillis, tel que les bornes supérieures sont envoyées vers les bornes supérieures, et les bornes inférieures sur les bornes inférieures. Les plongements de treillis mentionnés dorénavant seront considérés comme vérifiant cette contrainte. L'existence d'une paire minimale de degrés c. e. montre par exemple que le treillis en diamant généré par $c_0, c_1$ incomparables (c'est-à-dire avec $c_0 \cap c_1 < c_0$, $c_1 < c_0 \cup c_1$) peut se plonger de cette manière dans les degrés Turing, la borne inférieure étant le degré 0.

La construction effective d'une paire minimale de degrés c. e. (voir le théorème 13-5.2) a été exploitée pour montrer des résultats bien plus forts. Un treillis est dit *distributif* si $a \cap (b \cup c) = (a \cup b) \cap (a \cup c)$.

**Théorème 5.3 (Thomason [223] Lachlan et Lerman)**

Tout treillis distributif dénombrable peut se plonger dans les degrés c. e.

En ce qui concerne les treillis non distributifs, certains peuvent se plonger dans les degrés c. e. [131] et d'autres pas [134]. Aucune caractérisation n'est connue à ce jour.
Nous avons vu que la théorie des degrés Turing est de complexité maximale, il en va de même pour celle des degrés c. e. qui a la même complexité que la théorie constituée des formules vraies de l'arithmétique du premier ordre. Le premier résultat dans cette direction a été obtenu par Harrington et Shelah [83], qui ont montré que la théorie du premier ordre des degrés c. e. était indécidable. La preuve fut ensuite simplifiée et améliorée par Harrington et Slaman, puis par Nies, Shore et Slaman [168], qui ont montré le théorème suivant.

**Théorème 5.4 (Nies, Shore et Slaman [168])**

On peut transformer effectivement un énoncé $F$ de l'arithmétique du premier ordre en énoncé $F^*$ sur les degrés c. e., tel que :

$F$ est vrai dans $(\mathbb{N}, + , \times, 0, 1)$ si, et seulement si, $F^*$ est vrai dans $(\mathcal{R}, \leq)$.

Pour finir, Lempp, Nies et Slaman [137] ont montré que la théorie $Π_3^0$ des degrés c. e. était déjà indécidable, ce qui laisse ouverte la question suivante.

**Question 5.5.** La théorie $Π_2^0$ des degrés c. e. est-elle décidable ? ★
Deuxième partie

Aléatoire algorithmique
<figure><img src="image_104.png" /></figure>
Chapitre
15

Introduction

Nous avons abordé dans la section 10-2
une notion de typicité des ensembles qui
découle directement du travail de Baire :
être générique. Il est peu dire que ces no-
tions d'ensembles maigres et co-maigres
se sont révélées être d'une grande uti-
lité, et ce dans de multiples domaines :
analyse, théorie des ensembles, relations
d'équivalence, calculabilité, etc.

Et pourtant, si la fécondité des travaux
de René Baire est exceptionnelle, celle
des travaux de son collègue Henri Le-
besgue est encore au-dessus. Les deux
mathématiciens se connaissaient très
bien et ont étudié auprès du même pro-
fesseur —en l'occurrence Émile Borel —
dont la carrière brillante fait écho à celle
de ses deux élèves.

<figure><img src="image_105.png" /><figcaption>Henri Lebesgue, 1875-1941</figcaption></figure>

Lebesgue travaille sur la théorie de la mesure, ce qui conduira à une no-
tion de typicité orthogonale à celle de Baire : être aléatoire. La théorie de
la mesure peut être utilisée de manière similaire à celle des catégories de
Baire, pour des problématiques communes : par exemple, les points de dis-
continuité d'une fonction limite de fonctions continues forment une classe
maigre. Dans l'espace de Cantor, il s'agit d'une conséquence de la preuve
du théorème 10-3.20 : si G est 1-générique, alors le saut Turing est continu
en $G$. On montre quelque chose de similaire pour la mesure : soit $f$ une fonction limite de fonctions continues, il existe des ensembles fermés de mesure arbitrairement grande, sur lesquels la restriction de $f$ est continue. Ce sera une conséquence, dans l'espace de Cantor, de la preuve du théorème 19-3.8. La théorie de la mesure doit enfin sa renommée à l'utilisation qui en est faite pour axiomatiser la théorie des probabilités. Ainsi, un ensemble typique pour la théorie de la mesure peut être informellement vu comme un ensemble « aléatoire », c'est-à-dire qui satisfait toutes les propriétés qu'un ensemble vérifie avec probabilité 1.

L'étude des nombres aléatoires est aussi une manière d'étudier des nombres individuellement « inaccessibles », mais qui révèlent beaucoup de secrets quand on considère plutôt les groupes auxquels ils appartiennent. Cette intuition se trouve déjà chez Borel dans les années 1950. Aussi citons-nous pour illustrer notre propos un passage de son ouvrage « Les nombres inaccessibles » :

> « Toutes les théories qui se rattachent à la mesure des ensembles peuvent donc être considérées comme une contribution à la théorie des nombres inaccessibles; si nous ne pouvons étudier individuellement aucun de ces nombres, nous pouvons étudier des problèmes de probabilité qui sont relatifs, soit à l'ensemble de ces nombres, soit à certains sous-ensembles. La réponse à certaines questions se trouve être ainsi un coefficient de probabilité. Une telle réponse peut avoir souvent un grand intérêt dans bien des questions scientifiques. »

En calculabilité, cela nous amène à ce que l'on appelle aujourd'hui l'aléatoire algorithmique, un domaine qui est né d'une question d'ordre philosophique, en apparence simple : qu'est-ce qu'une suite de 0 et de 1 aléatoire ? Plus précisément, étant donné une suite de 0 et de 1, est-il « raisonnable » de penser qu'elle ait pu être obtenue par un tirage à pile ou face ?

Nous avons bien entendu une intuition sur la question : par exemple, la suite 0000000000000 semble moins aléatoire que la suite 01101001010010. Mais comment donner un sens précis à cette intuition ? D'autant que quand on y réfléchit, chacune des deux suites ci-dessus a exactement la même probabilité d'apparition (de $2^{-14}$). Pourtant, obtenir la deuxième avec un tirage à pile ou face apparaîtra parfaitement normal, alors qu'obtenir la première semblera extraordinaire. Nous avons en effet l'intuition qu'un nombre aléatoire — on entend ici par « nombre » un réel $r \in ]0,1[$, vu comme une suite infinie de 0 et de 1 via sa représentation binaire— devrait satisfaire la loi des grands nombres : la fréquence de 1 doit être la même que la fréquence de 0 c'est-à-dire 1/2. En poussant plus loin, on peut aussi demander que la fréquence de 00,01,10 et 11 soit la même, à savoir 1/4, et ainsi de suite pour toutes suites finies de bits. Émile Borel appelle de tels
nombres des *nombres normaux*, et a montré qu'un nombre est normal avec
probabilité 1. Mais est-ce suffisant pour considérer qu'un nombre puisse
être le résultat d'un tirage aléatoire de ses bits ? La réponse est non, et l'on
peut utiliser pour aller dans ce sens un résultat de Champernowne [32], qui
a montré que la suite obtenue en concatenant tous les entiers écrits en bi-
naire dans l'ordre, est un nombre normal : 0 1 10 11 100 101 110 111 ... Il
est clair en revanche que ce nombre n'a rien d'aléatoire, car il est calculable
par un procédé très simple, alors qu'un nombre aléatoire ne devrait pas
être calculable : imaginez un algorithme prédisant les numéros du loto, ou
la prochaine carte qui serait retournée au cours d'une partie de Blackjack ?
Ce serait la fin des casinos. Notons au passage que les différentes machines
électroniques de jeu de hasard ont recours à des processus physiques couplés
à des algorithmes de génération aléatoire, afin justement qu'un joueur ne
puisse pas << prédire l'avenir >> avec un simple calcul.

La première tentative de définir formellement le caractère aléatoire d'une
suite infinie de bits est en général attribuée à Richard von Mises, qui en 1919
propose la définition suivante : une suite est aléatoire si chacune de ses sous-
suites infinies, obtenable par un << processus de sélection raisonnable >>,
satisfait la loi des grands nombres. La calculabilité qui se développa peu
après nous offre un cadre naturel pour définir formellement ce que doit être
un processus de sélection raisonnable : simplement un processus calculable.
En 1939, Jean Ville démontra dans sa thèse << Étude critique de la notion
de collectif >> [228] que la définition de von Mises était insuffisante : pour
n'importe quel ensemble dénombrable de règles de sélection, il existe des
suites qui sont aléatoires au sens de von Mises, mais dont chaque préfixe
contient plus de 0 que de 1. Il est effectivement très improbable de tirer 1000
fois de suite à pile ou face, en ayant constamment plus de pile que de face.
Quand le nombre de tirages s'étend vers l'infini, cette probabilité tombe à 0.
On pourrait envisager d'étendre l'idée de von Mises et demander à ce que
les sous-suites sélectionnées ne satisfassent pas seulement la loi des grands
nombres, mais aussi d'autres lois qui sont satisfaites avec probabilité 1.
Mais quelles lois choisir ? En fait, si l'on en fixe un nombre fini $L_1, ..., L_n$,
il n'y a aucune raison de croire que l'on ne pourra pas trouver une suite
dont toutes les sous-suites calculables satisfont chacune de ces lois, tout en
échappant à une $(n+1)$-ième.

C'est en 1966 que Martin-Löf proposa la définition qui fait encore aujourd'hui consensus comme étant une définition << satisfaisante >> d'aléatoire : il considère toutes les lois $\Pi_2^0$ qui sont satisfaites avec probabilité 1, en remarquant qu'avec l'ajout d'une certaine condition sur les $\Pi_2^0$ en question, ceux-ci peuvent se combiner en une seule loi universelle. Un peu plus tard Chaitin [29], Gács [69] et Levin [142] ont tous les trois indépendamment
et presque simultanément introduit une définition de l’aléatoire algorith-
mique via un paradigme complètement différent, en l’occurrence celui de
la compressibilité, en utilisant une version spéciale de la complexité de
Kolmogorov. Par la suite, Levin [141] et Schnorr [193] ont démontré que la
définition d’aléatoire de Martin-Löf coïncidait celle de Chaitin/Gács/Levin,
révélant alors la robustesse de cette notion, pour laquelle on trouva par la
suite bon nombre d’autres caractérisations.

Les notions de compressibilité et de complexité de Kolmorogov permettent
une transition en douceur de la calculabilité vers l'étude de l'aléatoire, et
c'est donc par là que nous commencerons.
Chapitre 16

Complexité de Kolmogorov et
nombres aléatoires

Andrei Nikolaïevitch Kolmogorov (1903 - 1987) est certainement l'un des mathématiciens les plus fameux et les plus profi ques de l'école de Moscou, fondée par Dmitri Egorov et Nikolaï Luzin au début du XXe siècle, et dont nous aurons l'occasion de reparler dans la section 29-1. À l'issue de sa thèse en 1929, effectuée sous la direction de Luzin, Kolmogorov a déjà publié de nombreux articles et acquis une renommée internationale. Il devient en 1931 professeur à l'université de Moscou et y mènera une brillante carrière durant laquelle il participera à la fondation de pans entiers des mathématiques modernes.

Ses travaux les plus connus concernent
sans aucun doute l'axiomatisation, en 1933,
de la théorie des probabilités [10], dont nous reparlerons dans le chapitre 17.
Trente ans plus tard, Kolmogorov a des contributions importantes en topo-
logie, en théorie des systèmes dynamiques, et a participé à la résolution du
treizième problème de Hilbert. Sa carrière n'est pas terminée pour autant.
Il est alors sur le point de démarrer un autre champ d'étude mathématique

<figure><img src="image_106.png" /><figcaption>Andreï Nikolaïevitch Kolmo-
gorov, 1903–1987</figcaption></figure>
qui connaîtra une fois de plus un retentissement considérable : la théorie
algorithmique de l’aléatoire, complémentaire de la théorie des probabilités,
avec cette fois l’utilisation d’un outil nouveau, l’informatique. Il développe
notamment sa notion de complexité éponyme, dont nous nous efforcerons
au long de ce chapitre de montrer la richesse.

1. Complexité de Kolmogorov

Informellement, la complexité de Kolmogorov d'un objet fini est une mesure
de la quantité d'information nécessaire pour calculer cet objet. Si Kolmo-
gorov [121] fut le premier à publier sur le sujet, cette idée remonte en fait
aux travaux de Solomonoff [209].

**Définition 1.1.** On appelle *Machine* une fonction partielle calculable de $2^{<N}$ vers $2^{<N}$. La *complexité de Kolmogorov de σ relativement à M*, notée $C_M(\sigma)$, est la longueur de la plus petite chaîne $\tau$ telle que $M(\tau) = \sigma$. Formellement, $C_M(\sigma) = \min\{|\tau| : M(\tau) = \sigma\}$. ◇

La complexité de Kolmogorov d'une chaîne relativement à une machine M peut être vue comme une mesure de sa compression maximale possible via M. C'est donc une notion relative, qui dépend de la machine qui est utilisée, et si la machine en question ne fait rien, la notion n'est pas très intéressante. L'idée est bien sûr d'utiliser des machines qui compressent au maximum l'information.

1.1. Machine universelle

C'est Solomonoff le premier qui comprend la possibilité de définir une ma-
chine optimale, que l'on appelle aussi universelle : une machine dont le
taux de compression sera au moins aussi bon que celui de n'importe quelle
autre machine, à constante près.

**Définition 1.2.** Une machine $U$ est dite *universelle* si, pour toute machine $M$, il existe une constante $c_M \in \mathbb{N}$ telle que $C_U(\sigma) \le C_M(\sigma) + c_M$, pour toute chaîne $\sigma$. $\diamond$

Une machine universelle compresse donc aussi bien que n'importe quelle
autre machine M, mais à une certaine constante additive près c_M. Évidem-
ment, si la constante est grande par rapport à la chaîne que l'on veut
compresser, la notion perd de sa force, mais le point important est que
la constante ne dépend que de la machine M et non de la chaîne que l'on
veut compresser. Le poids de cette constante s'amenuise donc à mesure que
la taille des chaînes considérées augmente. En introduisant son concept de
machine universelle, Solomonoff a bien évidemment montré qu'une telle
machine existait, ce qui a aussi été démontré indépendamment par Kolmo-
gorov.

Théorème 1.3 (Solomonoff [210], Kolmogorov [122])

Il existe une machine universelle.

PREUVE. Soit $(M_e)_{e \in \mathbb{N}}$ une énumération des machines, c'est-à-dire que $M_e$ est la machine de code $e$. il suffit de définir la fonction calculable

$$
U : 2^{<N} \rightarrow 2^{<N}
$$

qui sur la chaîne 0^e1σ renvoie la valeur de M_e(σ). Étant donné une ma-
chine M_e, il est clair que, pour toute chaîne σ, on a

$$
C_U(\sigma) \le C_{M_e}(\sigma) + (e + 1).
$$

■

Notation

On fixe dès à présent une machine universelle U, et l'on note C(σ) la
valeur C_U(σ). Dès lors, C(σ) sera la complexité de Kolmogorov de σ.

Remarquons que la machine universelle que nous avons fixée n'a pas d'im-
portance : à constante additive près, toutes les machines universelles com-
pressent les chaînes de manière optimale, et tous les théorèmes qui vont
suivre sont indépendants du choix de celle-ci.

1.2. Les chaînes aléatoires

L'idée d'utilisation de la complexité de Kolmogorov comme mesure d'aléa-
toire est simple : moins une chaîne est compressible, plus elle est aléatoire.
On montre facilement que des chaînes incompressibles de toutes les tailles
existent.

**Proposition 1.4.** Pour tout $n$, il existe une chaîne $\sigma$ de taille $n$ telle que $C(\sigma) \ge n$. $\star$

*

PREUVE. Il s'agit d'un simple argument de comptage : $U$ est une fonction, et associe donc à une chaîne au plus une autre chaîne. Aussi, pour tout $n$, le nombre de chaînes de taille strictement inférieure à $n$ est de $\sum_{i=0}^{n-1} 2^i = 2^n - 1$. Il existe donc au moins une chaîne de taille $n$ qui n'est calculée via $U$ par aucune chaîne de taille strictement inférieure à $n$. $\blacksquare$

■

Nous nous intéresserons dans la suite aux chaînes incompressibles à cons-
tante près : si une chaîne de taille 10 000 est compressible par un programme
de taille 9990, mais pas mieux, elle peut être moralement considérée comme
« fortement » aléatoire. L'importance de cette constante s'effacera complètement quand nous poursuivrons dans la section 2 notre étude de l'aléatoire sur les préfixes d'objets infinis.

## 1.3. Le degré Turing de la complexité de Kolmogorov

Avec l'utilisation d'une machine universelle, la complexité de Kolmogorov d'une chaîne s'apparente à la taille du plus petit programme informatique capable de calculer cette chaîne. Il s'agit en quelque sorte de sa meilleure compression possible, si l'on ne prend pas en considération le temps nécessaire à sa décompression, qui peut s'avérer particulièrement long... Quant au temps nécessaire à sa compression, la situation est encore pire : il ne s'agit même plus d'un processus calculable !

### 1.3.1. La complexité de Kolmogorov n'est pas calculable

On donne une première démonstration du fait que la complexité de Kolmogorov n'est pas calculable, via une formalisation mathématique du paradoxe de Berry : « soit $n$ le plus petit entier que l'on ne peut pas définir en moins de cinquante mots ». Le paradoxe — qui devrait apparaître clairement au lecteur — vient de ce que le mot « définir » est lui-même mal défini. Il suffit de le remplacer par « calculable ».

**Proposition 1.5.** La fonction $\sigma \mapsto C(\sigma)$ n'est pas calculable. ★

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

PREUVE. Supposons que la fonction $\sigma \mapsto C(\sigma)$ soit calculable. Alors, on peut créer la fonction calculable $f : \mathbb{N} \to 2^{<\mathbb{N}}$ qui sur $n$ renvoie la première chaîne $\sigma$ — disons lexicographiquement — telle que $C(\sigma) > n$. En utilisant l'écriture en binaire des entiers, on peut définir la machine $M : 2^{<\mathbb{N}} \to 2^{<\mathbb{N}}$ qui sur la chaîne $\sigma_n$ (qui est l'écriture binaire de $n$) renvoie donc $f(n)$.

Comme la taille nécessaire pour représenter $n$ en base 2 est de $\log_2(n)$, on a ainsi $C_M(\sigma) \le \log_2(n)$, pour toute chaîne $\sigma = f(n)$. Il y a donc une constante $c_M$ telle que $C(\sigma) < \log_2(n) + c_M$, pour toute chaîne $\sigma = f(n)$. Dans le même temps, chacune de ces chaînes est choisie telle que $C(\sigma) > n$, ce qui donne $n < C(\sigma) < \log_2(n) + c_M$. Pour $n$ suffisamment grand, tel que $n > \log_2(n) + c_M$, on a une contradiction. ■

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

La fonction $\sigma \mapsto C(\sigma)$ n'est donc pas calculable. En revanche, elle est *approchable par le dessus*.

**Définition 1.6.** Une fonction $f : \mathbb{N} \to \mathbb{N}$ est *approchable par le dessus* si elle est la limite d'une suite $(f_n)_{n \in \mathbb{N}}$ de fonctions calculables avec, pour tout $n$, l'inégalité $f_{n+1} \le f_n$. ◇

<figure><img src="image_109.png" /></figure>
On peut définir l'approximation $(f_n)_{n \in \mathbb{N}}$ de la complexité de Kolmogorov en assignant à $f_0(\sigma)$ la taille du premier programme $\tau$ trouvé tel que $U(\tau) \downarrow= \sigma$, et en assignant à $f_{n+1}(\sigma)$ la taille du plus petit programme $\tau$ tel que $U(\tau)[n+1] \downarrow= \sigma$ si cette taille est plus petite que $f_n(\sigma)$, et $f_n(\sigma)$ sinon.

On montre facilement que les fonctions approchables par le dessus sont calculables avec l'arrêt des programmes informatiques

**Exercice 1.7.** Montrer que toute fonction approchable par le dessus est $\emptyset'$-calculable. ◇

### 1.3.2. La complexité de Kolmogorov est Turing-complète

Il est possible de renforcer la proposition 1.5 et de montrer que la connaissance de la complexité de Kolmogorov permet en fait de calculer le problème de l'arrêt. Il s'agit d'un bon exercice, pour lequel nous préparons ci-après le lecteur avec une proposition plus simple, évidente si l'on s'en tient à la construction qui a été faite ci-dessus d'une machine universelle, mais qui demande un peu de travail si l'on considère les machines universelles de manière abstraite.

**Proposition 1.8.** Soit $X$ une représentation d'une machine universelle

$$U : 2^{<\mathbb{N}} \to 2^{<\mathbb{N}}$$

(par exemple, avec $X(\langle\sigma, \tau\rangle) = 1 \text{ ssi } U(\sigma) \downarrow= \tau$ et $X(\langle\sigma, \epsilon\rangle) = 1 \text{ ssi } U(\sigma) \uparrow$). Alors, $X \ge_T \emptyset'$. ★

**PREUVE.** On définit la machine $M$ telle que $M(0^e) \downarrow= 0^s$ si $s$ est le plus petit entier tel que $\Phi_e(e)[s] \downarrow$. Si un tel entier n'existe pas, le calcul $M(0^e)$ ne s'arrête pas. Soit une constante $d$ telle que $C_U(\sigma) < C_M(\sigma) + d$, pour toute chaîne $\sigma$. Étant donné la connaissance de $U$, pour savoir si $\Phi_e(e) \downarrow$, il suffit de regarder $U(\sigma)$ pour toute chaîne $\sigma$ de taille inférieure à $e+d+1$, de récupérer la plus grande valeur $s$ telle que $U(\sigma) \downarrow= 0^s$ pour l'une de ces chaînes $\sigma$, et de calculer $\Phi_e(e)[s]$. On a alors $\Phi_e(e) \downarrow \leftrightarrow \Phi_e(e)[s] \downarrow$. ■

L'un des exercices suivants consiste à montrer que la connaissance de la complexité de Kolmogorov permet de calculer la machine universelle $U$ qui lui est associée, et donc le problème de l'arrêt. La considération suivante sera utile, et présente aussi son intérêt propre : la proposition 1.5 ne montre pas seulement que la complexité de Kolmogorov est non calculable, mais aussi que pour toute fonction de compression $I : 2^{<\mathbb{N}} \to 2^{<\mathbb{N}}$ telle que $C_I(\sigma) \le C(\sigma)$, la fonction $\sigma \mapsto C_I(\sigma)$ est non calculable. En revanche, comme nous le montre l'exercice 1.11, une telle fonction ne permet pas nécessairement de calculer le problème de l'arrêt, et a fortiori la complexité de Kolmogorov qui lui est associée non plus. Il est nécessaire pour cela d'utiliser la connaissance exacte de la complexité de Kolmogorov.
**Exercice 1.9.** (⋆) (Tibor Radó [182]). Tibor Radó introduit dans un article en 1962 [182] la fonction $\Sigma: \mathbb{N} \to \mathbb{N}$ du *castor affairé*, dont on peut résumer l'idée, avec les notations de ce livre, comme suit : $\Sigma(n)$ est le plus grand temps de calcul $t$ tel que $U(\sigma)[t] \downarrow$ pour une chaîne $\sigma$ de taille inférieure ou égale à $n$. Les chaînes $\sigma$ réalisant pour chaque $n$ ces plus grands temps de calcul sont baptisées « busy beaver » par Tibor Radó —en français « castor affairé » — une expression anglaise imagée pour désigner des personnes très travailleuses. Montrer que toute fonction $f \ge \Sigma$ permet de calculer $\emptyset'$. ◇

**Exercice 1.10.** (⋆⋆) (créditée à P. Gàcs. Voir 2.7.7. de [144]). Soit $X$ une représentation de $C: 2^{<\mathbb{N}} \to \mathbb{N}$ (par ex. avec $X(\langle\sigma, n\rangle) = 1 \text{ ssi } C(\sigma) = n$). Montrer que $X \ge_T \emptyset'$.

Indication.– Montrer que pour $n$ suffisamment grand, il existe une chaîne de taille $2n$, de complexité inférieure à $2n$, mais telle qu'aucun programme de taille inférieure à $2n$ ne peut la calculer en un temps inférieur à $\Sigma(n)$. ◇

**Exercice 1.11.** (⋆) Montrer qu'il existe une fonction de compression

$I: 2^{<\mathbb{N}} \to 2^{<\mathbb{N}}$ telle que $|I(\sigma)| \le C(\sigma)$, $\forall \sigma \in 2^{<\mathbb{N}}$, et telle que $\forall I' \le_T \emptyset'$. ◇

## 1.4. Propriétés numériques de la complexité de Kolmogorov

Nous voyons ici quelques propriétés élémentaires de la complexité de Kolmogorov. Nous commençons par deux notations importantes, que nous réutiliserons tout au long de ce chapitre.

**Notation**

Étant donné un entier $n$, on écrira par abus de notation $C(n)$ pour signifier $C(\sigma)$, où $\sigma$ est la représentation binaire standard de $n$. Notez que la taille de la représentation binaire de $n$ est de l'ordre de $\log_2(n)$.

**Notation**

On écrira $\le^+$ ou $=^+$ pour signifier inégalité ou égalité à constante aditive près. Par exemple, l'inégalité $C(\sigma) \le^+ |\sigma|$ de la proposition suivante signifie qu'il existe une constante $d$ telle que, pour toute chaîne $\sigma$, on a $C(\sigma) \le |\sigma| + d$.

### 1.4.1. Bornes pour la complexité de Kolmogorov

La complexité de Kolmogorov d'une chaîne admet comme borne inférieure la complexité de Kolmogorov de sa taille, et sa taille comme borne supérieure.
**Proposition 1.12.** Pour toute chaîne $\sigma$, on a $C(|\sigma|) \leq^+ C(\sigma) \leq^+ |\sigma|$. ⋆

PREUVE. Une chaîne $\sigma$ fournit toujours au moins comme information la taille de $\sigma$, via la machine $M$ qui sur $\sigma$ renvoie $|\sigma|$. En utilisant $M$, il est clair que $C(|\sigma|) \leq^+ C(\sigma)$ : en effet, si $U(\tau) = \sigma$, alors $M(U(\tau)) = |\sigma|$, et donc une description courte de $\sigma$ fournit aussi la même description courte de $|\sigma|$.

Par ailleurs, en utilisant la machine identité, qui sur $\sigma$ renvoie $\sigma$, on obtient $C(\sigma) \leq^+ |\sigma|$.

Les bornes supérieures et inférieures sont toutes les deux atteintes pour des chaînes arbitrairement grandes. Nous l'avons vu avec la proposition 1.4 pour la borne supérieure, et nous le verrons avec le théorème 1.17 pour la borne inférieure.

### 1.4.2. La complexité d'une paire d'éléments

Nous présentons ici un outil technique dont nous aurons besoin. Étant donné des chaînes $\sigma$ et $\tau$, quelle est la taille du plus petit programme permettant de retrouver à la fois $\sigma$ et $\tau$ ? Pour formaliser cela, nous utiliserons la notation $\langle\sigma, \tau\rangle$ pour indiquer un encodage standard des paires de chaînes. Intuitivement, la complexité de $\langle\sigma, \tau\rangle$ peut être au moins aussi grande que la complexité de $\sigma$ additionnée à celle de $\tau$, en particulier si les chaînes $\sigma$ et $\tau$ ne « partagent pas d'information ». Il est en fait possible de montrer que la complexité peut être encore plus grande que cela. Si $\sigma^*$ et $\tau^*$ sont les plus petites descriptions respectivement pour $\sigma$ et $\tau$, la chaîne $\sigma^*\tau^*$ ne permettra pas nécessairement de retrouver à la fois $\sigma$ et $\tau$, car on ne sait pas où « découper » la chaîne $\sigma^*\tau^*$ pour retrouver la description de $\sigma$ et celle de $\tau$. Nous verrons avec l'exercice 1.15 qu'il n'existe pas de solutions pour contourner ce problème. Il est tout de même possible de ne pas « trop perdre », comme en témoigne la proposition suivante.

**Proposition 1.13.** Pour toutes chaînes $\sigma, \tau$, on a

$$C(\langle\sigma, \tau\rangle) \leq^+ C(\sigma) + C(\tau) + 2\log_2(C(\tau)). \quad \star$$

PREUVE. Soit $\sigma^*$ et $\tau^*$ les plus petites descriptions pour $\sigma$ et $\tau$, respectivement. Une première idée est d'encoder $\langle\sigma, \tau\rangle$ par la chaîne $1^{|\tau^*|}0^*\sigma^*$. Il suffit alors de concevoir la machine qui lit d'abord tous les bits 1 de son entrée jusqu'à arriver à 0, puis grâce à l'information du nombre $n$ de 1 lus, sait ensuite où découper le reste de la chaîne pour produire $\tau$ et $\sigma$. On obtient alors $C(\langle\sigma, \tau\rangle) \leq^+ C(\sigma) + 2C(\tau)$.

On peut encore améliorer cela de la manière suivante : étant donné une chaîne $\rho$ qui code pour $|\tau^*|$, et donc telle que $|\rho| = \log_2(C(\tau))$, il suffit
de considérer la chaîne $\bar{\rho}$ qui double tous les bits de $\rho$, c'est-à-dire qui remplace 0 par 00 et 1 par 11, puis de considérer la chaîne $\bar{\rho}01\tau^*\sigma^*$. Cette fois la machine lit les bits de son entrée jusqu'à arriver à 01, puis dédouble tous les bits pour retrouver un encodage de la taille de $\tau^*$, ce qui lui permet ensuite de savoir où découper le reste de son entrée. ■

Les exercices suivants montrent que l'on perd nécessairement à encoder des paires de chaînes.

**Exercice 1.14. (\*(\*)) (Martin-Löf. Voir [120]).** Montrer que pour tout $k$, toute chaîne $\sigma$ suffisamment longue —de taille $c+k+2^{c+k}$ pour une certaine constante $c$ — possède un préfixe $\tau \preceq \sigma$ tel que $C(\tau) \le |\tau| - k$.

Indication.– Utiliser le fait que toute chaîne $\rho$ contient également $|\rho|$ comme information. ◇

**Exercice 1.15. (\*(\*))** Déduire de l'exercice précédent que, pour tout $k$, il existe des chaînes $\tau, \rho$ telles que $C(\tau\rho) \ge C(\tau) + C(\rho) + k$. Déduire que, pour tout $k$, il existe des chaînes $\tau, \rho$ telles que

$$C(\langle\tau, \rho\rangle) \ge C(\tau) + C(\rho) + k.$$

◇

## 1.5. Le théorème de Chaitin

Gregory Chaitin (1947 - ) est un mathématicien qui contribua en même temps que Kolmogorov et Solomonov à l'essor de la théorie algorithmique de l'aléatoire. Il est à l'origine de plusieurs théorèmes remarquables et d'une très grande profondeur. Son travail le plus célèbre est sans doute la découverte du nombre $\Omega$ de Chaitin (voir la définition 2.9), et de ses premières propriétés. Si le résultat que nous présentons ici est moins connu, il n'en est pas moins riche d'enseignements tant sur le plan mathématique que philosophique.

Supposons $X \subseteq \mathbb{N}$ calculable. Alors, pour tout $n$, il devrait être à peu près clair que les $n$ premiers bits de $X$ contiennent autant d'information que leur taille, c'est-à-dire $n$. Formellement, $C(X \upharpoonright_n) =^+ C(n)$ : d'après la proposition 1.12, on a $C(n) \le^+ C(X \upharpoonright_n)$, puis comme $X$ est calculable on

<figure><img src="image_110.png" /><figcaption>Gregory Chaitin, 1947 -</figcaption></figure>
peut facilement créer une machine qui à partir de $n$ produit $X \upharpoonright_n$, ce qui donne $C(X \upharpoonright_n) =^+ C(n)$.

Chaitin est parvenu à démontrer la réciproque de ce résultat : si chaque préfixe d’un ensemble $X$ admet une compression maximale, alors $X$ est un nombre calculable.

**Théorème 1.17 (Chaitin [30], Zvonkin et Levin [237], Meyer)**

Soit $X \in 2^N$. Alors, $X$ est calculable si, et seulement si, $C(X \upharpoonright_n) =^+ C(n)$ pour tout $n$.

La preuve repose sur deux lemmes surprenants. Le premier nous dit que pour toute machine $M$ et toute chaîne $\sigma$, le nombre de $M$-compressions « maximales » de $\sigma$ est borné par une constante qui ne dépend pas de $\sigma$. Le second découle du premier et nous dit que le nombre de chaînes de taille $n$ qui admettent une compression « maximale » est bornée par une constante qui ne dépend pas de $n$.

**Lemme 1.18.** Pour toute machine $M$, il existe une constante $c$ telle que, pour tout $\sigma \in 2^{<N}$ et $d \in \mathbb{N}$, on a :

$$ |\{\tau : |\tau| < C(\sigma) + d \wedge M(\tau) = \sigma\}| < 2^{c+d}. \quad \star $$

**PREUVE.** L'idée est la suivante : étant donné $m, k$, on peut calculatoirement énumérer la liste $L_{m,k}$ des chaînes qui ont au moins $2^m$ descriptions de tailles strictement inférieures à $k$ via la machine $M$. Notez qu'il y a au plus $2^{k-m}$ éléments dans $L_{m,k}$. À présent, pour décrire un élément de $L_{m,k}$, il suffit d'avoir comme information $m, k$ et une chaîne $\rho$ de taille $k - m$ qui représente sa place dans la liste $L_{m,k}$. En fait, l'information donnée par $m$ et $\rho$ suffit puisque $k$ peut se retrouver à partir de $m$ et $\rho$. D'après la proposition 1.13, on a

$$ C(\langle \rho, m \rangle) \le C(\rho) + C(m) + 2 \log_2(C(m)) \le k - m + 2 \log_2(m). $$

On peut donc construire une machine $N$ — qui dépend de $M$ — telle que chaque élément $\sigma$ de $L_{m,k}$ admet une description de taille inférieure ou égale à $k-m+2\log_2(m)+c_0$ via $N$, pour une certaine constante $c_0$ indépendante de $m, k$. On a donc $C_N(\sigma) \le k - m + 2\log_2(m) + c_0$, pour tout $m, k \in \mathbb{N}$ et tout $\sigma \in L_{m,k}$.

Soit $c_1 \in \mathbb{N}$ tel que $C \le C_N + c_1$. En posant

$c=c_0+c_1$, $m=2^{c+d}$ et $k=C(\sigma)+d$ pour une chaîne $\sigma$ quelconque, il suffit de montrer que $\sigma \notin L_{m,k}$. Supposons par l'absurde que $\sigma \in L_{m,k}$. On a donc

$$ C_N(\sigma) \le C(\sigma) + d - 2^{c+d} + 2\log_2(2^{c+d}) + c_0 \le C_N(\sigma) + 3(c+d) - 2^{c+d}, $$
ce qui donne $2^{c+d} \le 3(c+d)$. On peut bien entendu supposer $c \ge 4$, ce qui amène à une contradiction. Donc, $\sigma \notin L_{m,k}$, et le lemme est vérifié. ■
**Lemme 1.19.** Il existe une constante $c$ telle que, pour tous $n, d \in \mathbb{N}$, on a :

$$|\{\sigma : |\sigma| = n \text{ et } C(\sigma) < C(n) + d\}| < 2^{d+c}. \quad \star$$

**PREUVE.** Il suffit à présent d'appliquer le lemme précédent en remarquant qu'une description courte de la chaîne $\sigma$ donne aussi une description courte de $|\sigma|$. Supposons qu'il y ait plus de $2^{d+c}$ chaînes $\sigma$ de taille $n$ telles que $C(\sigma) < C(n) + d$. Alors, il y a aussi une machine $M$ telle qu'il y a plus de $2^{d+c}$ chaînes $\tau$ de taille inférieur à $C(n) + d$ pour lesquels $M(\tau) = n$, ce qui contredit le lemme précédent. ■

**PREUVE DU THÉORÈME 1.17.** L'idée est la suivante : étant donné $d$ fixé, l'ensemble $T = \{\sigma : \forall \tau \preceq \sigma C(\tau) \leq C(|\tau|) + d\}$ est un arbre. D'après le lemme 1.19, il existe $c$ tel que pour tout $n$ cet arbre contient au plus $2^{c+d}$ chaînes de taille $n$. En particulier, $[T]$ est fini, et d'après la proposition 8-3.6, tous les chemins de $T$ sont donc calculables relativement à la connaissance de $T$.

Le problème est que l'ensemble $T$ lui-même n'est pas calculable, car $C$ ne l'est pas. Nous allons donc le transformer de la manière suivante : nous remarquons d'abord que, d'après la proposition 1.4, il existe pour tout $k$ un entier $n$ entre $2^k$ et $2^{k+1} - 1$ tel que $\log_2(n) \leq C(n)$. Par ailleurs, d'après la proposition 1.12, il existe une constante $e$ pour laquelle on a toujours $C(n) \leq \log_2(n) + e$.

Nous utilisons ces informations pour faire une première transformation de $T$ :

$$T_1 = \{\sigma : \forall \tau \preceq \sigma C(\tau) \leq \log_2(|\tau|) + e + d\}.$$

Étant donné que $C(n) \leq \log_2(n) + e$, on a $T_1 \subseteq T_1$. Étant donné que pour tout $k$ il existe un entier $n$ entre $2^k$ et $2^{k+1} - 1$ tel que $\log_2(n) \leq C(n)$, pour tout $k$ on dispose aussi d'après le lemme 1.19 d'un entier $n$ entre $2^k$ et $2^{k+1} - 1$ tel que $|\{\sigma \in T_1 : |\sigma| = n\}| < 2^{e+d+c}$.

En particulier, $|[T_1]| < 2^{e+d+c}$. L'arbre $T_1$ n'est toutefois toujours pas calculable, mais simplement c. e. Soit $a_k$ défini pour tout $k$ comme le minimum pour $n$ compris entre $2^k$ et $2^{k+1} - 1$, du nombre de noeuds de taille $n$ dans l'arbre $T_1$. Notons que l'on a nécessairement $a_k < 2^{e+d+c}$. Soit alors $a = \limsup_{k \in \mathbb{N}} a_k$, et soit $m$ le plus petit entier tel que $a_k \leq a$ pour tout $k \geq m$. On peut à présent chercher de manière effective un temps de calcul $s_0$ et un entier $k_0 > m$ tels que pour tout $n$ compris entre $2^{k_0}$ et $2^{k_0+1} - 1$, au moins $a$ noeuds de taille $n$ sont énumérés dans $T_1[s_0]$. Soit $X \in [T_1]$. Nous prétendons que $X \upharpoonright_{2^{k_0}} \in T_1[s_0]$. En effet, dans le cas contraire, quand $X \upharpoonright_{2^{k_0+1}}$ et ses préfixes seront énumérés dans $T_1$, cela rajoutera un noeud de taille $n$ qui n'est pas dans $T_1[s_0]$, pour tout $n$ compris entre $2^{k_0}$ et $2^{k_0+1} - 1$. Le nombre de noeuds de taille $n$ dépasserait donc $a$, ce qui contredit le fait que $a_k \leq a$ pour tout $k \geq m$. Donc, $T_1[s_0]$ contient tous les préfixes de taille $2^{k_0}$ des éléments de $T_1$.
Une fois $s_i$ et $k_i$ définis, on calcule de la même façon inductivement $s_{i+1}>s_i$ et $k_{i+1}>k_i$ tels que pour tout $n$ compris entre $2^{k_{i+1}}$ et $2^{k_{i+1}+1}-1$, au moins $a$ noeuds de taille $n$ sont énumérés dans $T_1[s_{i+1}]$. Par le même argument que dans le paragraphe précédent, tout $X \in [T_1]$ a son préfixe de taille $2^{k_{i+1}}$ énuméré dans $T_1[s_{i+1}]$.

Cela nous permet de définir un arbre calculable $T_2$ tel que $[T_2] = [T_1]$. En particulier, $|[T_2]| < 2^{e+d+c}$ et $T_2$ contient tous les ensembles $X$ tels que $C(X \upharpoonright_n) \le C(n) + d$, pour tout $n$. Tous ces ensembles sont donc calculables.

## 2. Nombres aléatoires à la Chaitin/Levin

La définition originelle de la complexité de Kolmogorov souffre de certains problèmes. D’après l’exercice 1.10, on n’a pas nécessairement

$$C(\langle\sigma, \tau\rangle) \le C^+(\sigma) + C(\tau),$$

pour toutes chaînes $\sigma, \tau$. D’après l’exercice 1.14, pour tout entier $k$ et toute chaîne $\sigma$ suffisamment longue, on a l’inégalité $C(\tau) \le |\tau| - k$, pour un certain préfixe $\tau \le \sigma$. Cela nous empêche d’utiliser $C$ pour définir l’aléatoire sur les suites infinies. Il est nécessaire pour cela d’utiliser une variation de $C$: la complexité dite « sans préfixe ».

### 2.1. Complexité sans préfixe

La complexité sans préfixe fut introduite indépendamment par Levin [139] et Chaitin [29]. Elle est définie de la même manière que la complexité de Kolmorogov, mais en se restreignant aux machines dites « sans préfixe », que nous introduisons à présent.

**Définition 2.1.** Un ensemble $W \subseteq 2^{<N}$ est sans préfixe si $\sigma \in W$ implique $\tau \notin W$, pour toute chaîne $\tau \succ \sigma$. Une machine $M$ est sans préfixe si son domaine de définition est sans préfixe, c’est-à-dire que, pour toute chaîne $\sigma$, on a $M(\sigma) \downarrow$ implique $M(\tau) \uparrow$ pour toute chaîne $\tau \succ \sigma$. ◇

Une machine $M$ sans préfixe peut être vue comme une machine sur laquelle s’exécutent des programmes (les chaînes que $M$ prend en paramètre) délimités par une instruction de fin : si $\sigma$ est un programme valide, alors aucune extension de $\sigma$ n’est valide.

Notons que dans la réalité, les programmes informatiques tendent à former des ensembles sans préfixe. Dans n’importe quel langage de programmation, les fonctions ont un symbole de début et de fin. Quand bien même ça ne serait pas le cas, les systèmes de fichiers utilisés pour enregistrer les
programmes en binaire sont sans préfixe (comment savoir sinon où s’arrête un fichier !). Voyons à présent un théorème analogue au théorème de la machine universelle pour les machines arbitraires.

## Théorème 2.2

Il existe une machine sans préfixe qui est universelle pour les machines sans préfixe.

PREUVE. Soit $(M_e)_{e \in \mathbb{N}}$ une énumération des machines. Commençons par montrer qu'il existe une fonction calculable $f : \mathbb{N} \to \mathbb{N}$ telle que :

* ▷ pour tout $e \in \mathbb{N}$, la machine $M_{f(e)}$ est sans préfixe;

* ▷ si $M_e$ est sans préfixe, alors $M_{f(e)} = M_e$.

Étant donné un code $e$, la fonction $f$ calcule le code de la machine qui sur une entrée $\sigma$ cherche le plus petit $t \ge |\sigma|$ tel que $M_e(\sigma)[t] \downarrow$. Si un tel $t$ est trouvé, alors s'il existe $s < t$ tel que $M_e(\tau)[s] \downarrow$, pour $\tau \ne \sigma$ comparable avec $\sigma$ et tel que $|\tau| \le s$, on décide que la machine ne s'arrête pas, et donc $M_{f(e)}(\sigma) \uparrow$. Dans le cas contraire, si $M_e(\tau)[t] \downarrow$ pour $\tau < \sigma$, là encore on décide $M_{f(e)}(\sigma) \uparrow$. Sinon, on décide $M_{f(e)}(\sigma) \downarrow= M_e(\sigma)[t] \downarrow$.

Il est clair que si $M_e$ est sans préfixe, alors $M_{f(e)} = M_e$. Il est clair aussi que $M_{f(e)}$ est toujours sans préfixe : supposons par l'absurde que $M_{f(e)}(\sigma) \downarrow$ et $M_{f(e)}(\tau) \downarrow$ pour $\sigma < \tau$. Soit $t_\sigma \ge |\sigma|$, $t_\tau \ge |\tau|$ les plus petits temps de calcul tels que $M_e(\sigma)[t_\sigma] \downarrow$ et $M_e(\tau)[t_\tau] \downarrow$. Si $t_\sigma = t_\tau$, on a par définition $M_{f(e)}(\tau) \uparrow$. Si $t_\tau < t_\sigma$, on a par définition $M_{f(e)}(\sigma) \uparrow$, et symétriquement si $t_\sigma < t_\tau$.

On définit à présent la machine $U$ suivante : $U(1^e 0\sigma) = M_{f(e)}(\sigma)$. Notons que comme chaque machine $M_{f(e)}$ est sans préfixe, alors la machine $U$ l'est également. ■

## Notation

De manière générale si $M$ est une machine sans préfixe on écrira $K_M(\sigma)$ à la place de $C_M(\sigma)$. On fixe une machine sans préfixe universelle $U$. On note $K(\sigma)$ pour la valeur $K_U(\sigma)$. On dira que $K(\sigma)$ est la complexité sans préfixe de $\sigma$, et par opposition que $C(\sigma)$ est sa complexité pleine.

Certains théorèmes restent vrais pour la complexité sans préfixe. On adapte par exemple sans mal la preuve de la proposition 1.8 pour montrer que la connaissance d'une machine universelle sans préfixe permet de calculer $\emptyset'$. En revanche, les différentes bornes varient un peu.

**Exercice 2.3.** (⋆) Montrer qu'aucune fonction calculable $f : 2^{<\mathbb{N}} \to 2^{<\mathbb{N}}$ — même partielle — ne peut augmenter la complexité de ses paramètres : montrer pour une telle fonction qu'il existe une constante $c$ telle que $K(f(\sigma)) \le K(\sigma) + c$, pour tout $\sigma \in 2^{<\mathbb{N}}$ sur laquelle $f$ est définie. ◦
## 2.2. Propriétés numériques de la complexité sans préfixe

Une première spécificité, bien pratique, des machines sans préfixe est de pouvoir coder les paires de chaînes de manière optimale.

**Proposition 2.4.** Pour toutes chaînes $\sigma, \tau$, on a

$$ K(\langle\sigma, \tau\rangle) \leq^{+} K(\sigma) + K(\tau). \quad \star $$

**PREUVE.** Soit $U$ la machine sans préfixe universelle. On définit la machine sans préfixe $M$ qui sur une chaîne $\sigma$ cherche des chaînes $\tau, \rho$ telles que $\tau\rho = \sigma$, telles que $U(\tau) \downarrow$ et telles que $U(\rho) \downarrow$. la machine renvoie alors $\langle U(\tau), U(\rho) \rangle$. Notons que si un préfixe $\tau \preceq \sigma$ tel que $U(\tau) \downarrow$ existe, celui-ci est unique car $U$ est sans préfixe.

À présent, si $\sigma^*$ et $\tau^*$ sont les plus petits programmes tels que $U(\sigma^*) = \sigma$ et $U(\tau^*) = \tau$ pour des chaînes $\sigma, \tau$ arbitraires, alors $M(\sigma^*\tau^*) = \langle\sigma, \tau\rangle$, et donc $K(\langle\sigma, \tau\rangle) \leq^{+} K_M(\langle\sigma, \tau\rangle) \leq K(\sigma) + K(\tau)$. ■

Tout comme on avait $C(|\sigma|) \leq^{+} C(\sigma)$, on a ici toujours $K(|\sigma|) \leq^{+} K(\sigma)$. En revanche, on ne peut plus forcément garantir $K(\sigma) \leq^{+} |\sigma|$, la machine identité n'étant pas une machine sans préfixe. On a $K(\sigma) \leq^{+} |\sigma| + K(|\sigma|)$, à la place.

**Proposition 2.5.** Pour toute chaîne $\sigma$, on a

$$ K(|\sigma|) \leq^{+} K(\sigma) \leq^{+} |\sigma| + 2 \log_2(|\sigma|). \quad \star $$

**PREUVE.** Soit $U$ la machine universelle sans préfixe. Montrons la première inégalité. La machine $M$ qui à $\tau$ associe $|U(\tau)|$ est elle aussi sans préfixe. Supposons $U(\tau) = \sigma$. Alors, $M(\tau) = |\sigma|$. On a donc $K(|\sigma|) \leq^{+} K(\sigma)$.

Montrons à présent $K(\sigma) \leq^{+} |\sigma| + 2 \log_2(|\sigma|)$. On utilise la même technique que pour la preuve de la proposition 1.13 : étant donné une chaîne $\rho$, soit $\bar{\rho}$ la chaîne qui double tous les bits de $\rho$, c'est-à-dire qui remplace 0 par 00 et 1 par 11. On définit la machine $M$ qui s'arrête sur les chaînes de la forme $\bar{\rho}01\sigma$ telles que $\rho$ code pour la taille de $\sigma$, et renvoie alors $\sigma$. Notons que la machine $M$ est sans préfixe : si $M(\bar{\rho}01\sigma) \downarrow$, cela signifie que $\rho$ est un encodage de la taille de $\sigma$, et si à présent $M(\bar{\rho}01\sigma') \downarrow$ pour $\sigma' \prec \sigma$ ou $\sigma' \prec \sigma'$, cela signifierait aussi que $\rho$ encode $|\sigma'| \neq |\sigma|$, ce qui est impossible. On obtient enfin l'inégalité $K(\sigma) \leq^{+} |\sigma| + 2 \log_2(|\sigma|)$ via la machine $M$ en utilisant le fait que la représentation binaire d'un entier et de l'ordre du $\log_2$ de cet entier. ■

**Exercice 2.6.** $(\star)$ (Chaitin [29]). Montrer que l'on a également

$$ K(\sigma) \leq^{+} |\sigma| + K(|\sigma|), \quad \text{pour toute chaîne } \sigma. $$

En quoi est-ce une amélioration de la proposition 2.5 ? ◇
**Exercice 2.7. (*)** Montrer que, pour tout $c$, il existe une chaîne $\sigma$ telle que $K(\sigma) > |\sigma| + c$. ◇

## 2.3. Nombres aléatoires au sens de Chaitin/Levin

Levin, le premier, et, indépendamment, Chaitin ont tous les deux utilisé la complexité sans préfixe pour définir l’aléatoire pour des objets infinis.

**Définition 2.8 ([142], [31]).** Un ensemble $X \in 2^N$ est aléatoire au sens de Chaitin/Levin si $K(X \upharpoonright_n) \geq^+ n$, pour tout $n$. ◇

En d'autres termes, une suite infinie de 0 et de 1 est aléatoire si aucun de ses préfixes n'est compressible, à constante additive près. Notons que pour une telle définition, la complexité sans préfixe est nécessaire : comme nous l'avons déjà mentionné, l'exercice 1.14 montre qu'aucun ensemble $X \in 2^N$ ne satisfait $C(X \upharpoonright_n) \geq^+ n$ pour tout $n$. En revanche, nous pouvons montrer qu'un ensemble est aléatoire au sens de Chaitin/Levin avec probabilité 1. Nous reviendrons sur ce point dans le chapitre 17 après avoir défini formellement les notions de boréliens et de mesure.

Nous verrons que la définition de Chaitin et Levin est une « bonne » définition de l'aléatoire, et ce selon plusieurs critères imaginables. En particulier, un nombre aléatoire pour cette définition satisfait la loi des grands nombres. De plus, si un nombre présente une répétition, une incongruité, un « motif », il sera possible de créer une machine utilisant cela pour compressor même un peu les préfixes de ce nombre. Nous verrons en fait, pour aussi formelle que puisse être cette affirmation, qu'un nombre aléatoire pour cette définition satisfait toutes les lois de probabilité « naturelles » qui sont satisfaites avec probabilité 1.

Avant de voir cela plus en détail, nous présentons dès à présent le plus fameux résultat de Chaitin, que l'on peut résumer ainsi : la probabilité qu'un programme informatique s'arrête est un nombre aléatoire.

## 2.4. Le nombre $\Omega$ de Chaitin

Qu'entend-on précisément par « la probabilité qu'un programme informatique s'arrête » ? Considérons une machine sans préfixe universelle $U$. Supposons que l'on tire à pile ou face sans jamais s'arrêter pour déterminer un programme $\sigma$ sur lequel $U$ s'exécutera. Le tirage en question produit des chaînes $\sigma_1 < \sigma_2 < \sigma_3 < \dots$ avec $|\sigma_i| = i$. En procédant ainsi, la probabilité pour que l'on obtienne $\sigma_i$ tel que $U(\sigma_i) \downarrow$, est un nombre aléatoire : écrit en base 10 par exemple, la fréquence d'apparition des chiffres 0, 1, 2, ..., 9 dans les préfixes du développement décimal de ce nombre convergera vers 1/10. La fréquence d'apparition des nombres à deux chiffres convergera vers 1/100, etc. Définissons à présent formellement ce nombre.
**Définition 2.9.** Le nombre $\Omega$ de Chaitin est défini par :

$$ \Omega = \sum_{\{\sigma : U(\sigma) \downarrow\}} 2^{-|\sigma|}. \quad \diamond $$

Etant donné que $U$ est une machine sans préfixe, le nombre $\Omega$ est inférieur à 1. Pour voir cela, nous introduisons informellement le concept de mesure pour des intervalles $]a, b[ \subseteq [0, 1]$ comme étant simplement ce que l'on mesurerait avec une règle graduée : la valeur $b - a$. Une chaîne $\sigma$ peut se voir comme l'intervalle des réels compris entre $0.\sigma0^{\infty}$ et $0.\sigma1^{\infty}$. On vérifie facilement que la mesure de l'intervalle $]0.\sigma0^{\infty}, 0.\sigma1^{\infty}[$ est de $2^{-|\sigma|}$. Le fait que le domaine de définition de $U$ est sans préfixe correspond au fait que les intervalles de la forme $]0.\sigma0^{\infty}, 0.\sigma1^{\infty}[$ tels que $U(\sigma) \downarrow$ sont deux à deux disjoints. La somme de leur mesure correspond donc à la mesure de leur réunion, qui est nécessairement inférieure à la mesure de $[0, 1]$, à savoir 1.

On considère dans la suite le nombre $\Omega$ comme la représentation en binaire de son développement décimal. Remarquons d'abord que $\Omega$ est approchable par la gauche.

**Définition 2.10.** Un ensemble $X \in 2^N$ est *approchable par la gauche* s'il existe une suite calculable $(X_s)_{s \in \mathbb{N}}$ telle que $X_s$ est lexicographiquement plus petit que $X_{s+1}$ pour tout $s \in \mathbb{N}$, et pour laquelle $X = \lim_s X_s$. ♦

De manière équivalente, $X \in 2^N$ est approchable par la gauche s'il existe une suite croissante calculable de réels dont la représentation binaire converge vers $X$. Concrètement, dans une approximation par la gauche de $X$, un bit peut passer de 0 à 1 — ce qui correspond à une augmentation de la valeur du réel — comme pour un ensemble c. e., et un bit peut aussi passer de 1 à 0, mais seulement si un bit de poids plus fort passe au même moment de 0 à 1 — ce qui correspond aussi à une augmentation de la valeur du réel. Par exemple, le nombre $0,010000$ est plus grand que le nombre $0,000101$.

**Exercice 2.11.** Montrer que toute classe $\Pi_1^0$ non vide $\mathcal{P}$ contient un élément approchable par la gauche. ♦

Il est clair que les ensembles approchables par la gauche sont tous $\emptyset'^{-}$ calculable : il s'agit d'un cas particulier du lemme limite 4-7.2 de Shoenfield.

**Proposition 2.12.** Le nombre $\Omega$ est approchable par la gauche. En particulier, $\Omega$ est calculable en l'arrêt des programmes informatiques. ★

**PREUVE.** Définissons une suite calculable de réels calculables $(\Omega_s)_{s \in \mathbb{N}}$ tels que $\Omega_s \le \Omega_{s+1}$ et $\Omega = \lim_s \Omega_{s \in \mathbb{N}}$. Chaque réel $\Omega_s$ est simplement

$$ \sum_{\{\sigma : |\sigma| \le s \land U(\sigma)[s] \downarrow\}} 2^{-|\sigma|}. $$
Il est clair que $\Omega_s \le \Omega_{s+1}$, pour tout $s$, et que $\Omega = \lim_s \Omega_{s \in \mathbb{N}}$. ■
**Théorème 2.13 (Chaitin [29])**

Les $n$ premiers bits de $\Omega$ suffisent pour déterminer uniformément quelles sont les chaînes $\sigma$ de taille inférieure ou égale à $n$ telles que $U(\sigma) \downarrow$. En particulier, $\Omega \equiv_T \emptyset'$.

PREUVE. Soit $(\Omega_s)_{s \in \mathbb{N}}$ l'approximation par la gauche de $\Omega$ décrite dans la preuve de la proposition 2.12. Supposons que l'on connaisse les $n$ premiers bits de $\Omega$. Alors, il suffit de chercher le plus petit $s$ tel que $\Omega_s \upharpoonright_{n+1} = \Omega \upharpoonright_{n+1}$. Remarquons alors qu'un programme $\sigma$ de taille $m \le n$ tel que $U(\sigma)[s] \uparrow$ doit forcément être tel que $U(\sigma) \uparrow$. En effet, dans le cas inverse, on devrait ajouter la quantité $2^{-m}$ à $\Omega_s$, ce qui ferait nécessairement passer un bit de position inférieure ou égale à $m$ de 0 vers 1, et contredirait $\Omega_s \upharpoonright_{n+1} = \Omega \upharpoonright_{n+1}$. Pour savoir si $U(\sigma) \downarrow$ sur une chaîne $\sigma$ de taille inférieure ou égale à $n$, il suffit de regarder si $U(\sigma)[s] \downarrow$.

En particulier, $\Omega$ peut calculer $U$, et d'après une adaptation de la proposition 1.8 à la complexité sans préfixe, $\Omega$ peut donc calculer $\emptyset'$. ■

**Théorème 2.14 (Chaitin [29])**

Le nombre $\Omega$ est aléatoire au sens de Chaitin/Levin.

PREUVE. Supposons par l'absurde que, pour tout $c$, il existe $n$ tel que

$$K(\Omega \upharpoonright_n) < n - c.$$

Construisons la machine $M$ qui sur la chaîne $\tau$ calcule $\sigma = U(\tau)$, et cherche ensuite à déterminer l'ensemble $A_\tau$ des chaînes de taille inférieure ou égale à $|\sigma|$ sur lesquelles la machine $U$ s'arrête, en appliquant l'algorithme décrit dans le théorème 2.13, comme si $\sigma \prec \Omega$. Si jamais $M$ pense avoir déterminé $A_\tau$ au bout d'un certain temps de calcul, alors $M$ renvoie la première chaîne qui est différente de $U(\rho)$ pour toute chaîne $\rho \in A_\tau$.

Notons d'abord que si $M$ est appliqué à une chaîne $\tau$ telle que $U(\tau) = \sigma \prec \Omega$, alors $M$ s'arrêtera et sortira une chaîne $\rho$ dont la complexité de Kolmogorov est plus grande que $|\sigma|$. Dans le même temps, on a $K_M(\rho) \le |\tau|$. Soit $c$ tel que $K \le K_M + c$. Par hypothèse, il existe $n$ tel que $K(\Omega \upharpoonright_n) < n - c$. Il existe donc $\tau$ telle que $|\tau| < n - c$ et tel que $U(\tau) = \Omega \upharpoonright_n$. On a alors par construction $M(\tau) = \rho$ pour une chaîne $\rho$ telle que $n = |\Omega \upharpoonright_n| \le K(\rho)$. Cela nous donne $n \le K(\rho) \le K_M(\rho) + c < n - c + c < n$, ce qui est une contradiction.

Donc, il existe $c$ tel que pour tout $n$ on a $K(\Omega \upharpoonright_n) \ge n - c$, ce qui signifie que $\Omega$ est aléatoire au sens de Chaitin/Levin. ■
Le nombre $\Omega$ de Chaitin a suscité un fort intérêt au sein de la communauté. Solovay dans une série de notes non publiées sur le travail de Chaitin [212] a introduit une notion clef qui devait en permettre une étude approfondie : pour deux réels $X, Y$ approchables par la gauche, $X$ est *Solovay réductible* à $Y$ s'il existe une fonction calculable $f : \mathbb{Q} \to \mathbb{Q}$ et une constante $c$ telles que pour un rationnel $q < Y$, on a $0 \le X - f(q) < c(Y - q)$. En d'autres termes, une approximation rationnelle proche de $Y$ permet de calculer une approximation rationnelle aussi proche de $X$, à constante multiplicative près. La réducibilité Solovay implique en particulier la réducibilité Turing. Solovay a ensuite montré que $\Omega$ était complet pour la réducibilité Solovay, c'est-à-dire que n'importe quel réel approchable par la gauche était Solovay réductible à $\Omega$. Par la suite, Calude, Hertling, Khoussainov et Wang [26] ont montré qu'un réel approchable par la gauche et Solovay complet était nécessairement de la forme $\Omega$ pour une certaine machine sans préfixe universelle. Puis, Kučera et Slaman [127] ont finalement montré qu'un réel approchable par la gauche et aléatoire au sens de Chaitin/Levin était forcément Solovay complet, ce qui mis bout à bout nous donne le théorème suivant.

**Théorème 2.15**

Un ensemble $X \in 2^N$ aléatoire au sens de Chaitin/Levin est approchable par la gauche si, et seulement si, il est la probabilité qu'une certaine machine universelle sans préfixe s'arrête sur son entrée.

# 3. Caractérisation de K

L'objectif de cette section est de montrer le théorème suivant, qui constitue une caractérisation élégante de la complexité sans préfixe.

**Théorème 3.1 (Chaitin [31])**

La fonction $\sigma \mapsto K(\sigma)$ est, à constante additive près, la plus petite fonction $f: 2^N \to \mathbb{N}$ approchable par le dessus et telle que $\sum_{\sigma} 2^{-f(\sigma)} \le 1$.

Le cœur de cette caractérisation réside dans le théorème KC, dit de Kraft-Chaitin, permettant de construire des machines sans préfixe à partir d'un ensemble de requêtes abstrait, dit « ensemble borné de requêtes ».

**Définition 3.2**

On appelle *ensemble borné de requêtes* tout ensemble $A \subseteq 2^{<N} \times \mathbb{N}$ tel que
$$ \sum_{(\sigma,l) \in A} 2^{-l} \le 1, $$
et l'on note $\text{poids}(A)$ cette quantité. $\diamond$
Nous réutiliserons de manière intensive dans la suite le concept d'ensemble borné de requêtes et le théorème KC, démontré indépendamment par Levin [139], Schnorr [193] et Chaitin [29].

**Théorème 3.3 (Théorème KC)**

Soit A un ensemble borné de requêtes c. e. Alors, il existe une machine sans préfixe $M$ telle que $(\sigma, l) \in A$ implique $M(\tau) = \sigma$ pour une chaîne $\tau$ telle que $|\tau| = l$. En particulier, $K_M(\sigma) \le l$.

PREUVE. Le lecteur pourra s'aider de la figure 3.4 pour comprendre la construction qui suit. Supposons sans perte de généralité que $A$ est un ensemble infini. Soit $(A_s)_{s \in \mathbb{N}}$ une approximation de $A$. Notons que l'on a donc forcément poids$(A_s) < 1$ pour tout $s$.

Nous allons décrire dans ce qui suit une machine $M$ en tant qu'ensemble c. e. de couples $(\sigma, \tau)$, signifiant alors $M(\sigma) = \tau$. On écrira $M_s$ pour l'énumération de $M$ à l'étape $s$. À chaque étape de calcul $s$, pour chaque taille $l \ge 1$, on définit une chaîne $\sigma_s^l$, soit de taille $l$, soit égale au mot vide $\epsilon$, et un ensemble $r_s \in 2^\mathbb{N}$. Les chaînes $\sigma_s^l$ différentes du mot vide correspondront aux chaînes disponibles pour une association à l'étape $s+1$. Le rôle de la suite $(r_s)_{s \in \mathbb{N}}$ est double. D'abord, le réel représenté par $r_s$ en base 2 sera égal au poids de $A_s$. Ensuite, si le $(n-1)$-ième bit de $r_s$ est 0, cela signifie aussi que la chaîne $\sigma_s^n$ est différente de $\epsilon$, et est donc disponible pour une future association. On doit s'assurer à chaque étape $s$ que les propriétés suivantes sont satisfaites.

(1) L'ensemble des chaînes associées dans $M_s$ forment avec l'ensemble des chaînes $\sigma_s^l$ différentes du mot vide, un ensemble sans préfixe.

(2) Le réel $r_s$ vue comme la représentation binaire d'un réel est égale à poids$(A_s)$.

(3) Si $r_s(n-1) = 0$, alors la chaîne $\sigma_s^n$ est une chaîne de longueur $n$. Sinon, c'est le mot vide.

À l'étape 0, on définit $\sigma_0^l = 1^{l-1}0$ et $r_0$ comme la suite infinie de 0. Les propriétés (1), (2) et (3) sont vérifiées à l'étape 0.

À l'étape $s+1$, supposons que $(\tau, l)$ soit énuméré dans $A_{s+1}$. Si $r_s(l-1) = 0$, on énumère $(\sigma_s^l, \tau)$ dans $M$ à l'étape $s+1$, on assigne $\sigma_{s+1}^l$ au mot vide et l'on change $r_{s+1}(l-1)$ à 1. Pour $i \ne l$, on garde $r_{s+1}(i-1) = r_s(i-1)$ et $\sigma_{s+1}^i = \sigma_s^i$. On vérifie facilement par induction que les propriétés (1), (2) et (3) sont vraies à l'étape $s+1$.
<figure><img src="image_111.png" /><figcaption>FIGURE 3.4 – Illustration de la preuve du théorème 3.3. À l'étape s, les deux chaînes originelles de taille 4 et 5, en gras, ont déjà été assignées. On suppose que l'on veut à présent assigner une chaîne de taille 5 à quelque chose à l'étape $s+1$. Le problème est qu'il n'y en a plus de disponible. On « remonte » alors jusqu'à la plus grande chaîne disponible, ici $\sigma_3^s$, et l'on « libère » dessous, de nouvelles chaînes de taille 4 et 5 (en pointillé), il en reste alors une libre de taille 5, ici $\sigma_3^{s+1}$, pour une affectation à l'étape $s+1$. On remarque que les bits à 1 du réel $r_{s+1}$ obtenu en rajoutant $2^{-5}$ à $r_s$ correspondent exactement aux nouvelles chaînes disponibles.</figcaption></figure>

Sinon, si $r_s(l - 1) = 1$, soit $n$ le plus grand entier strictement supérieur à 0 et plus petit que $l$ tel que $r_s(n - 1) = 0$. Notons qu'un tel entier existe forcément, car sinon $r_s + 2^{-l} \ge 1$ et donc poids($A_s$) + $2^{-l} \ge 1$, ce qui est impossible par hypothèse. On assigne $\sigma_{s+1}^n$ au mot vide et l'on change $r_s(n - 1) = 1$. Ensuite, pour chaque $n < i \le l$, on assigne $\sigma_{s+1}^i$ à $\sigma_s^n 1^{i-n-1} 0$ et $r_{s+1}(i - 1) = 0$. Puis, on énumère $(\sigma_s^n 1^{l-n-1} 1, \tau)$ dans $M$ à l'étape $s+1$. Pour $1 \le i < n$ et $i > l$, on définit $r_{s+1}(i - 1) = r_s(i - 1)$ et $\sigma_{s+1}^i = \sigma_s^i$. On vérifie aisément par induction que les propriétés (1), (2) et (3) sont vraies à l'étape $s+1$.

Cela conclut la construction. Étant donné que la propriété (1) est vraie à chaque étape $s$, il est clair que $M$ est une machine sans préfixe. Par construction également, on a $(\sigma, l) \in A$ implique $M(\tau) = \sigma$ pour une chaîne $\tau$ de taille $l$. ■
PREUVE DU THÉORÈME 3.1. Soit $f : 2^{<\mathbb{N}} \to \mathbb{N}$ une fonction approchable par le dessus et telle que $\sum_{\sigma} 2^{-f(\sigma)} \le 1$. Supposons dans un premier temps que $f$ est calculable. Il nous suffit alors d'énumérer chaque couple $(\sigma, f(\sigma))$ dans un ensemble borné de requêtes. D'après le théorème KC, il existe une machine $M$ telle que $K(\sigma) \le^+ K_M(\sigma) \le f(\sigma)$.

À présent, si la fonction $f$ est approchable par le dessus via une approximation $(f_s)_{s \in \mathbb{N}}$, on énumère dans un ensemble borné de requêtes $L$ les couples $(\sigma, f_0(\sigma) + 1)$, puis les couples $(\sigma, f_{s+1}(\sigma) + 1)$ pour chaque $\sigma$ et chaque $s$ tel que $f_{s+1}(\sigma) < f_s(\sigma)$. Soit $A_0$ l'ensemble des paires $\langle s, \sigma \rangle$ telles que $s$ est le dernier temps de calcul pour lequel $f_s(\sigma) > f_{s+1}(\sigma) = f(\sigma)$, puis soit récursivement $A_{n+1}$ l'ensemble des paires $\langle s, \sigma \rangle$ telles que $s$ est le dernier temps de calcul pour lequel $f_s(\sigma) > f_{s+1}(\sigma) = \dots = f_{s+t}(\sigma)$ pour $\langle s+t, \sigma \rangle \in A_n$. On a

$$ \text{poids}(L) = \sum_{\sigma} 2^{-f(\sigma)-1} + \sum_{n} \sum_{\langle s, \sigma \rangle \in A_n} 2^{-f_s(\sigma)-1}. $$

Par hypothèse sur $f$,

$$ \delta_0 = \sum_{\langle s, \sigma \rangle \in A_0} 2^{-f_s(\sigma)-1} \le \sum_{\sigma} 2^{-f(\sigma)-1-1} \le \frac{1}{4}. $$

Puis, pour tout $n$,

$$ \delta_{n+1} = \sum_{\langle s, \sigma \rangle \in A_{n+1}} 2^{-f_s(\sigma)-1} \le \sum_{\langle s, \sigma \rangle \in A_n} 2^{-f_s(\sigma)-1-1} = \frac{1}{2} \sum_{s \in A_n, \sigma} 2^{-f_s(\sigma)-1} = \frac{1}{2} \delta_n. $$

Le poids de notre ensemble de requêtes est donc borné par le nombre réel $\sum_{\sigma} 2^{-f(\sigma)-1} + 1/4 + 1/8 + \dots \le 1$. On peut donc construire une machine $M$ via le théorème KC telle que $K(\sigma) \le^+ K_M(\sigma) \le f(\sigma) + 1$. ■

On utilisera parfois le théorème 3.1 sous la forme suivante, connue sous le nom de « coding theorem » en anglais : pour toute machine sans préfixe $M$, la probabilité d'obtenir $\sigma$ via $M$ est toujours bornée, à constante multipli-cative près, par $2^{-K(\sigma)}$.

### Théorème 3.5 (Chaitin [29], Levin [139, 142])

Soit $M$ une machine sans préfixe. On dénote par $P_M(\sigma)$ la probabilité que $M$ écrive $\sigma$, c'est-à-dire

$$ P_M(\sigma) = \sum_{\{\tau : M(\tau) \downarrow = \sigma\}} 2^{-|\tau|}. $$

Alors, il existe une constante $c_M$ telle que, pour tout $\sigma$, on ait

$$ P_M(\sigma) \le 2^{-K(\sigma)} \times 2^{c_M}. $$
PREUVE. Il suffit de remarquer que la fonction $\sigma \mapsto -\log_2(P_M(\sigma))$ est approchable par le dessus et vérifie $\sum_{\sigma} 2^{\log_2(P_M(\sigma))} \le 1$. On a donc une constante $c_M$ telle que $K(\sigma) \le -\log_2(P_M(\sigma)) + c_M$, pour tout $\sigma$. ■

# 4. Ensembles K-triviaux

Souvenons-nous à présent de la remarquable caractérisation de Chaitin des ensembles calculables comme étant ceux dont la complexité de Kolmogorov des préfixes est toujours minimale. Nous introduisons ici la même notion, mais pour la complexité préfixe.

**Définition 4.1.** Soit $A \subseteq \mathbb{N}$. L'ensemble $A$ est $K$-trivial si, pour tout $n$,
$$K(A \upharpoonright_n) \le {}^+ K(n).$$

◇

Chaitin essaya d'adapter sa preuve pour montrer que les K-triviaux sont tous calculables, mais sans succès. Il réussit tout de même à démontrer que les K-triviaux sont en quantité dénombrable et en particulier tous $\Delta_2^0$. Solovay, dans sa série de notes non publiées consacrées à l'aléatoire algorithmique, démontra l'existence d'ensembles K-triviaux non calculables. Nous utiliserons pour le montrer une méthode pratique permettant de construire facilement des degrés c. e. incalculables : les ensembles dits simples.

## 4.1. Ensembles simples

Les ensembles simples furent introduits par Emil Post dans sa quête de degrés c. e. incomplets (voir le chapitre 12). En particulier, Post a montré que tous les ensembles simples étaient incomplets pour la réduction many-one.

**Définition 4.2.** Un ensemble $A$ est *simple* s'il est c. e., de complémentaire infini, et si $A \cap W_e \neq \emptyset$ pour tout ensemble c. e. infini $W_e$. ◇

Autrement dit, un ensemble $A$ est simple s'il est c. e. et son complémentaire est infini et immune.

**Proposition 4.3.** Un ensemble simple n'est pas calculable.

★

PREUVE. Soit $A$ un ensemble simple. Comme le complémentaire de $A$ est infini, et comme $A$ intersecte tout ensemble c. e. infini, le complémentaire de $A$ ne peut pas être c. e. D'après la proposition 3-7.4, l'ensemble simple $A$ ne peut donc pas être calculable. ■
La proposition suivante donne une technique pour construire un ensemble simple, qui sera utilisée à plusieurs reprises dans l'étude de différentes notions d'aléatoire, et en particulier pour construire un ensemble K-trivial non calculable.

**Proposition 4.4.** Il existe un ensemble simple.

★

PREUVE. Soit $(W_e)_{e \in \mathbb{N}}$ une énumération des ensembles c. e. On énumère un ensemble simple $A$. À l'étape de calcul $t$, pour tout $e \le t$ tel que $A$ n'intersecte pas encore $W_e$ à l'étape $t$, on regarde s'il existe un élément $x$ dans $W_e[t]$ tel que $x > 2e$. Si c'est le cas, on énumère $x$ dans $A$.

Il est clair que si $W_e$ est infini, alors $A \cap W_e \neq \emptyset$. Montrons à présent que $\mathbb{N} \setminus A$ est infini. Pour tout $W_e$, on énumère au plus un élément dans $A$. De plus, pour tout entier $n = 2e$, seuls les ensembles $W_a$ pour $a < e$ peuvent énumérer un élément plus petit que $n$ dans $A$. Il y a donc au plus $n/2$ éléments plus petits que $n$ dans $A$, et ce, pour tout $n$. Le complémentaire de $A$ est donc infini. ■

## 4.2. Le théorème de Solovay

Nous sommes maintenant prêts à montrer que les K-triviaux ne coïncident pas avec les C-triviaux, autrement dit qu'il existe des K-triviaux non calculables.

**Théorème 4.5 (Solovay [212])**

Il existe des K-triviaux c. e. non calculables.

PREUVE. Le lecteur peut s'aider de la figure 4.6 pour suivre la preuve. Soit $(W_e)_{e \in \mathbb{N}}$ une énumération des ensembles c. e. Nous allons construire un ensemble $A$ simple — avec la même technique que celle de la preuve de la proposition 4.4 — et K-trivial. Afin de garantir que $A$ soit K-trivial, on va créer nous même notre machine $M$ telle que $K_M(A \upharpoonright_n) \leq^+ K(n)$ pour tout $n$. On utilisera pour cela un ensemble borné de requêtes $L$.

On notera $A_t$ et $L_t$ les résultats des énumérations de $A$ et $L$ à l'étape $t$. À l'étape de calcul 0, les ensembles $A_0$ et $L_0$ sont vides. À l'étape de calcul $t+1$, on procède comme suit.

(1) Pour tout $\langle n, \tau \rangle \le t+1$, si $t+1$ est le plus petit tel que $U(\tau)[t+1] = n$, on énumère alors $(A_t \upharpoonright_{n+1}, |\tau|+1)$ dans $L$ à l'étape $t+1$.

(2) Puis, pour tout $e \le t+1$ tel que $A_t$ n'intersecte pas $W_e[t+1]$, on regarde s'il existe $n \ge 2e$ tel que $n \in W_e[t+1]$ et tel que

$$ \sum_{\substack{U(\tau)[t+1]\downarrow=m, \\ \text{avec } m \ge n}} 2^{-|\tau|} < 2^{-e-2}. $$
Si l'on trouve un tel entier $n$, on énumère alors $n$ dans $A$ à l'étape $t+1$. Puis, pour toute chaîne $\tau$ telle que $U(\tau)[t+1] = m$ pour $m \ge n$, on énumère $(A_{t+1} \upharpoonright_{m+1}, |\tau|)$ dans $L$ à l'étape $t+1$.

Cela termine la construction.

Assurons-nous d'abord que $L$ est bien un ensemble borné de requêtes. Le poids de $L$ qui vient de (1) est forcément inférieur à $1/2$, car dans $L$ on augmente par rapport à $U$ la longueur de chaque description de 1. Enfin, pour chaque $e$, le poids de $L$ qui provient de (2), c'est-à-dire de ce que l'on rajoute après avoir énuméré dans $A$ un élément de $W_e$, est forcément inférieur à $2^{-e-2}$, par construction. Le poids total pour tous les entiers $e$ est donc inférieur à $\sum_{e \in N} 2^{-e-2} = 1/2$. Le poids total de $L$ est donc borné par 1, ce qui implique que $L$ est un ensemble borné de requêtes.

D'après le théorème KC (3.3), on peut à présent définir une machine $M$ telle que $(\sigma, l) \in L$ implique $K_M(\sigma) \le l$. Il est clair par construction que $K(n) \le l$ implique $K_M(A \upharpoonright_n) \le l+1$. En effet, à chaque fois qu'une description de taille $l$ est découverte pour $n$ à l'étape $t$, on s'assure que l'on aura une description de taille $l+1$ pour $A_t \upharpoonright_n$. Par ailleurs, à chaque fois que $A_{t+1} \ne A_t$ à cause de l'énumération d'un élément $n$, on met à jour l'ensemble $L$ en s'assurant que chaque chaîne $A_t \upharpoonright_m$ pour $m \ge n$ aura des descriptions de même taille que toutes les descriptions de $m$ dans la version courante de $U$.

Il reste à montrer que $A$ est simple. Par l'argument usuel (voir la proposition 4.4), $A$ est co-infini, car on énumère au plus un élément dans $A$, pour chaque $W_e$, et cet élément est supérieur à $2e$. Soit à présent $e$ tel que $W_e$ est infini. On a $\sum_{U(\tau)\downarrow} 2^{-|\tau|} < 1$, ce qui implique qu'il existe $n$ suffisamment grand tel que $\sum_{U(\tau)\downarrow\ge n} 2^{-|\tau|} < 2^{-e-2}$. Donc, si $W_e$ est infini, on finira par trouver un tel entier $n$ et par l'énumérer dans $A$. $\blacksquare$

Il est clair que si l'ensemble $A$ est K-trivial, $\bar{A}$ l'est également. Il existe donc des K-triviaux $\Delta_2^0$ non c. e.

**Exercice 4.7.** (⋆) Montrer que la classe des ensembles K-triviaux est close par jointure Turing : si les ensembles $A_0$ et $A_1$ sont K-triviaux, alors $A_0 \oplus A_1$ est également K-trivial. ◇

## 4.3. Le théorème de Chaitin

On peut être tenté au premier abord de voir le résultat de Solovay comme un échec de la complexité préfixe. La complexité pleine permet d'échafauder une caractérisation propre et soignée des ensembles C-triviaux, mais qui semble perdre de son élégance avec $K$. Cette nouvelle classe d'ensembles mérite-t-elle que l'on s'y intéresse ? Nous allons voir que oui.
<figure><img src="image_112.png" /><figcaption>FIGURE 4.6 – Illustration de la preuve du théorème 4.5. L’ajout de $x$ dans $A$ à l’étape $t+1$ provoque une perte potentielle de $p_x$: l’alignement sur $K(m)$ qui a été fait pour tous les préfixes de $A$ de taille $m$ plus grande que $x$. Il existe nécessairement un entier $n$ suffisamment grand tel que cette perte sera bornée par $2^{-e-2}$ à n’importe quel temps de calcul $t$.</figcaption></figure>

La classe des K-triviaux est sans aucun doute la plus étudiée et la plus riche de l’aléatoire algorithmique. Les différents travaux de nombreux auteurs ont conduit à en donner pas moins d’une dizaine de caractérisations différentes. Nous y consacrerons donc le chapitre 20 entièrement.

Pour le moment, nous montrons simplement le résultat de Chaitin, central pour le chapitre 20 à venir : les K-triviaux sont tous $\Delta_2^0$. L’idée est la même que pour montrer que les ensembles C-triviaux sont calculables.

**Théorème 4.8 (Chaitin [29])**

Il existe une constante $c$ telle que, pour tout $\sigma \in 2^{<\mathbb{N}}$ et $d \in \mathbb{N}$, on a

$$|\{\sigma : |\sigma| = n \wedge K(\sigma) \le K(n) + d\}| < 2^c \times 2^d.$$

PREUVE. Soit $U$ notre machine universelle sans préfixe, et soit $M$ la machine sans préfixe qui sur $\tau$ renvoie $|U(\tau)|$. D’après le théorème 3.5, soit $c$ une constante telle que $P_M(\sigma) < 2^{-K(\sigma)} \times 2^c$ pour toute chaîne $\sigma$.

Supposons à présent que, pour $n$ fixé, on ait plus de $2^c \times 2^d$ chaînes $\sigma$ de taille $n$ telles que $K(\sigma) \le K(n) + d$. Alors, via $M$, on a également plus de $2^c \times 2^d$ descriptions distinctes de $n$ qui sont toutes de taille inférieure ou égale à $K(n) + d$. Cela nous donne l’inégalité

$$P_M(n) \ge 2^c \times 2^d \times 2^{-K(n)-d} = 2^c \times 2^{-K(n)},$$

ce qui contredit le choix de $c$. ■
**Corollaire 4.9 (Chaitin [29])**

Les ensembles K-triviaux sont tous $\Delta_2^0$.

PREUVE. Étant donné que $K \leq_T \emptyset'$, pour tout $d$, la classe

$$ \{X : \forall n K(X \upharpoonright_n) \leq K(n) + d\} $$

est une classe $\Pi_1^0(\emptyset')$. Par le théorème 4.8, cette classe contient un nombre fini d'éléments. Ils sont donc tous $\emptyset'$-calculables, par le corollaire 8-3.8 relativisé à $\emptyset'$. ■
<figure><img src="image_113.png" /></figure>
Chapitre 17

Boréliens, mesure et calculabilité

Le logicien, philosophe et mathématicien suédois Per Martin-Löf propose une notion d'aléatoire suivant un paradigme bien différent de celui de Chaitin/Levin : un ensemble aléatoire est un ensemble qui n'a aucune propriété « atypique », c'est-à-dire aucune propriété qui est vraie avec probabilité 0, étant donné des tirages indépendants d'une suite infinie de bits, via un processus aléatoire qui produit à chaque coup 0 ou 1 avec probabilité 1/2.

La formalisation mathématique de la théorie des probabilités a vu le jour au XXe siècle, avec les travaux de Kolmorogov, qui publia en 1933 son manuel *Fondements de la théorie des probabilités*. Kolmorogov s'appuie pour cela sur les travaux du début du XXe siècle de Borel et Lebesgue sur la théorie de la mesure et de l'intégration. La théorie de la mesure appliquée à ce que l'on appelle « les boréliens effectifs » est le concept central que nous utiliserons dans notre étude de l'aléatoire algorithmique.

1. Un peu d'histoire

Nous sommes au mois d'août de l'année 1900. Des mathématiciens du monde entier convergent vers la Sorbonne, où se tient leur deuxième congrès international. La belle époque bat son plein au cœur d'un Paris paisible. La tour Eiffel y fut érigée un an plus tôt, Sarah Bernhardt au sommet de sa gloire se produit au théâtre de la Renaissance, la première ligne de métro est en service, les frères Lumière projettent leurs premiers films sur le champ de Mars, et la grande roue de Paris vient d'y être construite, à l'occasion de
la cinquième exposition universelle, qui a accueilli plus de cinquante millions de visiteurs. Les bouleversements culturels et techniques qui marquent ce début de XXᵉ siècle font écho aux bouleversements mathématiques du moment.

## 1.1. Le congrès international de 1900

Émile Borel, alors jeune maître de conférence à l'ENS assiste au congrès international. Il y écoute Henri Poincaré, qui disserte avec talent de cette discipline émergente qu'est la logique mathématique et des questions philosophiques qu'elle pose. Contrairement à certains de ses contemporains, Poincaré n'est pas foncièrement opposé à la logique, mais il défend face à elle une attitude prudente et au fond empreinte d'une certaine lucidité [177] : « *En devenant rigoureuse, la science mathématique prend un caractère artificiel qui frapperait tout le monde ; elle oublie ses origines historiques ; on voit comment les questions peuvent se résoudre, on ne voit plus comment et pourquoi elles se posent.* » Poincaré, également physicien, considère que les mathématiques ne doivent pas s'éloigner de la physique, par laquelle elles gardent une connexion nécessaire avec le réel. Ce point de vue apparaît plus clairement quelques années plus tard dans son ouvrage « *Science et Méthode* », en 1908 [178] : « *La logique parfois engendre des monstres. On vit surgir toute une foule de fonctions bizarres qui semblaient s'efforcer de ressembler aussi peu que possible aux honnêtes fonctions qui servent à quelque chose. Plus de continuité, ou bien de la continuité, mais pas de dérivées [...] Autrefois, quand on inventait une fonction nouvelle, c'était en vue de quelque but pratique ; aujourd'hui, on les invente tout exprès pour mettre en défaut les raisonnements de nos pères, et l'on n'en tirera jamais que cela.* »

Le point de vue de Poincaré est opposé à celui de l'autre géant mathématique de l'époque : le mathématicien David Hilbert, pour qui les mathématiques se suffisent très bien à elles-mêmes en tant qu'ensemble de concepts abstraits. Et si ce deuxième congrès international de mathématiques est resté dans l'Histoire, c'est sans aucun doute dû à la conférence qu'y donne Hilbert, durant laquelle il énonce une liste de vingt-trois problèmes mathématiques non résolus, et qui marqueront la recherche du siècle à venir. Hilbert connaît bien les travaux de Cantor sur l'infini, et est sans doute un des plus fervents partisans de cette nouvelle mathématique, à laquelle la logique seule et non le réel donne sa réalité. Aussi est-ce tout naturellement qu'Hilbert place comme problème numéro 1 celui de l'hypothèse du continu : « *Existe-t-il un infini strictement compris entre celui des nombres entiers et celui des nombres réels ?* » C'est dans ce contexte que Borel commence sa carrière.
## 1.2. Le trio français

Fils d'un pasteur protestant, Émile Borel est né à Saint-Affrique en 1871. Élève brillant et polyvalent, il est reçu à dix-huit ans premier au concours de l'École polytechnique ainsi qu'à celui de l'École normale supérieure, dans laquelle il rentre en 1889. Il est ensuite reçu premier à l'agrégation de mathématiques en 1893, puis devient maître de conférence à Lille, puis à Paris quelques années plus tard. Il s'intéresse très vite aux travaux de Cantor, et montre rapidement son talent et sa créativité, en l'utilisant avec succès pour l'étude des fonctions. Il y initiera également ses élèves, parmi lesquels figurent deux étudiants exceptionnels : Henri Lebesgue et René Baire. Tous deux issus de familles très pauvres,

ils sortiront de leur condition sociale par leur travail et leur talent mathématique. Borel et ses deux élèves, le trio français, marqueront tous les trois une avancée majeure dans les mathématiques, à travers une utilisation ingénieuse des notions de « dénombrable » et de « nombres transfinis » développées par Cantor, et qui déboucheront sur la découverte des catégories de Baire, dont nous avons déjà parlé dans la section 10-2.2, sur celle des ensembles dit boréliens, et sur la théorie de la mesure et de l'intégration. C'est de ces deux dernières découvertes dont il est question dans ce chapitre.

<figure><img src="image_114.png" /><figcaption>Émile Borel, 1871-1956</figcaption></figure>

## 1.3. Le point de vue de Borel

Les recherches remarquables de notre trio français connaîtront leurs limites. Borel tout d'abord au fil de sa carrière fait de moins en moins confiance à la théorie des ensembles, encore mal formalisée, et sujette à de nombreux paradoxes. Borel écrira vers la fin de sa vie [107, p.59] « J'ai été extrêmement séduit dès l'âge de 20 ans, par la lecture des travaux de Cantor [...] Georg Cantor a apporté, dans l'étude des mathématiques, cet esprit romantique qui est l'un des côtés les plus séduisants de l'âme allemande ». Cette attirance déclinera avec le temps, et Borel adoptera petit à petit un point de vue proche de celui de Poincaré vis-à-vis de la théorie des ensembles, tout en lui ajoutant une touche constructiviste, une idée naturelle chez lui depuis ses