premiers travaux mathématiques, en substance : les objets que l'on mani-
pule doivent être descriptibles explicitement. De ces objets-là seulement on
peut garantir une certaine forme d'existence, le reste n'étant qu'abstraction
inaccessible. Borel utilise de fait, dès 1898 dans sa « Leçon sur la théorie des
fonctions » le mot *effectif* dans un sens proche de ce que l'on appelle au-
jourd'hui « calculable », concept encore non formalisé à l'époque, mais dans
lequel Borel — précurseur — décelait déjà une importance fondamentale. Il
fut ainsi le premier à définir les ensembles calculatoirement énumérables,
afin de résoudre le paradoxe de Berry (que nous avons déjà présenté dans la
section 16-1.3) : « Soit $n$ le plus petit nombre non définissable en moins de
cinquante mots. » Borel propose une nouvelle approche pour la résolution
de ce paradoxe [22] : si l'on considère la liste des phrases écrites en français
qui définissent un nombre de manière unique, il n'existe pour autant au-
cun algorithme permettant de trouver *effectivement* quel nombre est défini
par une phrase. Borel fait alors la première distinction entre ensembles
calculatoirement énumérables, qu'un algorithme peut mettre en bijection
avec $N$, et ensemble simplement dénombrable, pour lesquels on ne peut pas
nécessairement calculer une bijection avec $N$. Cet exemple montre le goût
prononcé de Borel pour le constructivisme mathématique. Arnaud Denjoy
raconte encore à propos de Borel [107, p.56] : « Le nombre avait pour lui
une réalité presque charnelle. Il déniait la qualité d'existence à la plupart
des nombres incommensurables, dont l'intervention est pourtant indispen-
sable pour fonder nos théories générales. Il exigeait des mathématiques une
clarté, une évidence cartésienne, c'est-à-dire qu'elles soient aussi proches
du sensuel que du rationnel ».

1.4. La fin du trio

Borel perdra petit à petit son intérêt pour la théorie des ensembles, qu’il
juge sans doute trop abstraite. Il faut dire que les mathématiques sont
loin d’être son seul domaine d’activité. Il est curieux de tout, et n’a aucun
mal à remplacer sa passion de jeunesse. Il crée en 1906 avec sa femme la
« Revue du Mois », journal scientifique et littéraire, il devient directeur
en 1910 de l’École normale supérieure, s’engage volontairement en 1914
durant la Première Guerre mondiale et prend rapidement de nombreuses
responsabilités politiques, d’abord député, puis chef de cabinet du ministère
de la guerre et responsable des services techniques de l’armement. Il sera
enfin un court moment ministre de la Marine après la guerre. Il participe
en 1936 à la création de l’organisation d’État de la Recherche, qui deviendra
plus tard le CNRS. Il sera également un membre actif de la résistance
durant la Seconde Guerre mondiale, et publiera toute sa vie de nombreux
ouvrages de mathématiques et de vulgarisation. Borel ne s’est donc pas
ennuyé, loin de là, et n’a sans doute pas seulement arrêté son activité de
recherche mathématique par manque de temps, mais aussi car il voulait
prendre ses distances avec ce qu'il appelait « les hautes mathématiques ».
Il déclare ainsi à son ami Paul Valéry en 1914 [107, p.83] qu'il était effrayé
des conséquences sur son esprit de la recherche en théorie des ensembles « à
cause de la fatigue qu'elle impose et qui fait craindre des troubles sérieux
à ceux qui s'imposent ce travail. » Les deux autres membres de notre trio
eurent leurs propres problèmes, et stoppèrent eux aussi leurs travaux.

Baire n'a pas une très bonne santé et souffre de jalousie envers son collègue Henri Lebesgue, dont les travaux — contrairement aux siens — eurent presque instantanément un retentissement international. Baire s'estime lésé par rapport à Lebesgue; qui occupe rapidement des postes prestigieux à la Sorbonne et au Collège de France, alors que lui doit se contenter de la faculté des sciences de Dijon<fnref n="1" />. Les problèmes de santé physique et psychologique de Baire l'empêchent de travailler durant de longues périodes, conduisant de surcroît à des difficultés financières. À cela s'ajoute la frustration de ce qu'il considère comme une non-reconnaissance de ses mérites scientifiques, et qui le plonge dans une grave dépression. Il obtient en 1914 un congé maladie, qui se prolongera jusqu'en 1932, date à laquelle il se suicide dans un hôtel genevois près du lac Léman.

Lebesgue n'a pas les problèmes physiques et psychologiques de Baire, mais
lui aussi souffre de jalousie : envers son mentor Émile Borel! Lebesgue
conteste à Borel la paternité de certaines idées sur la théorie de la mesure
et la relation entre les deux hommes se dégrade, comme en témoigne cette
lettre de 1917 adressée à Borel : « *Je vous l'ai dit... je n'ai plus en vous la*
*même confiance qu'autrefois... Pour le moment toute relation qui sortirait*
*de la banalité de la camaraderie serait de ma part, une hypocrisie. Ce ne*
*serait pas avec vous que je déjeunerais, ce serait avec de vieux souvenirs ...*
*Le genre de relations que nous avons eues depuis un an vous a assez fait*
*sentir mon état d'esprit pour que cette lettre ne vous surprenne pas trop.*
*Je crois cependant qu'elle vous fera quelques peines et j'ai conservé trop*
*d'amitié cachée pour vous pour ne pas en être peiné moi-même ». Ainsi*
s'éteint petit à petit l'élan créateur de l'école française de la théorie des
ensembles. C'est à quelques milliers de kilomètres de Paris, que sera repris
le flambeau, avec la naissance de la très fameuse école de Moscou. Il s'agit
là d'une autre histoire, que nous aborderons dans la section 29-1.

## 2. Premières intuitions sur la mesure

Essayons d'expliquer un peu ce que l'on entend par *mesure* en mathématiques. Un des buts de la théorie de la mesure est de formaliser la notion de « taille » des parties d'un ensemble.

<footnote n="1">1. Nous retranscrivons ici l'état d'esprit de Baire, sans préjuger aucunement des mérites — dont nous ne doutons pas — de l'université de Bourgogne.</footnote>
Considérons par exemple la ligne des réels. Nous avons une bonne intuition de ce qu'est la mesure d'un intervalle $[a, b]$, car celle-ci correspond à ce que l'on mesurerait effectivement en pratique avec une règle graduée : il s'agit du réel $b - a$. Nous écrirons alors $\lambda([a, b]) = b - a$, la fonction $\lambda$ désignant la mesure dite « standard », que l'on appelle généralement mesure de Lebesgue. Étant donné une réunion $[a, b] \cup [c, d]$ de deux intervalles disjoints, il paraît tout aussi naturel de définir

$$ \lambda([a, b] \cup [c, d]) = \lambda([a, b]) + \lambda([c, d]) = (b - a) + (d - c) $$

Ce que l'on entend par mesure d'un ensemble arbitraire de réels $I \subseteq \mathbb{R}$ est en revanche beaucoup moins clair. Nous verrons que quelle que soit la notion de mesure que l'on prend, dès lors qu'elle satisfait quelques propriétés raisonnables, par exemple la mesure d'une réunion disjointe est la somme des mesures, il existe nécessairement des ensembles non mesurables.

Dans le cas qui nous occupe, nous allons nous employer à définir une mesure sur des sous-parties de l'espace de Cantor. Comme nous l'avons vu dans la section 2-6, l'espace de Cantor peut être vu comme l'intervalle $[0, 1]$ en voyant toute suite binaire infinie $X \in 2^N$ comme le réel $0.X$ en développement binaire. En particulier, nous définirons $\lambda(2^N) = \lambda([0,1]) = 1$. La règle qui veut que la mesure des réunions disjointes est égale à la somme de la mesure des réunions fonctionne aussi pour les réunions dénombrables : par exemple,

$$ \begin{aligned} \lambda\left(\bigcup_{n \in \mathbb{N}} [2^{-2n-1}, 2^{-2n}]\right) &= \sum_{n \in \mathbb{N}} (2^{-2n} - 2^{-2n-1}) = \sum_{n \in \mathbb{N}} 2^{-2n}(1 - 2^{-1}) \\ &= 2^{-1} \sum_{n \in \mathbb{N}} 2^{-2n} = \frac{1}{2} \times \frac{1}{1 - \frac{1}{4}} = \frac{2}{3}. \end{aligned} $$

Chaque ouvert de l'espace de Cantor possède donc une mesure : un ouvert $U \subseteq 2^\omega$ est de la forme $U = \bigcup_{\sigma \in W}[\sigma]$. Notons que l'on peut toujours choisir $W$ de telle manière à ce que celui-ci soit sans préfixe : si $\sigma \preceq \tau$ et $\sigma, \tau \in W$, alors on peut toujours enlever $\tau$ de $W$, car $[\tau] \subseteq [\sigma]$. Pour un tel ensemble $W$ sans préfixe, on a donc $\lambda(U) = \sum_{\sigma \in W} 2^{-|\sigma|}$.

La règle de la mesure des réunions disjointes nous donne dès lors une mesure des ensembles fermés : si $C \subseteq 2^N$ est fermé, alors $\lambda(C) + \lambda(2^N \setminus C) = \lambda(2^N)$. Comme $\lambda(2^N) = 1$, nous avons $\lambda(C) = 1 - \lambda(2^N \setminus C)$, où $2^N \setminus C$ est un ouvert.

## 2.1. Classes $\Pi_2^0$

Pour pouvoir définir l'aléatoire de Martin-Löf, il est nécessaire d'étendre la mesure à des classes plus complexes encore que les fermés et les ouverts. À titre d'exemple, considérons la loi des grands nombres : une suite aléatoire
devrait avoir comme propriété que la limite de ses fréquences de 0 et de 1 parmi ses préfixes, existe et tende vers $1/2$ quand la taille des préfixes tend vers $+\infty$. Essayons de décrire la classe $\mathcal{A}$ des suites qui ne satisfont pas cette propriété. Il s'agit de la classe des suites $X$ telles que pour un $\varepsilon > 0$ donné, pour tout $n \in \mathbb{N}$ il existe $m \ge n$ tel que la fréquence de 0 dans le préfixe de $X$ de taille $m$ dépasse $1/2+\varepsilon$ ou est en dessous de $1/2+\varepsilon$. Pour $\varepsilon$ fixé, on peut décrire ces classes de la manière suivante : $\mathcal{A}_{\varepsilon} = \bigcap_{n} \mathcal{U}_{\varepsilon,n}$, où

$$ \mathcal{U}_{\varepsilon,n} = \bigcup_{m \ge n} [C_{\varepsilon,m}] \quad \text{et} \quad C_{\varepsilon,m} = \left\{ \sigma \in 2^m : \left| \frac{\#\{i \le m : \sigma(i) = 0\}}{m} - \frac{1}{2} \right| > \varepsilon \right\}, $$

où $[C_{\varepsilon,m}]$ dénote l'ouvert décrit par l'ensemble $C_{\varepsilon,m} \subseteq 2^{<\mathbb{N}}$, où $|\cdot|$ dénote la valeur absolue et $\#\cdot$ la taille d'un ensemble. Il est clair que chaque ensemble $\mathcal{U}_{\varepsilon,n}$ est une classe $\Sigma_1^0$ : un ouvert effectif. Chaque $\mathcal{A}_{\varepsilon}$ est donc une intersection dénombrable d'ouverts effectifs.

Nous appellerons classes $\Pi_2^0$ les intersections effectives d'ouverts effectifs. Quelle est la mesure de la classe $\Pi_2^0$ $\mathcal{A}_{\varepsilon} = \bigcap_{n} \mathcal{U}_{\varepsilon,n}$ ? Il est possible de montrer que la classe $\mathcal{A}_{\varepsilon}$ n'est ni ouverte ni fermée : elle est d'une complexité supérieure. En revanche, d'après le fait 10-2.2 chaque étape de l'intersection dénombrable est un ouvert, c'est-à-dire que, pour tout $n$, la classe $\mathcal{A}_{\varepsilon,n} = \bigcap_{m \le n} \mathcal{U}_{\varepsilon,m}$ reste une classe ouverte et même une classe $\Sigma_1^0$ (voir le lemme 3.5). Il s'ensuit que chaque classe $\mathcal{A}_{\varepsilon,n}$ est mesurable : en tant qu'ouvert, la mesure $\lambda(\mathcal{A}_{\varepsilon,n})$ est bien définie. Par ailleurs, $\mathcal{A}_{\varepsilon,n+1} \subseteq \mathcal{A}_{\varepsilon,n}$. À chaque étape, la mesure ne peut donc que diminuer et comme elle ne peut descendre en dessous de 0, elle a nécessairement une limite. On peut donc définir en toute logique

$$ \lambda\left(\bigcap_{n} \mathcal{U}_{\varepsilon,n}\right) = \lim_{n \to +\infty} \lambda(\mathcal{A}_{\varepsilon,n}) = \lim_{n \to +\infty} \lambda\left(\bigcap_{m \le n} \mathcal{U}_{\varepsilon,m}\right). $$

## 2.2. Lien avec les probabilités

Les notions de mesure, de classe $\Pi_2^0$ et d'autres classes de complexité supérieure, ont été formellement définies et étudiées par Borel et Lebesgue au début du XXe siècle. Si Lebesgue utilise surtout la mesure pour sa théorie de l'intégration, Borel a compris très tôt les liens entre mesure et probabilité, qu'il utilise par exemple en 1909 pour montrer que la loi des grands nombres est satisfaite avec probabilité 1 par les ensembles d'entiers [23]. Il faudra toutefois attendre les travaux de Kolmogorov en 1933 pour que la théorie de la mesure soit utilisée en toute généralité pour une axiomatique formelle de la théorie des probabilités [10].

L'analogie entre mesure et probabilité est simple : supposons que l'on tire des bits aléatoirement à pile ou face, en utilisant un processus qui donne 0
avec probabilité $1/2$ et $1$ avec probabilité $1/2$. Ce processus génère peut à petit une suite $Z \in 2^N$. La mesure d'une classe $B \subseteq 2^N$ correspond simplement à la probabilité que $Z$ appartiennent à $B$. L'idée de Martin-Löf sera donc de dire qu'une suite « aléatoire » ne devrait appartenir à aucune classe de mesure 0, c'est-à-dire à aucun ensemble « atypique ». Évidemment, chaque ensemble $Z$ appartient à la classe $\{Z\}$ qui est de mesure 0 — on vérifie en effet facilement que le complémentaire de $\{Z\}$ est un ouvert de mesure 1—, ce qui est problématique pour cette intuition : aucun ensemble n'est alors aléatoire. Martin-Löf propose alors de ne sélectionner qu'une partie de ces classes : les $\Pi_2^0$ dont la mesure converge vers 0 de manière effective.

### 3. Classes boréliennes

Nous commençons par présenter les classes sur lesquelles la mesure se définit naturellement, à la manière dont nous l'avons décrite dans la section précédente. Il s'agit de la hiérarchie borélienne, nommée d'après Émile Borel. Cette hiérarchie est écrite en gras (boldface) pour la distinguer de sa version effective (lightface) que nous définirons plus tard. Un « ~ » est parfois ajouté sous la notation de la hiérarchie borélienne pour éviter toute confusion — c'est ce qui est fait dans ce texte.

**Définition 3.1 (Hiérarchie borélienne).** Une classe $B \subseteq 2^N$ est $\Sigma_1^0$ si elle est ouverte et $\Pi_1^0$ si elle est fermée. On définit ensuite inductivement sur $n > 1$ :

1. une classe $B \subseteq 2^N$ est $\Sigma_{n+1}^0$ si elle est une réunion dénombrable de classes $\Pi_n^0$;

2. une classe $B \subseteq 2^N$ est $\Pi_{n+1}^0$ si elle est une intersection dénombrable de classes $\Sigma_n^0$.

Une classe est $\Delta_n^0$ si elle est à la fois $\Sigma_n^0$ et $\Pi_n^0$.

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

Notons que les classes $\Sigma_n^0$ sont les complémentaires dans $2^N$ des classes $\Pi_n^0$ (cela vient de l'égalité $2^N \setminus \bigcup_n A_n = \bigcap_n (2^N \setminus A_n)$). La hiérarchie borélienne est en quelque sorte une hiérarchie de complexité sur « la forme » des ensembles. Il est clair que les classes $\Sigma_n^0$ (respectivement $\Pi_n^0$) sont aussi $\Pi_{n+1}^0$ (respectivement $\Sigma_{n+1}^0$), car on peut toujours écrire $A = A \cup A \cup A \dots$ ou $A = A \cap A \cap A \dots$. Nous allons voir avec le lemme 3.12 que les classes $\Sigma_n^0$ sont aussi $\Sigma_{n+1}^0$, et que les classes $\Pi_n^0$ sont aussi $\Pi_{n+1}^0$. Nous verrons également que la hiérarchie borélienne est stricte : de la même manière qu'un ouvert n'est pas forcément un fermé, une intersection dénombrable
d'ouverts ne pourra pas forcément être décrite comme une réunion dénom-
brable de fermés, et ainsi de suite.

<figure><img src="image_116.png" /><figcaption>FIGURE 3.2 – *Hiérarchie borélienne*</figcaption></figure>

Souvenons-nous que les ouverts et fermés possèdent un analogue effectif,
que l'on note respectivement Σ₀₁ et Π₀₁. Nous allons maintenant voir com-
ment étendre cette correspondance en définissant les Σ₀ⁿ et Π₀ⁿ, corres-
pondant aux Σ₀ⁿ et Π₀ⁿ effectifs : on demande simplement à ce que les
réunions/intersections soient uniformes.

**Définition 3.3 (Hiérarchie borélienne effective).** Un code $\Sigma_1^0$ pour une classe $\Sigma_1^0 \mathcal{U} \subseteq 2^{<N}$ est un entier de la forme $\langle 1, 0, e \rangle$, où $W_e \subseteq 2^{<N}$ décrit $\mathcal{U}$, c'est-à-dire $\mathcal{U} = \bigcup_{\sigma \in W_e}[\sigma]$. Un code $\Pi_1^0$ pour son complémentaire est donné par $\langle 1, 1, e \rangle$. On définit par induction pour $n > 0$, comme suit.

(1) Une classe $\mathcal{B}$ est $\Sigma_{n+1}^0$ s'il existe un ensemble c. e. $W_e \subseteq \mathbb{N}$ énumérant des codes $\Pi_n^0$ de classes telles que $\mathcal{B} = \bigcup_n \mathcal{B}_n$, où $\mathcal{B}_n$ est la classe correspondant au $n$-ième code énuméré dans $W_e$. Un code $\Sigma_{n+1}^0$ pour $\mathcal{B}$ est donné par $\langle n+1, 0, e \rangle$.

(2) Une classe $\mathcal{B}$ est $\Pi_{n+1}^0$ s'il existe un ensemble c. e. $W_e \subseteq \mathbb{N}$ énumérant des codes $\Sigma_n^0$ de classes telles que $\mathcal{B} = \bigcap_n \mathcal{B}_n$, où $\mathcal{B}_n$ est la classe correspondant au $n$-ième code énuméré dans $W_e$. Un code $\Pi_{n+1}^0$ pour $\mathcal{B}$ est donné par $\langle n+1, 1, e \rangle$.

Une classe $\mathcal{B}$ est $\Delta_n^0$ si elle est à la fois $\Sigma_n^0$ et $\Pi_n^0$.

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

Remarquons la similarité des classes $\Sigma_{n+1}^0$ de l'espace de Cantor avec les ensembles d'entiers $\Sigma_{n+1}^0$. Ces derniers peuvent également être définis comme des réunions dénombrables de classes $\Pi_n^0$, via la correspondance usuelle réunion/quantification existentielle et intersection/quantification universelle.
**Exercice 3.4.** Montrer qu’à partir du code $\Sigma_n^0$ (resp. $\Pi_n^0$) d’une classe $\mathcal{A}$, on peut obtenir de manière calculable le code $\Pi_n^0$ (resp. $\Sigma_n^0$) de $2^N \setminus \mathcal{A}$. $\diamond$

Voyons un petit lemme similaire aux propositions 5-1.7 et 5-1.6 de la hiérarchie arithmétique pour les entiers, que nous utiliserons implicitement dans la suite.

**Lemme 3.5.** Les classes $\Sigma_n^0$ sont closes par intersections finies et réunions dénombrables effectives. Les classes $\Pi_n^0$ sont closes par réunions finies et intersections dénombrables effectives.

\star

**PREUVE.** Si une réunion dénombrable de classes $\Sigma_n^0$ est effective, on peut aisément calculer un code $\Sigma_n^0$ pour cette réunion. Par passage au complémentaire (exercice 3.4), les intersections dénombrables de classes $\Pi_n^0$ sont des classes $\Pi_n^0$.

Montrons que les classes $\Sigma_1^0$ sont closes par intersections finies. Soient donc $U_0 = \bigcup_{\sigma \in W_0}[\sigma]$ et $U_1 = \bigcup_{\sigma \in W_1}[\sigma]$ deux classes $\Sigma_1^0$. Alors,

$$ U_0 \cap U_1 = \bigcup_{\sigma_0 \in W_0, \sigma_1 \in W_1} [\sigma_0] \cap [\sigma_1]. $$

On peut également décrire l’ensemble c. e. des chaînes constituant l’ouvert $U_0 \cap U_1$ de la manière suivante : on énumère une chaîne $\sigma$ quand on la trouve dans $W_i$ pour $i < 2$ et quand un préfixe de $\sigma$ est énuméré dans $W_{i-1}$. Par passage au complémentaire, les classes $\Pi_1^0$ sont closes par réunions finies. Notons que l’on peut uniformément produire un code de $U_0 \cap U_1$ à partir de codes de $U_0$ et de $U_1$, et que l’on peut faire de même pour les réunions de deux fermés.

Supposons à présent que les classes $\Sigma_n^0$ sont closes par intersections finies et que les classes $\Pi_n^0$ sont closes par réunions finies. Soient $B_0 = \bigcup_{n \in W_0} A_{0,n}$ et $B_1 = \bigcup_{n \in W_1} A_{1,n}$ des classes $\Sigma_{n+1}^0$, avec chaque $A_{i,n}$ une classe $\Pi_n^0$ pour $i < 2$. Alors, $B_0 \cap B_1 = \bigcup_{n_0 \in W_0, n_1 \in W_1} A_{0,n_0} \cap A_{1,n_1}$. Par hypothèse d’induction, chaque classe $A_{0,n_0} \cap A_{1,n_1}$ est $\Pi_n^0$, et l’on peut uniformément en obtenir un code $\Pi_n^0$ à partir d’un code $\Pi_n^0$ de $A_{0,n_0}$ et de $A_{1,n_1}$. On peut donc facilement trouver un code pour la classe $B_0 \cap B_1$. Par passage au complémentaire (exercice 3.4), les classes $\Pi_{n+1}^0$ sont closes par réunions finies.

■

**Exercice 3.6.** S’assurer que la preuve du lemme 3.5 fournit aussi l’uniformité : étant donné des codes de $B_1$ et $B_2$ deux classes $\Sigma_n^0$ (resp. $\Pi_n^0$), on peut calculer un code $\Sigma_n^0$ (resp. $\Pi_n^0$) de la classe $B_1 \cap B_2$ (resp. $B_1 \cup B_2$). $\diamond$

Le lemme précédent permet de généraliser aux boréliens quelque chose qui a été vu dans la section 8-2.1 pour les ouverts et les fermés : les classes $\Pi_{n+1}^0$ peuvent toujours être considérées décroissantes.
Étant donné $\bigcap_n \mathcal{B}_n$, on peut considérer de manière équivalente la classe $\bigcap_n(\bigcap_{m \le n} \mathcal{B}_m)$. Notons que les classes usuelles — en général définies à l'aide de formules — tendent à être effectives. Voyons quelques exemples.

**Exemple 3.7.** (1) La classe des ensembles infinis est $\Pi_2^0$ :

$$ \{X : \forall n \exists m > n m \in X\} = \bigcap_n \{X : X(m) = 1 \text{ pour } m > n\}. $$

En utilisant les catégories de Baire, on montre facilement que cette classe n'est pas $\Sigma_2^0$. En effet, un fermé ne contenant que des ensembles infinis est forcément d'intérieur vide; et, dans le complémentaire d'une réunion de fermés d'intérieur vide, on trouve facilement en utilisant le lemme 10-2.14 un ensemble infini.

(2) La classe des ensembles qui sont des sauts Turing d'autres ensembles est $\Pi_2^0$. On montre facilement (voir l'exercice 4-6.4) l'existence d'une fonctionnelle $\Phi_e$ telle que $\Phi_e(X)$ est totale pour tout $X$ et telle que $\Phi_e(X') = X$ pour tout $X$. Dès lors, on définit l'ensemble des sauts comme :

$$ \left\{ X : \forall n \left( \begin{array}{l} X(n) = 1 \land \Phi_n(\Phi_e(X), n) \downarrow \\ \lor(X(n) = 0 \land \Phi_n(\Phi_e(X), n) \uparrow) \end{array} \right) \right\} \\ = \\ \bigcap_n \{ X : X(n) = 1 \land \Phi_n(\Phi_e(X), n) \downarrow \} \\ \cup \{ X : X(n) = 0 \land \Phi_n(\Phi_e(X), n) \uparrow \}, $$

ce qui est une intersection dénombrable de réunions d'un ouvert et d'un fermé. D'après le lemme 3.12, à venir, une intersection d'un ouvert et d'un fermé peut toujours être présentée comme une classe $\Pi_2^0$. En utilisant le théorème de la base low, on voit facilement que cet ensemble n'est pas $\Sigma_2^0$ puisqu'un ensemble low n'est pas le saut d'un autre ensemble. On peut consulter la correction de l'exercice 3.10 pour une preuve que cet ensemble n'est pas $\Sigma_2^0$.

(3) La classe des ensembles de densité supérieure positive — dont le ratio d'éléments parmi leurs préfixes est infiniment souvent plus grand qu'un certain $\varepsilon$ — est $\Sigma_3^0$ :

$$ \{ X : \exists \varepsilon > 0 \forall n \exists m > n \frac{\#\{i \le m : X(i) = 1\}}{m} > \varepsilon \}. $$

Là encore, on peut consulter la correction de l'exercice 3.11 pour une preuve que cet ensemble n'est pas $\Pi_3^0$.

(4) Toute classe dénombrable $\mathcal{B} = \{X_0, X_1, \dots\}$ est $\Sigma_2^0$. En effet, on a l'égalité $\mathcal{B} = \bigcup_n \{X_n\}$, où $\{X_n\}$ et un fermé.
Le lecteur pourra se rendre compte avec les exercices 3.10 et 3.11 de la difficulté, en général, de séparer les complexités boréliennes. Les techniques utilisées sont souvent des utilisations sophistiquées des catégories de Baire, via des forcings spécifiques.

Les exemples précédents illustrent le fait que la complexité borélienne des ensembles n'est pas liée à une puissance de calcul, mais réellement à une différence de forme : une intersection effective d'ouverts effectifs peut ne pas être de la forme d'une réunion de fermés, indépendamment de la puissance de calcul dont on dispose pour définir cette réunion de fermés. Cela nous conduit aussi à la considération suivante.

### Relativisation à un oracle

La hiérarchie borélienne effective se relativise à un oracle $X \in 2^N$, en remplaçant c. e. par $X$-c. e. dans la définition 3.3. Par ailleurs, on montre sans mal qu'un ensemble $\Sigma_n^0$ (resp. $\Pi_n^0$) est $\Sigma_n^0(X)$ (resp. $\Pi_n^0(X)$) pour un certain oracle $X$, qui par exemple encodera les différentes réunions/ intersections des différents ouverts/fermés constituant le borélien.

Voyons à présent d'autres exemples illustrant la relativisation à un oracle.

**Exemple 3.8.** (1) La classe des ensembles low est $\Sigma_2^0(\emptyset'')$ : chaque ensemble low est l'unique point d'un $\Pi_1^0(\emptyset')$. En revanche, $\emptyset''$ est nécessaire pour que la réunion de tous ces fermés soit uniforme. Le lecteur pourra consulter l'exercice 3.9 pour s'en assurer.

(2) La classe des ensembles high est $\Sigma_4^0(\emptyset'')$. Soit $T_{e,n} \subseteq 2^{<N}$ l'ensemble $\emptyset''$ -calculable des chaînes $\sigma$ telles que $\Phi_e(\sigma, n) \downarrow = \emptyset''(n)$. La classe des high peut se décrire comme :

$$ \bigcup_{e} \bigcap_{n} \bigcup_{\sigma \in T_{e,n}} \mathcal{A}_{e,n,\sigma}, $$

où $\mathcal{A}_{e,n,\sigma}$ est l'ensemble

$$ \{X : \forall i < |\sigma|, [(\sigma(i) = 1 \land \Phi_i(X, i) \downarrow) \lor (\sigma(i) = 0 \land \Phi_i(X, i) \uparrow)]\}. $$

Pour voir qu'il s'agit bien d'une description des ensembles high, il faut utiliser le fait que $\sigma \leq \tau$ implique $\mathcal{A}_{e,n,\tau} \subseteq \mathcal{A}_{e,n,\sigma}$ et $\sigma, \tau$ in-comparables impliquent $\mathcal{A}_{e,n,\tau} \cap \mathcal{A}_{e,n,\sigma} = \emptyset$. D'après le lemme 3.12, à venir, chaque classe $\mathcal{A}_{e,n,\sigma}$ est $\Sigma_2^0$ (uniformément en $e, n$ et $\sigma$) en tant que réunion d'un ouvert et d'un fermé, ce qui rend la classe des ensembles high $\Sigma_4^0(\emptyset'')$.

**Exercice 3.9.** (**) Établir que la classe des ensembles low n'est pas $\Sigma_2^0(\emptyset')$. ◇
**Exercice 3.10. (★★★)** Montrer que la classe des ensembles qui sont des sauts Turing n'est pas $\Sigma_2^0$. ◇

**Exercice 3.11. (★★★★)** Montrer que la classe des ensembles de densité supérieure positive — dont le ratio d'éléments parmi ses préfixes est infini-ment souvent plus grand qu'un certain $\varepsilon$ — n'est pas $\Pi_3^0$. ◇

Nous terminons par un dernier lemme dont la contrepartie pour la hiérarchie arithmétique est évidente, mais qui requiert un peu de travail dans le cas de la hiérarchie borélienne.

**Lemme 3.12.** Les classes $\Sigma_n^0$ ou $\Pi_n^0$ sont aussi $\Delta_{n+1}^0$. ★

**PREUVE.** Il est clair par définition que les classes $\Sigma_n^0$ sont $\Pi_{n+1}^0$ et que les classes $\Pi_n^0$ sont $\Sigma_{n+1}^0$. Les classes $\Sigma_1^0$ sont $\Sigma_2^0$ en tant que réunions effec-tives de cylindres, chaque cylindre étant une classe $\Pi_1^0$ dégénérée. Notons qu'à partir du code d'une classe $\Sigma_1^0$, on peut uniformément calculer un code $\Sigma_2^0$ de la même classe. Par passage au complémentaire (exercice 3.4), les classes $\Pi_1^0$ peuvent être uniformément transformées en classes $\Pi_2^0$. Sup-posons à présent que les classes $\Sigma_n^0$ sont uniformément $\Sigma_{n+1}^0$ et que les classes $\Pi_n^0$ sont uniformément $\Pi_{n+1}^0$. Soit $\bigcup_n A_n$ une classe $\Sigma_{n+1}^0$, où cha-que $A_n$ est $\Pi_n^0$. Par hypothèse d'induction, chaque $A_n$ peut être uni-formément transformé en classe $\Pi_{n+1}^0$, et donc $\bigcup_n A_n$ est $\Sigma_{n+2}^0$. Par passage au complémentaire (exercice 3.4), les classes $\Pi_{n+1}^0$ sont $\Pi_{n+2}^0$. ■

# 4. Mesure de Lebesgue

Nous allons maintenant voir comment étendre la mesure de Lebesgue — jusque-là définie pour les ouverts, les fermés et les classes $\Pi_2^0$ — à tous les boréliens de l'espace de Cantor, de manière à ce qu'elle possède des bonnes propriétés d'additivité.

**Notation**

On dénote par $\lambda$ la mesure de Lebesgue sur les boréliens de l'espace de Cantor, c'est-à-dire telle que $\lambda([\sigma]) = 2^{-|\sigma|}$ pour tout cylindre $\sigma$.

## 4.1. Définition de la mesure

Le mathématicien Caratheodory a montré que la mesure de Lebesgue, définie simplement sur les cylindres $[\sigma]$ comme étant $2^{-|\sigma|}$, se prolongeait de manière unique sur les boréliens en utilisant l'intuition donnée au début de ce chapitre pour mesurer les $\Pi_2^0$.
**Théorème 4.1 (Caratheodory)**

La mesure $\lambda$ telle que $\lambda([\sigma]) = 2^{-|\sigma|}$ pour tout cylindre $[\sigma]$, se prolonge de manière unique sur les boréliens en une fonction qui conserve la propriété d'additivité dénombrable : si $(B_n)_{n \in \mathbb{N}}$ est une suite de boréliens deux à deux disjoints, alors :

$$ \lambda\left(\bigcup_n B_n\right) = \sum_n \lambda(B_n). $$

Le prolongement se définit par induction de la manière suivante : pour une suite croissante (resp. décroissante) de boréliens $B_n \subseteq B_{n+1}$ (respectivement $B_{n+1} \subseteq B_n$), on a $\lambda(\bigcup_n B_n) = \sup_n \lambda(B_n)$ (respectivement $\lambda(\bigcap_n B_n) = \inf_n \lambda(B_n)$).

Le concept de mesure défini par Lebesgue en 1901 est au départ différent de celui présenté dans le théorème 4.1 [136] :

« Considérons un ensemble de points de $[a, b]$ ; on peut d'une infinité de manières enfermer ces points dans une infinité dénombrable d'intervalle ; la limite inférieure de la somme des longueurs de ces intervalles est la mesure de l'ensemble. Un ensemble E est dit mesurable si sa mesure augmentée de celle de l'ensemble des points ne faisant pas partie de E donne la mesure de $[a, b]$. Voici deux propriétés de ces ensembles : une infinité d'ensembles mesurables $E_i$ étant donnée, l'ensemble des points qui font partie de l'un au moins d'entre eux est mesurable ; si les $E_i$ n'ont deux à deux aucun point commun, la mesure de l'ensemble obtenu est la somme des mesures des $E_i$. L'ensemble des points communs à tous les $E_i$ est mesurable. »

Constatons que Lebesgue ne parle pas de classes boréliennes, mais à la place de classes mesurables (ou d'ensembles mesurables dans la terminologie ci-dessus) : il prétend que si chaque classe $(E_i)_{i \in \mathbb{N}}$ est mesurable, alors $\bigcup_i E_i$ est mesurable, tout comme $\bigcap_i E_i$. Il donne aussi la propriété d'additivité dénombrable. Mais pour définir la mesure d'une classe $B$ quelconque, il utilise le fait que la mesure des ouverts — des réunions disjointes d'intervalles — est définie sans ambiguïté pour l'esprit humain, pour définir alors la mesure de n'importe quelle classe $B$ comme étant

$$ \inf_{\mathcal{U} \text{ classe } \Sigma_1^0, \text{ avec } B \subseteq \mathcal{U}} \lambda(\mathcal{U}). $$

Notons que Lebesgue laisse entendre la possibilité que toutes les classes ne sont pas forcément mesurables. Il pose pour la mesurabilité d'une classe la condition que le calcul de sa mesure soit cohérent avec l'intuition que la mesure de $B \subseteq [a, b]$ plus la mesure de $[a, b] \setminus B$ doit correspondre à la mesure de $[a, b]$, c'est-à-dire $b - a$.

Caratheodory a formalisé l'intuition de Lebesgue sous le nom de mesure extérieure. Il est en effet possible de construire — à l'aide de l'axiome
du choix — des classes non mesurables de $[0,1]$ dans le sens imaginé par Lebesgue, c'est-à-dire telles que la mesure extérieure de l'une quelconque d'entre elles ajouté à la mesure de son complémentaire dans $[0,1]$ ne soit pas égale à 1. Nous nous apprêtons à voir toutefois que la définition de Lebesgue rejoint celle que nous avons donnée pour les classes boréliennes, qui sont elles toutes mesurables (voir le théorème 4.4).

## 4.2. Propriétés de la mesure

Résumons ici les propriétés de la mesure de Lebesgue qui seront utilisées régulièrement tout au long de cette partie.

### Propriétés de la mesure

* Mesure des classes de bases : $\lambda([\sigma]) = 2^{-|\sigma|}$.

* Mesure sur les boréliens (définie par induction) :

$$ \lambda\left(\bigcup_n \mathcal{B}_n\right) = \sup_n \lambda\left(\bigcup_{m \le n} \mathcal{B}_m\right) \text{ et } \lambda\left(\bigcap_n \mathcal{B}_n\right) = \inf_n \lambda\left(\bigcap_{m \le n} \mathcal{B}_m\right). $$

* Mesure du complémentaire :

$$ \lambda(\mathcal{A} \setminus \mathcal{B}) = \lambda(\mathcal{A}) - \lambda(\mathcal{A} \cap \mathcal{B}). $$

* Additivité : pour $(\mathcal{A}_n)_{n \in \mathbb{N}}$ une suite de classes mesurables deux à deux disjointes, on a

$$ \lambda\left(\bigcup_n \mathcal{A}_n\right) = \sum_n \lambda(\mathcal{A}_n). $$

* Sous-additivité : pour $(\mathcal{A}_n)_{n \in \mathbb{N}}$ une suite de classes mesurables, on a

$$ \lambda\left(\bigcup_n \mathcal{A}_n\right) \le \sum_n \lambda(\mathcal{A}_n). $$

Notons que la sous-additivité se déduit de l'additivité : si $\mathcal{A}_0$ et $\mathcal{A}_1$ ne sont pas disjoints, on a en revanche $\mathcal{A}_0 \cup \mathcal{A}_1 = \mathcal{A}_0 \cup (\mathcal{A}_1 \setminus \mathcal{A}_0)$, avec $\mathcal{A}_0$ disjoint de $\mathcal{A}_1 \setminus \mathcal{A}_0$. Par additivité de la mesure, on a donc

$$ \lambda(\mathcal{A}_0 \cup \mathcal{A}_1) = \lambda(\mathcal{A}_0) + \lambda(\mathcal{A}_1 \setminus \mathcal{A}_0) \le \lambda(\mathcal{A}_0) + \lambda(\mathcal{A}_1). $$

Nous allons à présent montrer que tout borélien $\mathcal{B}$ est mesurable dans le sens donné par Lebesgue : l'infimum de la mesure des ouverts contenant $\mathcal{B}$ correspond à la mesure de $\mathcal{B}$ comme définie inductivement dans le théorème 4.1. Si l'on y ajoute l'infimum de la mesure des ouverts contenant le complémentaire de $\mathcal{B}$, on obtient nécessairement 1. Nous montrerons aussi une version effective de cela, et nous avons besoin pour l'effectivité d'étudier le niveau de complexité calculatoire de la mesure d'un borélien.
### 4.3. Calcul de la mesure

Nous allons montrer que la mesure d'une classe $\Sigma_n^0$ est un réel approchable par la gauche relativement à $\emptyset^{(n-1)}$, et en particulier que la mesure d'une classe $\Sigma_1^0$ est un réel approchable par la gauche. Nous avons besoin pour cela d'un lemme sur les classes $\Sigma_1^0$ qui sera souvent réutilisé par la suite. Souvenons-nous de la définition 16-2.1 d'ensembles sans préfixe.

**Lemme 4.2.** Soit $U = [W]$ une classe $\Sigma_1^0$ pour un ensemble c. e. $W \subseteq 2^{<\mathbb{N}}$. On peut calculer uniformément en un code de $W$ le code d'un ensemble c. e. $W'$ sans préfixe tel que $U = [W']$. ★

**PREUVE.** À l'étape de calcul $t$, si une nouvelle chaîne $\sigma$ entre dans $W$, et si un préfixe de $\sigma$ appartient déjà à $W'$, on n'énumère pas $\sigma$ dans $W'$. Sinon, si des extensions $\tau \supsetneq \sigma$ sont déjà dans $W'$, alors on calcule $n$, la plus petite taille telle que les extensions de $\sigma$ dans $W'$ à cette étape soient toutes de taille inférieure à $n$ (ce qui est possible car, à chaque étape, $W'$ ne contient qu'un nombre fini d'éléments). On énumère alors dans $W'$ toutes les extensions de $\sigma$ de taille $n$ qui n'ont pas de préfixe dans $W'$.

Il est clair que $W'$ est sans préfixe, et que l'on a $[W] = [W']$. ■

**Ensemble sans préfixe minimal**

Un ensemble sans préfixe $W$ est *minimal* si pour toute chaîne $\sigma$ et tout entier $n$, on a $\sigma\tau \notin W$ pour au moins une chaîne $\tau$ de taille $n$. Notons que le lemme précédent ne nous garantit pas que l'ensemble sans préfixe que l'on énumère est minimal : il se peut que l'énumération sans préfixe contienne par exemple la chaîne $\sigma 0$ et $\sigma 1$, qui pourraient alors être remplacées par la chaîne $\sigma$. Tout ouvert $U$ est généré par un ensemble sans préfixe minimal $W$, mais il ne sera pas toujours possible d'obtenir $W$ de manière c. e.

Nous pouvons à présent passer à la proposition annoncée.

**Proposition 4.3.** Soit $n > 0$, et soit $\mathcal{B} \subseteq 2^{<\mathbb{N}}$ une classe $\Sigma_n^0$. Le réel $\lambda(\mathcal{B})$ est approchable par la gauche relativement à $\emptyset^{(n-1)}$ et uniformément en un code de $\mathcal{B}$. En particulier, $\lambda(\mathcal{B})$ est $\emptyset^{(n)}$-calculable uniformément en un code de $\mathcal{B}$. ★

**PREUVE.** Soit $\mathcal{B} = \bigcup_{\sigma \in W} [\sigma]$ une classe $\Sigma_1^0$ avec $W$ un ensemble c. e. Par le lemme 4.2, on peut supposer que $W$ est un ensemble sans préfixe. Alors, $\lambda(\mathcal{B}) = \sum_{\sigma \in W} 2^{-|\sigma|}$. Il est donc clair que $\lambda(\mathcal{B})$ est un réel approchable par la gauche uniformément en un code de $\mathcal{B}$.

Supposons que la mesure de toute classe $\Sigma_n^0$ soit $\emptyset^{(n)}$-calculable uniformément en son code. Soit $\mathcal{B} = \bigcup_m A_m$ une classe $\Sigma_{n+1}^0$, avec chaque $A_m$
une classe $\Pi_n^0$. Posons alors $C_m = \bigcup_{k \le m} A_k$. Comme $C_m \subseteq C_{m+1}$, il vient $\lambda(C_m) \le \lambda(C_{m+1})$. Aussi, par définition, on a $\lambda(\bigcup_m A_m) = \sup_m \lambda(C_m)$. Par le lemme 3.5 et l'exercice 3.6, chaque classe $C_m$ est $\Pi_n^0$, et l'on peut lui trouver un code $\Pi_n^0$ uniformément en $m$ et en un code de $\mathcal{B}$. Comme la mesure du complémentaire de chaque classe $C_m$ est $\emptyset^{(n)}$-calculable, alors la mesure de $C_m$ l'est également — comme 1 moins la mesure du complémentaire de $C_m$ dans $2^N$, — et elle l'est de plus uniformément en un code de $C_m$. La mesure $\mathcal{B}$ est donc le supremum de la suite $r_1 \le r_2 \le r_3 \le \dots$, où chaque $r_m = \lambda(C_m)$. Comme chaque $r_m$ est un réel $\emptyset^{(n)}$-calculable uniformément en $m$, alors $\lambda(\mathcal{B}) = r = \sup_m r_m$ est un réel approchable par la gauche relativement à $\emptyset^{(n)}$ et uniformément en un code de $\mathcal{B}$. ■

Nous sommes à présent prêts à montrer le théorème voulu, dans sa version effective.

**Théorème 4.4**

Pour tout $\mathcal{B} \subseteq 2^N$ classe $\Sigma_n^0$ et pour tout rationnel $\varepsilon > 0$, il existe :

(1) $\mathcal{U}$ une classe $\Sigma_1^0(\emptyset^{(n-1)})$ telle que $\mathcal{B} \subseteq \mathcal{U}$ et telle que $\lambda(\mathcal{U} \setminus \mathcal{B}) \le \varepsilon$;

(2) $\mathcal{F}$ une classe $\Pi_1^0(\emptyset^{(n-1)})$ telle que $\mathcal{F} \subseteq \mathcal{B}$ et telle que $\lambda(\mathcal{B} \setminus \mathcal{F}) \le \varepsilon$.

De plus, un code de $\mathcal{U}$ peut être calculé uniformément en $\varepsilon$ et en un code de $\mathcal{B}$, et un code de $\mathcal{F}$ peut être calculé à l'aide de $\emptyset^{(n)}$ uniformément en $\varepsilon$ et en un code de $\mathcal{B}$.

**PREUVE.** Soit $\mathcal{B}$ une classe $\Sigma_1^0$. Alors, le point (1) est évident. Pour le point (2), il suffit de considérer les approximations ouvertes/fermées de $\mathcal{U}$ à chaque étape de calcul $t$, données par $\mathcal{U}[t]$. On peut à l'aide de l'arrêt calculer pour tout $\varepsilon$ le plus petit $t$ tel que $\lambda(\mathcal{U}\setminus\mathcal{U}[t]) < \varepsilon$. Supposons le théorème vrai pour des classes $\Sigma_n^0$ et montrons qu'il est vrai pour des classes $\Sigma_{n+1}^0$. Soit $\mathcal{B} = \bigcup_m A_m$ une classe $\Sigma_{n+1}^0$ avec chaque $A_m$ une classe $\Pi_n^0$.

Montrons (1). Le lecteur peut s'aider de la figure 4.5 pour suivre la preuve. Le complémentaire $\overline{A}_m$ de chaque $A_m$ est $\Sigma_n^0$. Par hypothèse d'induction, d'après (2) on peut uniformément trouver pour tout $m$ à l'aide de $\emptyset^{(n)}$ une classe $\Pi_1^0(\emptyset^{(n-1)})$ $\mathcal{F}_m \subseteq \overline{A}_m$ telle que $\lambda(\overline{A}_m \setminus \mathcal{F}_m) \le \varepsilon 2^{-m-1}$, pour tout $m$. Soit $\mathcal{U}_m$ le complémentaire du fermé $\mathcal{F}_m$. En particulier, pour tout $m$, on a $\lambda(\mathcal{U}_m \setminus A_m) \le \varepsilon 2^{-m-1}$. Cela nous donne :

$$ 
\begin{align*}
\lambda(\bigcup_m \mathcal{U}_m \setminus \bigcup_m A_m) &\le \lambda(\bigcup_m (\mathcal{U}_m \setminus A_m)) \\
&\le \sum_m \lambda(\mathcal{U}_m \setminus A_m) \\
&\le \sum_m \varepsilon 2^{-m-1} \\
&\le \varepsilon.
\end{align*}
$$
<figure><img src="image_118.png" /><figcaption>FIGURE 4.5 – Illustration. Les rectangles sont les composantes $\Pi_n^0$ d'une classe $\Sigma_{n+1}^0$ croissante. Les contours arrondis en pointillés sont des ouverts contenant chaque composante. La partie grisée est la partie en trop, dont la mesure doit décroître suffisamment rapidement.</figcaption></figure>

Par ailleurs chaque $\mathcal{U}_m$ est une classe $\Sigma_1^0(\emptyset^{(n-1)})$ dont le code est calculable en $\emptyset^{(n)}$ uniformément. Donc, $\mathcal{U} = \bigcup_m \mathcal{U}_m$ est une classe $\Sigma_1^0(\emptyset^{(n)})$.

Montrons (2). Le lecteur peut s'aider de la figure 4.6 pour suivre la preuve. Par hypothèse d'induction, il existe d'après (1) une classe $\Sigma_1^0(\emptyset^{(n-1)}) \mathcal{U}_m$ telle que $\overline{\mathcal{A}}_m \subseteq \mathcal{U}_m$ et $\lambda(\mathcal{U}_m \setminus \overline{\mathcal{A}}_m) \le \varepsilon 2^{-m-2}$ pour tout $m$. Soit $\mathcal{F}_m$ le complémentaire de l'ouvert $\mathcal{U}_m$. On a alors $\lambda(\mathcal{A}_m \setminus \mathcal{F}_m) \le \varepsilon 2^{-m-2}$. D'après le lemme 3.5, chaque classe $\bigcup_{m \le k} \mathcal{A}_m$ pour $k \in \mathbb{N}$ est $\Pi_n^0$, et donc chaque classe $\bigcup_m \mathcal{A}_m \setminus \bigcup_{m \le k} \mathcal{A}_m$ pour $k \in \mathbb{N}$ est $\Sigma_{n+1}^0$. À l'aide de $\emptyset^{(n+1)}$, on cherche en utilisant la proposition 4.3 le plus petit $k$ tel que $\lambda(C) < \varepsilon/2$ pour $C = \bigcup_m \mathcal{A}_m \setminus \bigcup_{m \le k} \mathcal{A}_m$. On a alors :

$$ 
\begin{align*}
\lambda(\bigcup_m \mathcal{A}_m \setminus \bigcup_{m \le k} \mathcal{F}_m) &\le \lambda(C) + \lambda(\bigcup_{m \le k} \mathcal{A}_m \setminus \bigcup_{m \le k} \mathcal{F}_m) \\
&\le \lambda(C) + \lambda(\bigcup_{m \le k} (\mathcal{A}_m \setminus \mathcal{F}_m)) \\
&\le \frac{1}{2}\varepsilon + \frac{1}{2}\sum_{m \le k} \varepsilon 2^{-m-1} \\
&\le \varepsilon.
\end{align*}
$$

Comme chaque $\mathcal{F}_m$ est une classe $\Pi_1^0(\emptyset^{(n-1)})$ dont le code peut être trouvé uniformément en $m$, alors $\mathcal{F} = \bigcup_{m \le k} \mathcal{F}_m$ est aussi une classe $\Pi_1^0(\emptyset^{(n-1)})$ et en particulier $\Pi_1^0(\emptyset^{(n)})$, dont le code est uniforme en la borne $k$, qui elle est calculable en à l'aide de $\emptyset^{(n+1)}$. ■
<figure><img src="image_119.png" /><figcaption>FIGURE 4.6 – Illustration. Les rectangles sont les composantes $\Pi_n^0$ d'une classe $\Sigma_{n+1}^0$ croissante. Les contours arrondis en pointillés sont des fermés contenus dans chaque composante. La partie grisée est la partie qui manque, dont la mesure doit décroître suffisamment rapidement. De plus il ne sera pas nécessaire de prendre des classes fermées dans chaque composante : on peut s'arrêter quand les composantes de la classe $\Sigma_{n+1}^0$ n'ajoutent presque plus de mesure. Ainsi, on a bien une réunion finie de fermés qui reste fermée.</figcaption></figure>

**Exercice 4.7. (*)** Montrer que la borne calculatoire de la proposition 4.3 ne peut pas être simplifiée : pour tout $n$, il existe $B$ une classe $\Sigma_n^0$ telle que le réel $\lambda(B)$ permet de calculer $\emptyset^{(n)}$. $\diamond$
<figure><img src="image_120.png" /></figure>
Chapitre 18

Aléatoire au sens de Martin-Löf

Nous avons à présent les outils nécessaires pour définir l’aléatoire de Martin-Löf. L’idée est de définir un ensemble $X$ comme étant aléatoire s’il n’a aucune propriété « atypique », une propriété étant atypique si la classe des ensembles qui la partagent est de mesure 0.

# 1. Intuitions et définitions

Reprenons notre exemple de la loi des grands nombres de la section 17-2.1. Nous avions défini pour un certain $\varepsilon > 0$ la classe $\mathcal{A}_{\varepsilon} = \bigcap_{n} \mathcal{U}_{\varepsilon,n}$ où

$$ \mathcal{U}_{\varepsilon,n} = \bigcup_{m \ge n} [C_{\varepsilon,m}] \quad \text{et} \quad C_{\varepsilon,m} = \{ \sigma \in \mathbb{Z}^m : \left| \frac{\#\{i \le m : \sigma(i) = 0\}}{m} - \frac{1}{2} \right| > \varepsilon \}, $$

où $[C_{\varepsilon,m}]$ dénote l’ouvert décrit par l’ensemble $C_{\varepsilon,m} \subseteq 2^{\mathbb{N}}$. La classe $\mathcal{A}_{\varepsilon}$ contient tous les $X$ dont la fréquence de 1 parmi ses préfixes est infini-ment souvent au-dessus de $1/2 + \varepsilon$ ou alors infiniment souvent en dessous de $1/2 - \varepsilon$. Il est possible de montrer, en utilisant les inégalités de Hoeff-ding [93], que l’on a $\lambda([C_{\varepsilon,m}]) \le 2e^{-2m\varepsilon^2}$, pour tout $m$. Notons que les classes $([C_{\varepsilon,m}])_{m \in \mathbb{N}}$ ne sont pas forcément disjointes, et rappelons ici la propriété de sous-additivité de la mesure : si $(\mathcal{B}_n)_{n \in \mathbb{N}}$ est une suite quel-conque de classes mesurables, alors $\lambda(\bigcup_n \mathcal{B}_n) \le \sum_n \lambda(\mathcal{B}_n)$.

Posons $a_m = e^{-2m\varepsilon^2}$. Alors, pour tout $n$, en utilisant la sous-additivité de la mesure, on a $\lambda(\mathcal{U}_{\varepsilon,n}) \le \sum_{m \ge n} 2a_m = 2a_n \times (1+a_1^2+a_2^2+\dots)$. La formule de convergence des séries géométriques donne $\lambda(\mathcal{U}_{\varepsilon,n}) \le 2a_n/(1-a_1)$. Quand $n$ tends vers l’infini, la suite $2a_n/(1-a_1)$ converge clairement vers 0. Il s’ensuit que $\lambda(\mathcal{U}_{\varepsilon,n})$ se rapproche de plus en plus de 0 quand $n$ augmente, et donc que $\lambda(\bigcap_n \mathcal{U}_{\varepsilon,n}) = 0$.
Pour tout $\varepsilon$, chaque classe $\bigcap_n U_{\varepsilon,n}$ sera donc comme un test à passer pour être accepté dans le club des nombres aléatoires : le test en question est une classe de mesure 0 spécifique dans laquelle aucun aléatoire digne de ce nom ne peut figurer. La sous-additivité de la mesure implique que $\bigcup_{\varepsilon \in \mathbb{Q}^+} \bigcap_n U_{\varepsilon,n}$ est toujours une classe de mesure 0. Un nombre aléatoire digne de ce nom n'y figure donc pas. L'intuition de Martin-Löf est alors la suivante : les critères importants pour nous les mathématiciens, qui recherchent une définition formelle de l'aléatoire rejoignant notre intuition, sont capturables par des classes de mesure 0 du même ordre de complexité que chaque $\bigcap_n U_{\varepsilon,n}$ : des classes $\Pi_2^0$. Enfin, l'idée clef de Martin-Löf est la suivante : si l'on considère tous les $\Pi_2^0$ de mesure 0, on a affaire à une infinité dénombrable de tests que chaque suite aléatoire doit réussir. En revanche, avec une simple restriction sur les $\Pi_2^0$ que l'on considère, il est possible de tous les regrouper en un seul et même test, les contenant tous (nous le verrons avec le corollaire 2.2). Il suffit de considérer les classes $\Pi_2^0$ décroissantes de la forme $\bigcap_n U_n$ telles que $\lambda(U_n) \le 2^{-n}$ pour tout $n$ : on ne cherche pas simplement à ce que $\lambda(\bigcap_n U_n)$ soit égal à 0, mais aussi à ce que la convergence vers 0 se fasse suffisamment rapidement.

**Définition 1.1 (Martin-Löf [150]).** Un test de Martin-Löf est donné par $\bigcap_n U_n$, une classe $\Pi_2^0$ décroissante telle que $\lambda(U_n) \le 2^{-n}$ pour tout $n$. Un ensemble $Z \in 2^N$ passe le test si $Z \notin \bigcap_n U_n$. Si $Z$ ne passe pas le test, il est capturé par le test. ◇

Notons que la condition $\lambda(U_n) \le 2^{-n}$ pour un test $\bigcap_n U_n$ peut être relaxée : il suffit qu'il existe une fonction calculable $f: \mathbb{N} \to \mathbb{Q}$ telle que $\lim_n f(n) = 0$ et telle que $\lambda(U_n) \le f(n)$ pour tout $n$. On peut alors à partir de cela définir une autre classe $\Pi_2^0$ satisfaisant la définition donnée plus haut, en cherchant simplement pour tout $n$ de trouver la $n$-ième composante $U_{m_n}$ telle que $\lambda(U_{m_n}) \le 2^{-n}$.

**Définition 1.2 (Martin-Löf [150]).** Un ensemble $Z$ est aléatoire au sens de Martin-Löf s'il passe tous les tests de Martin-Löf. ◇

Nous avons montré ci-dessus que la classe $\bigcap_n U_{\varepsilon,n}$, capturant les ensembles dont la fréquence de 1 parmi ses préfixes est infiniment souvent au-dessus de $1/2 + \varepsilon$, ou infiniment souvent en dessous de $1/2 - \varepsilon$, est telle que

$$\lambda(U_{\varepsilon,n}) \le 2a_n/(1-a_1), \text{ où } a_n = e^{-2n\varepsilon^2}.$$

Chaque $U_n$ est donc bien borné par une fonction calculable en $n$, et qui tend vers 0. Donc, si $Z$ est un aléatoire de Martin-Löf, il ne peut appartenir à aucune classe $\bigcap_n U_{\varepsilon,n}$, et la fréquence de ses 1 parmi ses préfixes va converger vers $1/2$. On peut généraliser ce résultat comme suit.
**Exercice 1.3. (*)** Généraliser l'exemple donné en début de section pour montrer que pour tout ensemble $X$ aléatoire au sens de Martin-Löf, pour toute chaîne $\sigma$ de taille $n$, si $\tau_0\tau_1\tau_2... = X$ est le découpage de $X$ en chaînes de taille $n$, alors la fréquence des $i \le m$ tels que $\tau_i = \sigma$ converge vers $2^{-|\sigma|}$ quand $m$ tend vers $+\infty$.

Indication.– On pourra utiliser l'inégalité de Hoeffding pour $X$ écrit en base $2^n$. Pour toute base $q$ et tout $a < q$, l'inégalité de Hoeffding donne

$$ \lambda([C_{\varepsilon,m}^{q,a}]) \le 2e^{-2m\varepsilon^2}, $$ 
 où 
 $$ C_{\varepsilon,m}^{q,a} = \{ \sigma \in q^m : \left| \frac{\#\{i \le m : \sigma(i) = a\}}{m} - \frac{1}{q} \right| > \varepsilon \}. \quad \diamond $$

Nous donnons tout de suite un autre type de test, moins restrictif mais qui donne la même notion d'aléatoire, et qui nous sera utile de temps à autre.

## Définition 1.4

Un test de Solovay est donné par une suite calculable $(\mathcal{U}_n)_{n \in \mathbb{N}}$ de classe $\Sigma_1^0$ telle que $\sum_n \lambda(\mathcal{U}_n)$ est finie. Un ensemble $Z$ passe le test de Solovay si $Z$ n'appartient qu'à un nombre fini de classes $\mathcal{U}_n$. Sinon, $Z$ est capturé par le test. ◇

## Théorème 1.5

Un ensemble est aléatoire au sens de Martin-Löf si, et seulement si, il passe tous les tests de Solovay.

**PREUVE.** Une direction est triviale : tout test de Martin-Löf est un test de Solovay. Pour l'autre direction, supposons $Z$ capturé par un test de Solovay $(\mathcal{U}_n)_{n \in \mathbb{N}}$. Il doit exister $m$ suffisamment grand tel que $\sum_{n \ge m} \lambda(\mathcal{U}_n) < 1$. Notons que $Z$ est alors toujours capturé par $(\mathcal{U}_n)_{n \ge m}$, et l'on peut donc considérer sans perte de généralité $\sum_n \lambda(\mathcal{U}_n) < 1$.

On définit $\mathcal{V}_m$ comme étant la classe $\Sigma_1^0$ des ensembles $X$ appartenant au moins à $2^m$ classes $\mathcal{U}_{i_1}, \mathcal{U}_{i_2}, \dots, \mathcal{U}_{i_{2m}}$ distinctes. Soit $W_m$ l'ensemble sans préfixe minimal qui décrit la classe $\mathcal{V}_m$. Pour chaque chaîne $\sigma \in W_m$, il vient $[\sigma] \subseteq \mathcal{U}_{i_j}$ pour au moins $2^m$ classes $\mathcal{U}_{i_1}, \mathcal{U}_{i_2}, \dots, \mathcal{U}_{i_{2m}}$ distinctes. En particulier, $2^m \times 2^{-|\sigma|} = \lambda(\mathcal{U}_{i_1} \cap [\sigma]) + \dots + \lambda(\mathcal{U}_{i_{2m}} \cap [\sigma])$. Comme $\sigma_1, \sigma_2 \in W_m$ implique $[\sigma_1] \cap [\sigma_2] = \emptyset$, alors $\sigma_1, \sigma_2 \in W_m$ implique

$$ (\mathcal{U}_i \cap [\sigma_1]) \cap (\mathcal{U}_i \cap [\sigma_2]) = \emptyset, \text{ pour tout } i. $$

On a donc $2^m \sum_{\sigma \in W_m} 2^{-|\sigma|} \le \sum_n \lambda(\mathcal{U}_n) < 1$. Cela donne $2^m \lambda(\mathcal{V}_m) \le 1$, et donc $\lambda(\mathcal{V}_m) < 2^{-m}$. Ainsi, $\bigcap_m \mathcal{V}_m$ est un test de Martin-Löf, qui par hypothèse sur $Z$ le capture. ■
## 2. Les aléatoires de Martin-Löf et de Chaitin/Levin coincident

Martin-Löf dans son article [150] a montré comment construire un test universel : un test de Martin-Löf les contenant tous. Quelques années plus tard, Levin et Schnorr ont montré indépendamment que ce test universel pouvait en fait être défini en utilisant la complexité de Kolmogorov sans préfixe : les nombres aléatoires au sens de Chaitin/Levin sont exactement ceux qui sont aléatoires au sens de Martin-Löf. Ce résultat fait de l’aléatoire de Martin-Löf une notion d’aléatoire robuste, dans le sens où elle possède plusieurs caractérisations qui n’ont a priori rien à voir entre elles.

### Théorème 2.1 (Levin [140], Schnorr [193])

Un ensemble Z est aléatoire au sens de Martin-Löf ssi il est aléatoire au sens de Chaitin/Levin.

**PREUVE.** Supposons que Z ne soit pas aléatoire au sens de Chaitin/Levin. Alors, pour tout $c$, il existe $n$ tel que $K(Z|_n) < n-c$. Donc, Z appartient à l'ensemble $\bigcap_c U_c$, où $U_c = \{X : \exists n K(X|_n) < n-c\}$. Notons que chaque $U_c$ est une classe $\Sigma_1^0$ uniformément en $c$, et donc que $\bigcap_c U_c$ est une classe $\Pi_2^0$. Pour chaque $c \in \mathbb{N}$, soit $W_c$ un ensemble sans préfixe tel que $[W_c] = U_c$ et tel que pour tout $\sigma \in W_c$, $K(\sigma) < |\sigma| - c$. Notons que $W_c$ n'est pas nécessairement c. e. On a donc

$$ \sum_{\sigma \in W_c} 2^{-|\sigma|+c} \le \sum_{\sigma \in W_c} 2^{-K(\sigma)}. $$

Comme $K$ est la complexité sans préfixe, on a $\sum_{\sigma \in W_c} 2^{-K(\sigma)} \le 1$. Il en découle que $\lambda(\mathcal{U}_c) = \sum_{\sigma \in W_c} 2^{-|\sigma|} \le 2^{-c}$. Par suite, $\bigcap_c U_c$ est un test de Martin-Löf, et donc que $Z$ n'est pas aléatoire au sens de Martin-Löf.

Supposons à présent que $Z$ ne soit pas aléatoire au sens de Martin-Löf. Il existe alors $\bigcap_n U_n$ une classe $\Pi_2^0$ telle que $U_{n+1} \subseteq U_n$, telle que $\lambda(\mathcal{U}_n) \le 2^{-n}$ et pour laquelle $Z \in \bigcap_n U_n$. Soit $W_n \subseteq 2^{<\mathbb{N}}$ un ensemble $\Sigma_1^0$ sans préfixe tel que $\mathcal{U}_n = \bigcup_{\sigma \in W_n} [\sigma]$. On définit pour tout $c$ l'ensemble borné de requêtes $L_c$ en énumérant $(\sigma, |\sigma| - c + 1)$ dans $L_c$, pour tout $\sigma \in W_{2c}$. Le poids de $L_c$ est alors égal à $\sum_{\sigma \in W_{2c}} 2^{-|\sigma|+c-1} = 2^{c-1}\lambda(\mathcal{U}_{2c}) \le 2^{c-1}2^{-2c} = 2^{-c-1}$. En particulier la réunion des $L_c$ est un ensemble de requêtes dont le poids est borné par $\sum_{c \in \mathbb{N}} 2^{-c-1} = 1$. D'après le théorème KC (théorème 16-3.3), on a donc une machine $M$ sans préfixe telle que $K_M(\sigma) \le |\sigma| - c + 1$, pour toute chaîne $\sigma \in W_{2c}$. Il s'ensuit que pour tout $Z \in \bigcap_n U_n$, on a pour tout $c$ un entier $n$ tel que $K_M(Z|_n) \le n-c$. Aucun $Z \in \bigcap_n U_n$ n'est donc aléatoire au sens de Chaitin/Levin. ■
**Corollaire 2.2**

Il existe un test de Martin-Löf universel, c'est-à-dire un test de Martin-Löf qui les contient tous.

PREUVE. D'après la preuve du théorème précédent, l'ensemble

$$ \bigcap_c \mathcal{U}_c, \text{où } \mathcal{U}_c = \{X : \exists n K(X \upharpoonright_n) < n - c\} $$

est un test de Martin-Löf contenant tous les tests de Martin-Löf.

**Notation**

On appellera MLR les ensembles aléatoires au sens de Martin-Löf, de l'anglais « Martin-Löf random ».

**Corollaire 2.3**

Il existe un ensemble Z low et MLR. Il existe un ensemble Z calculatoirement dominé et MLR.

PREUVE. Comme la classe des MLR est $\Sigma_2^0$, c'est-à-dire une réunion effective de $\Pi_1^0$, chacune de ces classes $\Pi_1^0$ contient d'après le théorème 8-4.3 de la base low un ensemble low, et d'après le théorème 8-4.5 de la base calculatoirement dominé, un ensemble calculatoirement dominé.

# 3. Aléatoire et degré Turing

Voyons à présent un théorème qui fait écho au théorème 10-3.37 qui nous disait que pour $X$ non calculable, la classe des ensembles qui calculent $X$ est maigre. De la même manière, Sacks a montré que la classe des ensembles qui calculent une suite $X \in 2^N$ non calculable est de mesure nulle.

Nous utilisons pour cela un remarquable lemme de Lebesgue qui découle du théorème 17-4.4 : le fait que tout borélien $\mathcal{B}$ de mesure positive « concentre toute sa mesure dans des intervalles » : il n'est pas possible de construire $\mathcal{B}$ de mesure disons 1/4, de telle manière à ce que pour tout $\sigma$, la classe $\mathcal{B} \cap [\sigma]$ ne contienne qu'un quart de $[\sigma]$ en termes de mesure. Il y aura forcément un intervalle $[\sigma]$ au sein duquel $\mathcal{B}$ occupe « presque toute la place ». On introduit pour cela la notation suivante.

**Notation**

Soit $\mathcal{B} \subseteq 2^N$ un borélien et soit $[\sigma]$ un cylindre. On note $\lambda(\mathcal{B} | [\sigma])$ pour la mesure de $\mathcal{B}$ relativement à $[\sigma]$, c'est-à-dire :

$$ \lambda(\mathcal{B} | [\sigma]) = \frac{\lambda(\mathcal{B} \cap [\sigma])}{\lambda([\sigma])}. $$
Par exemple, si $\lambda(\mathcal{B} | [\sigma]) = 1/2$, cela signifie que $\mathcal{B}$ occupe $\ll$ la moitié de la place $\gg$ dans le cylindre $[\sigma]$. Voyons à présent le lemme de densité Lebesgue.

**Lemme 3.1 (Lemme de densité de Lebesgue)**

Soit $\mathcal{B}$ un borélien de mesure positive. Alors, pour tout $\varepsilon > 0$ il existe un cylindre $[\sigma]$ tel que $\lambda(\mathcal{B} | [\sigma]) > 1 - \varepsilon$. ★

**PREUVE.** L'idée est simple. D'après le théorème 17-4.4, on peut approximer $\mathcal{B}$ par un ouvert $\mathcal{U}$ le contenant et dont la mesure est aussi proche de $\mathcal{B}$ que l'on le souhaite. Pour un ouvert dont la mesure est suffisamment proche de celle de $\mathcal{B}$, il n'est pas possible que la mesure de $\mathcal{B}$ à l'intérieur de chaque cylindre $[\sigma]$ de l'ouvert soit trop petite, sinon la mesure totale de $\mathcal{B}$ est trop petite par rapport à celle de $\mathcal{U}$. Nous donnons à présent la preuve formelle.

Fixons $\varepsilon > 0$. D'après le théorème 17-4.4, il existe un ouvert $\mathcal{U} \supseteq \mathcal{B}$ tel que $\lambda(\mathcal{U} \setminus \mathcal{B}) < \varepsilon\lambda(\mathcal{B})$. Soit $W \subseteq 2^{\mathbb{N}}$ sans préfixe tel que $\mathcal{U} = \bigcup_{\sigma \in W} [\sigma]$. Notons que l'on a $\lambda(\mathcal{B}) = \sum_{\sigma \in W} \lambda(\mathcal{B} \cap [\sigma])$. Supposons par l'absurde que, pour tout $\sigma \in W$, on ait $\lambda(\mathcal{B} | [\sigma]) \le 1 - \varepsilon$. Alors,

$$ \sum_{\sigma \in W} \lambda(\mathcal{B} \cap [\sigma]) \le \sum_{\sigma \in W} (1-\varepsilon)\lambda([\sigma]) = (1-\varepsilon) \sum_{\sigma \in W} \lambda([\sigma]) = (1-\varepsilon)\lambda(\mathcal{U}). $$

On a donc $\lambda(\mathcal{B}) \le (1 - \varepsilon)\lambda(\mathcal{U})$. Mais, par hypothèse,

$$ \lambda(\mathcal{U}) - \lambda(\mathcal{B}) = \lambda(\mathcal{U} \setminus \mathcal{B}) < \varepsilon\lambda(\mathcal{B}) \le \varepsilon\lambda(\mathcal{U}). $$

Cela donne $\lambda(\mathcal{B}) > \lambda(\mathcal{U}) - \varepsilon\lambda(\mathcal{U}) = (1 - \varepsilon)\lambda(\mathcal{U})$, et une contradiction. ■

Notons que Lebesgue a montré quelque chose de plus fort encore, que nous verrons avec le théorème 19-4.6 : les intervalles $\sigma$ du lemme précédent sont en fait très nombreux : pour presque tous les $X \in \mathcal{B}$, la quantité $\lambda(\mathcal{B} | [X \upharpoonright_n])$ tend vers 1 quand $n$ tend vers $+\infty$. Voyons à présent le théorème de Sacks.

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

Soit $Y \in 2^{\mathbb{N}}$ non calculable. Alors, $\lambda(\{X \in 2^{\mathbb{N}} : X \ge T Y\}) = 0$.

**PREUVE.** Soit $\Phi$ une fonctionnelle Turing. Supposons par l'absurde que $\lambda(\{X \in 2^{\mathbb{N}} : \Phi(X) = Y\}) > 0$. D'après le lemme 3.1 de densité de Lebesgue, il existe une chaîne $\sigma$ telle que $\lambda(\{X \in 2^{\mathbb{N}} : \Phi(X) = Y\} | [\sigma]) > 1/2$.

On décrit à présent un algorithme pour calculer $Y$, dont le principe se résume à un $\ll$ vote à la majorité $\gg$ : pour tout $n$ et pour tout $i \in \{0, 1\}$, on énumère petit à petit l'ouvert $\mathcal{U}_{n,i}$ décrit par les chaînes $\tau \succeq \sigma$ telles que $\Phi(\tau, n) \downarrow = i$. D'après notre hypothèse sur $\sigma$, pour tout $n$, on doit avoir $\lambda(\mathcal{U}_{n,i} | [\sigma]) > 1/2$, pour $i = Y(n)$. Notons que pour des raisons
évidentes de « manque de place », on ne peut pas avoir $\lambda(U_{n,i} | [\sigma]) > 1/2$, pour $i \neq Y(n)$. Il suffit donc d'attendre d'avoir $\lambda(U_{n,i} | [\sigma]) > 1/2$, pour un certain $i$. À ce moment, on est sûr que $Y(n) = i$.

L'algorithme contredit le fait que $Y$ est non calculable. Il s'ensuit que

$$ \lambda(\{X \in 2^N : \Phi(X) = Y\}) = 0. $$

Comme c'est le cas pour toutes les fonctionnelles, et qu'une réunion dénombrable d'ensembles de mesure 0 est encore de mesure 0, on en déduit donc l'égalité $\lambda(\{Y \in 2^N : Y \geq_T X\}) = 0$. ■

Le théorème précédent implique qu'un ensemble $Z$ suffisamment aléatoire, ne peut pas calculer un ensemble non calculable $Y$. Cela montre en particulier que les algorithmes probabilistes sont impuissants à fournir plus de puissance de calcul : à supposer que l'on dispose d'un moyen de produire des bits aléatoires (via un processus physique par exemple), la probabilité pour que la suite produite permette par exemple de calculer l'arrêt est nulle.

Nous voyons à présent un théorème dual : étant donné un ensemble arbitraire, on peut toujours trouver un aléatoire de Martin-Löf le calculant. L'idée générale est la suivante : étant donné un arbre calculable $T$ où chaque nœud a au moins deux extensions incomparables, il est trivial de calculer une bijection entre $2^N$ et $[T]$ : si $f(\sigma)$ est défini, alors $f(\sigma_0)$ et $f(\sigma_1)$ sont envoyés chacun vers les premières extensions incomparables de $f(\sigma)$ dans $T$. Comme la bijection est calculable, on en déduit que $[T]$ contient un élément Turing équivalent à n'importe quel ensemble.

Si à présent l'arbre $T$ contient en plus des feuilles — comme c'est la cas pour les arbres qui représentent des classes $\Pi_1^0$, l'algorithme ne fonctionne plus du tout. Le problème est de savoir quel nœud est « réellement » branchant : il se peut qu'un nœud soit branchant, mais que l'une de ses extensions n'aboutisse finalement qu'à des feuilles. Il est en fait possible de construire des classes $\Pi_1^0$ indénombrables dont aucun membre ne calcule l'arrêt, ou même dont aucun membre ne calcule d'ensemble Martin-Löf aléatoire [38, Lemme 5.1]. En revanche, quand la classe $\Pi_1^0$ en question est de mesure positive, la situation change : la mesure positive nous donne une certaine garantie sur le fait que « beaucoup » de nœuds sont branchants, ce qui nous permet de développer un encodage — non calculable — de n'importe quel élément de telle manière à ce qu'un algorithme de décodage soit possible. Nous avons pour cela besoin d'un lemme garantissant la rapidité avec laquelle on peut trouver des nœuds branchants dans un arbre de mesure positive.
**Lemme 3.3 (Kučera [128])**

Soit $\mathcal{B}$ un borélien. Supposons $\lambda(\mathcal{B} | [\sigma]) \ge 2^{-n}$. Alors, il existe deux extensions distinctes $\tau_0, \tau_1 \supseteq \sigma$ de taille $|\sigma| + n + 1$ telles que $\lambda(\mathcal{B} | [\tau_i]) \ge 2^{-n-1}$.★

PREUVE. Il s'agit d'un simple argument de comptage : supposons que pour toutes les chaînes $\tau$ de taille $|\sigma| + n + 1$ qui étendent $\sigma$, sauf une, on ait $\lambda(\mathcal{B} | [\tau]) < 2^{-n-1}$. Alors, en considérant $\tau$ tel que $|\tau| = |\sigma| + n + 1$, on a :

$$ 
\begin{align*}
\lambda(\mathcal{B} \cap [\sigma]) &\le 2^{-|\sigma|-n-1} + (2^{n+1}-1)2^{-|\tau|-n-1} \\
&\le 2^{-|\sigma|-n-1} + (2^{n+1}-1)2^{-|\sigma|-2n-2} \\
&\le 2^{-|\sigma|-n-1} + 2^{n+1}2^{-|\sigma|-2n-2} - 2^{-|\sigma|-2n-2} \\
&\le 2^{-|\sigma|-n-1} + 2^{-|\sigma|-n-1} - 2^{-|\sigma|-2n-2} \\
&< 2^{-|\sigma|-n},
\end{align*}
$$

ce qui contredit $\lambda(\mathcal{B} | [\sigma]) \ge 2^{-n}$. ■

D'après le lemme p, notons que si $\mathcal{B}$ est une classe $\Pi_1^0$ de mesure positive et que $T$ soit l'arbre calculable qui le représente, alors $\lambda([T] | [\sigma]) \ge 2^{-n}$ implique que la prochaine extension branchante de $\sigma$ arrivera avant $n+1$ bits.

**Théorème 3.4 (Kučera [128], Gács [70])**

Soit $X \in 2^N$. Alors, il existe $Z \in 2^N$ un ensemble MLR tel que $Z \ge_T X$.

PREUVE. On montre le théorème suivant. Soit $\mathcal{P}$ une classe $\Pi_1^0$ de mesure positive; alors, pour tout $X$ il existe $Z \in \mathcal{P}$ tel que $Z \ge_T X$. Le lecteur peut consulter la figure 3.5 pour une illustration de la preuve. Fixons $X$. Construisons notre élément $Z \in \mathcal{P}$ tel que $Z \ge_T X$. Fixons d'abord $c$ tel que $\lambda(\mathcal{P}) > 2^{-c}$. On définit, en rapport avec le lemme 3.3, les constantes $m_0 = 0$ et $m_{n+1} = m_n + c + n + 1$.

On définit $\sigma_0 = \epsilon$. Supposons que $\sigma_n$ de taille $m_n$ est défini tel que

$$ \lambda(\mathcal{P} | [\sigma_n]) \ge 2^{-c-n}. $$

On définit une extension $\sigma_{n+1}$ avec la même propriété. D'après le lemme 3.3, il existe deux extensions $\tau_0, \tau_1$ distinctes de taille $m_n + c + n + 1$ telles que $\lambda(\mathcal{P} | [\tau_i]) \ge 2^{-c-(n+1)}$. Si $X(n) = 0$, on définit alors $\sigma_{n+1}$ comme l'extension la plus à gauche vérifiant l'inégalité. Si $X(n) = 1$, on définit alors $\sigma_{n+1}$ comme l'extension la plus à droite vérifiant l'inégalité. Quant à $Z$, il est défini comme le point limite de $\sigma_0 < \sigma_1 < \dots < \sigma_n < \sigma_{n+1} < \dots$.

Il est clair que $Z \in \mathcal{P}$. On doit maintenant détailler la manière dont on peut utiliser $Z$ pour calculer $X$. Pour trouver le bit $X(n)$, soit $\sigma = Z \lfloor_{m_n}$. On co-énumère l'ensemble $A$ des chaînes $\tau \supseteq \sigma$ de taille $m_{n+1}$ telles
<figure><img src="image_121.png" /><figcaption>FIGURE 3.5 – Illustration de la preuve du théorème de Kučera/Gács. On a défini notre chaîne $\sigma_n$ de taille $m_n$. Nous avons la garantie qu'il existe deux chaînes distinctes $\tau_0, \tau_1$ de taille $m_{n+1}$ et telles que l'on puisse continuer la construction à partir de n'importe laquelle des deux. Il suffit de choisir $\tau_0$ comme la plus à gauche de ces chaînes et $\tau_1$ comme étant la plus à droite. On choisit $\sigma_{n+1} = \tau_0$ pour encoder un 0, et $\sigma_{n+1} = \tau_1$ pour encoder un 1. Pour le décodage, en ayant la connaissance de $\sigma_n$ et $\sigma_{n+1}$, il suffit alors d'attendre que suffisamment de nœuds de l'arbre étendant $\sigma_n$ se terminent en feuille — plus précisément que la condition de mesure les concernant descend sous un certain seuil — jusqu'à ce que $\sigma_{n+1}$ devienne le nœud le plus à gauche ou le plus à droite de ce qu'il reste. À ce moment, on sait quel bit a été encodé.</figcaption></figure>

que $\lambda(\mathcal{P} | [\tau]) \ge 2^{-c-(n+1)}$. Si jamais $Z \upharpoonright_{m_{n+1}}$ apparaît à une certaine étape de calcul $t$ comme étant la chaîne la plus à gauche de $A[t]$, alors $X(n) = 0$. Si jamais $Z \upharpoonright_{m_{n+1}}$ apparaît à une certaine étape de calcul $t$ comme étant la chaîne la plus à droite de $A[t]$, alors $X(n) = 1$. Par construction, un de ces deux événements doit forcément arriver. ■

## 4. Aléatoire et degré DNC

Le théorème 3.4 de Kučera/Gács nous dit qu'il existe un aléatoire de Martin-Löf *au-dessus* de chaque degré Turing, mais pas nécessairement dans chaque degré Turing. Nous allons en fait voir que si par exemple tout ensemble 1-générique peut être calculé par un ensemble Martin-Löf aléatoire, aucun ensemble Martin-Löf aléatoire ne peut être en revanche calculé par un ensemble 1-générique. L'idée est simplement que tout Martin-Löf aléatoire est de degré DNC et, comme nous l'avons vu avec le théo-
rème 10-3.21, aucun ensemble 1-générique ne borne de degré DNC. Précisé-
ment, nous allons montrer le théorème suivant, qui donne deux autres
caractérisations des degrés DNC. L'équivalence (1) ↔ (2) a été montrée
par Kjos-Hanssen, Merkle et Stephan [112], et l'équivalence (1) ↔ (3) par
Greenberg et Miller [76].

Théorème 4.1

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

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

(2) $X$ calcule une fonction $f: n \to 2^{<N}$ telle que $K(f(n)) \ge n$;

(3) $X$ calcule un sous-ensemble infini d'un ensemble MLR.

Afin de montrer (1) → (3), nous utiliserons un autre lemme de Kučera.

**Lemme 4.2 (Kučera [128]).** Soit $\mathcal{P}$ une classe $\Pi_1^0$ de mesure positive. Il existe $\mathcal{Q} \subseteq \mathcal{P}$ une sous-classe $\Pi_1^0$ de mesure positive et un entier $c$ tels que, pour $\mathcal{P}_e$ la classe $\Pi_1^0$ de code $e$, on a $\mathcal{Q} \cap \mathcal{P}_e \neq \emptyset \to \lambda(\mathcal{Q} \cap \mathcal{P}_e) > 2^{-e-c}$. ★

PREUVE. Soit $c$ tel que $\lambda(\mathcal{P}) > 2^{-c+1}$. On définit $\mathcal{Q}$ comme étant la classe qui co-énumère $\mathcal{P}$ et dans le même temps, à chaque étape $s$, pour tout $e \le s$, si la mesure de $\mathcal{Q}[s] \cap \mathcal{P}_e[s]$ descend en dessous $2^{-e-c}$, enlève $\mathcal{P}_e[s]$ de $\mathcal{Q}[s]$. Pour chaque entier $e$, on enlève un morceau d'une mesure d'au plus $2^{-e-c}$. La mesure totale enlevée est dès lors bornée par $\sum_{e \in \mathbb{N}} 2^{-e-c} = 2^{-c+1}$. Comme $\lambda(\mathcal{P}) > 2^{-c+1}$, on a $\lambda(\mathcal{Q}) > 0$. ■

Nous pouvons à présent montrer le théorème annoncé.

PREUVE DU THÉORÈME 4.1. Montrons (1) → (2). Supposons X de degré DNC. Pour tout n, on peut calculer le code $a_n$ de l'ensemble $W_{a_n}$ qui énumère toutes les chaînes $\sigma$ telles que $K(\sigma) < n$. Notons que

$$
|W_{a_n}| < \sum_{m<n} 2^m = 2^n.
$$

D'après le théorème 7-2.6, l'ensemble $X$ calcule donc uniformément en $n$
une chaîne $\sigma \notin W_{a_n}$, et donc telle que $K(\sigma) \ge n$.

Montrons à présent (2) → (1). Supposons que $X$ ne soit pas de degré DNC.
Alors, pour toute fonction $f \le_T X$, on a $f(n) = \Phi_n(n) \downarrow$ pour une infinité
de $n$. Or, $\Phi_n(n) \downarrow$ implique $K(\Phi_n(n)) <^+ K(n)$ (voir l'exercice 16-2.3 si
cette étape n'est pas claire), et l'on a $K(n) \le^+ \log_2(n) + 2 \log_2(\log_2(n))$,
d'après la proposition 16-2.5, ce qui donne

$$
K(\Phi_n(n)) \le \log_2(n) + 2 \log_2(\log_2(n)).
$$

Or, $\log_2(n) + 2 \log_2(\log_2(n)) < n$, pour $n$ suffisamment grand.
Montrons à présent (1) → (3). Soit X de degré DNC. Soit $\mathcal{P}$ une classe $\Pi_1^0$ de mesure positive ne contenant que des ensembles aléatoires au sens de Martin-Löf. D'après le lemme 4.2, on peut supposer qu'il existe $c \in \mathbb{N}$ tel que l'on a on a $\mathcal{P} \cap \mathcal{P}_e \neq \emptyset$ implique $\lambda(\mathcal{P} \cap \mathcal{P}_e) > 2^{-c-e}$ pour $\mathcal{P}_e$ la classe $\Pi_1^0$ de code $e$. Pour un ensemble $S \subseteq \mathbb{N}$ quelconque, on définit

$$Q_S = \{Y : S \subseteq Y\}.$$

Notons que $Q_S$ est $\Pi_1^0$ pour tout $S \subseteq \mathbb{N}$ fini. Supposons que l'on ait défini $S_n \subseteq \mathbb{N}$ de taille $n$ tel que $Q_{S_n}$ est de code $e_n$ et tel que $\mathcal{P} \cap Q_{S_n} \neq \emptyset$. Soit $W_n$ l'ensemble c. e. des entiers $a$ tels que $\mathcal{P} \cap Q_{S_n \cup \{a\}} = \emptyset$. Par hypothèse, on a

$$\lambda(\mathcal{P} \cap Q_{S_n}) > 2^{-c-e_n}.$$

Aussi, si jamais un entier $a$ est dans $W_n$, cela signifie que pour tout élément $Z$ de $\mathcal{P} \cap Q_{S_n}$ on a $Z(a) = 0$. Pour une suite d'entiers $a_1, a_2, \dots, a_m$ fixée, l'ensemble des $Z$ tels que $\forall i < m \ Z(a_i) = 0$ est un ensemble de mesure $2^{-m}$ puisque la moitié des éléments $Z$ sont tels que $Z(a_1) = 0$, puis la moitié de cette moitié sont tels que $Z(a_2) = 0$, etc.

Comme $\lambda(\mathcal{P} \cap Q_{S_n}) > 2^{-c-e_n}$, on a donc forcément au plus $c+e_n$ éléments dans $W_n$. On peut donc appliquer le théorème 7-2.6 pour calculer uniformément à partir de $X$ un entier $a \notin W_n$, et donc tel que $\mathcal{P} \cap Q_{S_n \cup \{a\}} \neq \emptyset$. On définit $S_{n+1} = S_n \cup \{a\}$, et l'on calcule un code $e_{n+1}$ pour $Q_{S_{n+1}}$. On calcule de cette manière à l'aide de $X$ l'ensemble infini $S = \bigcup_n S_n$ pour lequel $\mathcal{P} \cap Q_S = \bigcap_n \mathcal{P} \cap Q_{S_n}$. Comme $\lambda(\mathcal{P} \cap Q_{S_n}) > 0$ pour tout $n$, alors $\mathcal{P} \cap Q_{S_n}$ est non vide pour tout $n$. En tant qu'intersection décroissante de fermés non vides, la classe $\mathcal{P} \cap Q_S$ est non vide. En particulier, il existe un élément $Z \in \mathcal{P}$ tel que $S \subseteq Z$.

Montrons à présent (3) → (1). Soit $X \subseteq Z$ un sous-ensemble infini d'un MLR. Pour tout $n$, soit $f(n)$ le $n$-ième élément de $X$. Nous allons établir que

$$K(X \upharpoonright_{f(n)}) >^+ n.$$

Supposons le contraire, c'est-à-dire $\forall c \exists n K(X \upharpoonright_{f(n)} < n - c$. Alors, on peut aussi compressor $Z \upharpoonright_{f(n)}$ de $c$ bits, en utilisant machine $M$ qui sur $\tau\sigma$ tel que $U(\tau) \downarrow = \rho$ renvoie la chaîne $\sigma$ dans laquelle on intercale les 1 de $\rho$ aux positions auxquels ils se trouvent dans $\rho$ (si jamais $\sigma$ est suffisamment grande). La chaîne $\sigma$ représente ici le préfixe de $Z \upharpoonright_{f(n)}$ auquel on a ≪ enlevé ≫ les $n$ bits à 1 de $X \upharpoonright_{f(n)}$. Elle est donc de taille $f(n) - n$. La chaîne $\tau$ est quant à elle une compression de $X \upharpoonright_{f(n)}$ de taille inférieure à $n - c$. La chaîne $\tau\sigma$ est donc une compression de taille inférieure à $f(n) - c$ d'un préfixe de $Z$ de taille $f(n)$, ce qui aboutit à une contradiction pour $c$ suffisamment grand. On a donc $K(X \upharpoonright_{f(n)}) >^+ n$ et, d'après (2) → (1), on a bien (3) → (1). ■
**Corollaire 4.3**

*La classe des ensembles de degré DNC est de mesure 1.*

PREUVE. On déduit aisément du précédent théorème que tous les ensembles MLR sont de degré DNC. ■

Nous avons vu avec l'exercice 8-7.6 que pour tout ensemble $X$, toute fonction $f: \mathbb{N} \to \{0,1\}$ DNC relativement à $X$ calculait $X$, autrement dit tout degré PA relativement à $X$ calcule $X$. La situation est différente lorsque l'on considère des fonctions DNC à valeurs arbitraires.

**Corollaire 4.4**

*Pour tout ensemble $X$, il existe une fonction $f: \mathbb{N} \to \mathbb{N}$ DNC relativement à $X$ qui ne calcule pas $X$.*

PREUVE. Par le corollaire 4.3 relativisé, la mesure de la classe des ensembles calculant une fonction DNC relativement à $X$ est 1, tandis que par le théorème 3.2, la mesure de la classe des ensembles calculant $X$ est 0. Il s'ensuit qu'il existe un ensemble calculant une fonction DNC relativement à $X$, mais ne calculant pas $X$.
Chapitre 19

Autres notions d'aléatoire

La définition d'aléatoire de Martin-Löf est-elle la bonne définition ? La concordance entre le point de vue « incompressibilité » et le point de vue « typicité » va dans ce sens. Il y a toutefois peu d'espoir d'obtenir de certitudes sur le fait que cette définition mathématique —ou une autre— vienne à épouser un jour avec perfection les contours des aspects épistémologiques dont elle relève.

Nous rejoignons ici le point de vue de Christopher Porter, qui dans une thèse pluridisciplinaire mathématiques/philosophie [179] défend la « no thesis thesis », selon laquelle il n'y a pas de définition absolue de ce qu'est un nombre aléatoire. À titre d'exemple, on peut légitimement considérer que la capacité à calculer $\emptyset'$ est une propriété atypique. C'est pourtant le cas du nombre aléatoire $\Omega$, qui ne l'est donc pas tant que cela.

Nous voyons donc ici d'autres notions d'aléatoires, plus ou moins fortes et dignes d'intérêt, notamment à travers les liens que l'on peut tisser entre elles et la calculabilité. Notons qu'un très grand nombre de classes de nombres aléatoires ont été étudiées, certaines plus faibles et d'autres plus fortes ou même incomparables à l'aléatoire au sens de Martin-Löf. Notre objectif n'est pas ici d'en présenter une liste exhaustive, mais plutôt de donner une photographie de quelques-unes des plus emblématiques d'entre elles.

# 1. Les fortement MLR

Commençons d'abord par examiner ce qu'il se passe si l'on enlève la condition d'être effectivement de mesure 0 pour un test.
**Définition 1.1.** Un ensemble $Z$ est fortement MLR $^a$ s'il n'appartient à aucun ensemble $\Pi_2^0$ de mesure 0. ◇

La notion d'ensemble fortement MLR est naturelle. Après tout, pourquoi s'embêter avec la condition de convergence rapide de la mesure des $\Pi_2^0$ vers 0 ? On obtient une notion plus forte, mais peut-être moins élégante, comme en témoigne la proposition et les corollaires suivants.

**Proposition 1.2.** Aucun ensemble $\Delta_2^0$ n'est fortement MLR. ★

PREUVE. Soit $A$ un ensemble $\Delta_2^0$, et soit $(A_s)_{s \in \mathbb{N}}$ une suite d'ensembles calculables telle que $\lim_s A_s = A$. On définit $U_{\langle n,t \rangle} = \bigcup_{s>t} [A_s \upharpoonright_n]$. Il est clair que $\cap_{\langle n,t \rangle \in \mathbb{N}} U_{\langle n,t \rangle} = \{A\}$. En particulier, $\cap_{\langle n,t \rangle \in \mathbb{N}} U_{\langle n,t \rangle}$ est un $\Pi_2^0$ de mesure 0 qui contient $A$. ■

**Corollaire 1.3**

L'ensemble des fortement MLR est strictement inclus dans celui des MLR.

PREUVE. En tant qu'ensemble approchable par la gauche, $\Omega$ est $\Delta_2^0$, et donc non fortement MLR. ■

**Corollaire 1.4**

Il n'existe aucun test universel pour la classe des fortement MLR.

PREUVE. Soit $\cap_n U_n$ un $\Pi_2^0$ de mesure 0. Pour un certain $n$, l'ensemble $2^\mathbb{N} \setminus U_n$ est donc un $\Pi_1^0$ de mesure positive. Soit $T$ l'arbre calculable qui représente $2^\mathbb{N} \setminus U_n$. Le chemin le plus à gauche de $T$ est un ensemble approchable par la gauche, et donc $\Delta_2^0$, et donc aussi non fortement MLR. On en conclut qu'il n'existe aucune classe $\Pi_2^0$ de mesure 0 qui contienne tous les ensembles non fortement MLR. ■

Il est possible d'améliorer considérablement le corollaire 1.4. Yu Liang a en effet montré [236] que la classe des éléments qui ne sont pas fortement MLR n'est pas $\Pi_2^0$ (même relativement à un oracle quelconque, il n'existe pas de test capturant exactement les non fortement MLR) et même n'est pas $\Pi_3^0$. La complexite borélienne de la classe des non fortement MLR est donc strictement $\Sigma_3^0$.

<footnote>a. Pour des raisons historiques dans l'avancée de la compréhension des différentes notions d'aléatoire, le concept est connu en anglais sous le nom de « weak-2-random ». Nous l'avons ici rebaptisé d'une manière que nous jugeons plus conforme à la réalité.</footnote>
On constate donc qu’en enlevant la condition de convergence rapide vers 0 dans la mesure des $\Pi_2^0$, on enlève certains ensembles MLR — au moins ceux qui sont $\Delta_2^0$. Il paraît probable que ces derniers ne soient pas les seuls à se faire exclure. On peut en fait en donner une caractérisation élégante découverte par Downey, Nies, Weber et Yu.

**Théorème 1.5 (Downey, Nies, Weber et Yu [48])**

Soit $Z$ un ensemble MLR. Les énoncés suivants sont équivalents :

(1) $Z$ n’est pas fortement Martin-Löf aléatoire ;

(2) $Z$ calcule un ensemble $\Delta_2^0$ non calculable ;

(3) $Z$ calcule un ensemble c. e. non calculable.

**PREUVE.** Montrons d’abord (2) $\to (1)$. Soit $A$ un ensemble $\Delta_2^0$ non calculable avec $A = \lim_s A_s$. Soit $\Phi$ telle que $\Phi(Z) = A$. On définit $\mathcal{U}_{\langle n,t \rangle}$ la classe $\Sigma_1^0$ égale à $\bigcup_{s>t}\{X \ : \ \Phi(X) \succeq A_s \upharpoonright_n\}$. Il est clair que $\bigcap_{\langle n,t \rangle} \mathcal{U}_{\langle n,t \rangle}$ contient exactement l’ensemble des $X$ tels que $\Phi(X) = A$. Par le théorème 18-3.2 de Sacks, cet ensemble est de mesure nulle. Donc, $Z$ n’est pas fortement Martin-Löf aléatoire.

Comme (3) $\to (2)$ est trivial, il nous reste à montrer (1) $\to (3)$. Supposons $Z$ MLR tel que $Z \in \bigcap_n \mathcal{U}_n$, où $\bigcap_n \mathcal{U}_n$ est une classe $\Pi_2^0$ de mesure nulle. On peut supposer $\mathcal{U}_{n+1} \subseteq \mathcal{U}_n$. Nous allons construire un ensemble c. e. simple $A$ (voir la définition 16-4.2) tel que le $\ll$ temps d’entrée $\gg$ de $Z$ dans $\mathcal{U}_n$ borne le temps nécessaire à l’énumération de $n$ dans $A$. En même temps que l’on construit $A$, on construit pour tout $e$ des classes $\mathcal{V}_e$ qui sont $\Sigma_1^0$ et telles que $\lambda(\mathcal{V}_e) < 2^{-e}$. Les classes $\mathcal{V}_e$ seront utilisées pour créer un test de Solovay qui nous aidera à conclure. On fixe une énumération $(W_e)_{e \in \mathbb{N}}$ des ensembles c. e. Au départ, chaque $\mathcal{V}_e$ est l’ensemble vide. À l’étape de calcul $t$, pour tout $e \le t$, si jamais $W_e$ n’intersecte pas encore $A$, alors on cherche $n \in W_e[t]$, avec $n > 2e$ tel que $\lambda(\mathcal{U}_n[t]) < 2^{-e}$. Si l’on trouve un tel $n$, on l’énumère dans $A$ à l’étape $t$, et l’on fixe $\mathcal{V}_e = \mathcal{U}_n[t]$. Cela conclut la construction.

Notons que si $W_e$ est infini, on finira forcément par trouver $n \in W_e[t]$ avec $n > 2e$ tel que $\lambda(\mathcal{U}_n[t]) < 2^{-e}$, car à partir d’un certain $n$ on a de toute façon $\lambda(\mathcal{U}_n) < 2^{-e}$. Donc, par l’argument usuel (voir la proposition 16-4.4), $A$ est bien un ensemble simple, et donc non calculable. Il reste à montrer que $Z$ permet de calculer $A$. On utilise pour cela nos ensembles $\mathcal{V}_e$ qui forment un test de Solovay, car $\lambda(\mathcal{V}_e) \le 2^{-e}$, et donc $\sum_e \lambda(\mathcal{V}_e)$ est fini. En particulier, si $Z$ est MLR, il ne peut appartenir qu’à un nombre fini de $\mathcal{V}_e$. Il existe donc $m$ tel que, pour tout $n \ge m$, si l’entier $n$ est énuméré dans $A$ à l’étape $t$, alors $Z \notin \mathcal{U}_n[t]$. Il suffit donc pour savoir si $n \ge m$ appartient à $A$ de chercher le plus petit temps $t$ tel que $Z \in \mathcal{U}_n[t]$, et d’énumérer $A$ jusqu’à l’étape $t$. On a alors $n \in A$ ssi $n \in A[t]$. $\blacksquare$
Parmi les ensembles MLR qui sont capturés par des $Π_2^0$ de mesure nulle, il y a donc bien sûr tous les MLR qui calculent $\emptyset'$, mais ce ne sont pas les seuls (c'est en particulier une conséquence du corollaire 20-3.10 à venir). Nous verrons en revanche avec le corollaire 20-3.2 que si un MLR est incomplet — ne calcule pas $\emptyset'$ — et calcule un ensemble c. e. non calculable, alors cet ensemble est nécessairement K-trivial. Il s'agit en fait d'une caractérisation des ensembles c. e. et K-triviaux, comme nous le verrons avec le corollaire 20-3.10.

Voyons à présent un corollaire intéressant du théorème 1.5. Nous avons vu avec le corollaire 18-2.3 qu'il existait des ensembles MLR et calculatoirement dominés. Nous verrons avec le théorème 3.4 qu'être calculatoirement dominé est toutefois une propriété atypique : la classe des ensembles calculatoirement dominés est de mesure nulle. Le corollaire suivant indique que la notion d'être fortement Martin-Löf aléatoire n'est pas suffisante pour en rendre compte.

**Corollaire 1.6**

Soit Z un ensemble MLR, mais non fortement Martin-Löf aléatoire. Alors, Z n'est pas calculatoirement dominé.

**PREUVE.** Si Z est un ensemble MLR, mais non fortement Martin-Löf aléatoire, alors il calcule un ensemble c. e. non calculable, qui est donc par la proposition 7-4.7 non calculatoirement dominé. ■

On déduit du corollaire précédent que tous les MLR qui sont calculatoirement dominés sont aussi fortement MLR. Il nous faudra donc une notion plus forte pour capturer ces éléments. La notion d'être fortement Martin-Löf aléatoire est en revanche suffisante pour montrer qu'il est atypique d'être de degré PA, via une preuve due à Frank Stephan, et dont nous espérons que le lecteur appréciera la finesse. Stephan lui-même résume son résultat d'une manière très eastwoodienne : « Il y a deux types d'ensembles Martin-Löf aléatoires dans ce monde : ceux qui sont calculatoirement suffisamment puissants pour résoudre le problème de l'arrêt, et ceux qui sont calculatoirement trop faibles pour être PA. »

**Théorème 1.7 (Stephan [218])**

Soit Z Martin-Löf aléatoire. Alors, Z est de degré PA si, et seulement si, $Z \ge_T \emptyset'$.

**PREUVE.** Supposons que $\Phi(Z)$ soit un ensemble $DNC_2$, dans le but de montrer $Z \ge_T \emptyset'$. Durant la construction, nous allons définir de manière effective une suite de codes de fonctions partielles calculables

$$a_0 < a_1 < a_2 < \dots$$
Aussi, d'après le théorème du point fixe, on peut supposer que chacun des $a_k$ code pour une fonction qui a accès à cette suite, y compris au code $a_k$ lui-même. Nous partitionnons la suite $(a_k)_{k \in \mathbb{N}}$ en une série d'intervalle consécutifs $I_n$ de telle manière à ce que $I_n$ contiennent $2^n$ éléments de la suite. Nous nommerons dorénavant $a_n^k$ le k-ième élément de $I_n$. Au départ, chaque $a_n^k$ est le code d'une fonction définie nulle part, qui attend certains évènements avant de peut-être s'arrêter sur certaines entrées.

Pour tout $n \in \mathbb{N}$, on définit $\mathcal{U}_{n,i}^0$ la classe $\Sigma_1^0$ des $\{X : \Phi(X, a_n^0) \downarrow= i\}$. On cherche ensuite $i \in \{0,1\}$ et un temps de calcul $t$ tels que $\lambda(\mathcal{U}_{n,i}^0[t]) > 2^{-n}$. Si l'on trouve pour $n$ un tel élément $i \in \{0,1\}$ et un tel temps de calcul $t$, alors on définit $\mathcal{U}_n^0 = \mathcal{U}_{n,i}^0[t]$, on décide que $a_n^0$ est le code de la fonction qui sur $a_n^0$ renvoie $i$, et l'on définit $\mathcal{U}_{n,i}^1 = \{X \notin \mathcal{U}_n^0 : \Phi(X, a_n^1) \downarrow= i\}$. On continue ensuite inductivement : si $\mathcal{U}_n^{k-1}$ est défini ainsi que $\mathcal{U}_{n,i}^k$ pour $i \in \{0,1\}$, alors on cherche $i \in \{0,1\}$ et un temps de calcul $t$ tels que $\lambda(\mathcal{U}_{n,i}^k[t]) > 2^{-n}$. Si l'on trouve un tel élément $i \in \{0,1\}$ et un tel temps de calcul $t$, on définit $\mathcal{U}_n^k = \mathcal{U}_{n,i}^{k-1} \cup \mathcal{U}_{n,i}^k[t]$, on décide que $a_n^k$ est le code de la fonction qui sur $a_n^k$ renvoie $i$, et l'on définit $\mathcal{U}_{n,i}^{k+1} = \{X \notin \mathcal{U}_n^k : \Phi(X, a_n^{k+1}) \downarrow= i\}$.

Dans la suite, nous appellerons les différents $\mathcal{U}_{n,i}^0, \mathcal{U}_{n,i}^1, \mathcal{U}_{n,i}^2, \dots$ des versions de $\mathcal{U}_{n,i}$. Les classes $\mathcal{U}_n^0, \mathcal{U}_n^1, \mathcal{U}_n^2, \dots$ seront quant à elles des versions tronquées. Lors de ce procédé, remarquons deux choses : d'abord, pour tout $n$, on arrivera à des versions finales et non tronquées $\mathcal{U}_{n,0}^k$ et $\mathcal{U}_{n,1}^k$ de $\mathcal{U}_{n,0}$ et $\mathcal{U}_{n,1}$, telles que $\lambda(\mathcal{U}_{n,0}^k \cup \mathcal{U}_{n,1}^k) < 2^{-n+1}$. En effet, par construction, chaque nouvelle version est disjointe de sa version tronquée précédente, qui a une mesure strictement plus grande que $2^{-n}$. Comme il y a $2^n$ versions possibles, chacune des deux dernières doit forcément avoir une mesure inférieure à $2^{-n}$.

Ensuite, aucun ensemble appartenant à une version tronquée $\mathcal{U}_n^k$ ne peut calculer un ensemble DNC$_2$ via $\Phi$ : on s'assure de cela en définissant le code $a_n^k$ comme étant tel que $\Phi_{a_n^k}(a_n^k) \downarrow= i$, pour $i$ tel que tout élément de $\mathcal{U}_n^k$ renvoie aussi $i$ sur $a_n^k$. Comme $\Phi(Z)$ est un ensemble DNC$_2$, alors $Z$ est forcément dans chaque dernière version non tronquée. En revanche, si pour les dernières versions $\mathcal{U}_{n,0}^k$ et $\mathcal{U}_{n,1}^k$, on a bien que $\mathcal{U}_{n,0}^k \cup \mathcal{U}_{n,1}^k$ est une classe $\Sigma_1^0$ de mesure inférieure à $2^{-n+1}$, ces classes ne sont pas obtenues uniformément en $n$, car on ne sait potentiellement jamais si l'on est arrivé ou non à la dernière version. C'est là que $\emptyset'$ entre en jeu.

On va à présent définir un test de Solovay via les ensembles $\mathcal{V}_n$ suivants : au départ, chaque $\mathcal{V}_n$ est l'ensemble vide. Puis, si $n$ est énuméré dans $\emptyset'$ au temps $t$, on déclare alors que $\mathcal{V}_n$ est la réunion $\mathcal{U}_{n,0}^k \cup \mathcal{U}_{n,1}^k$ des versions disponibles au temps $t$, éventuellement tronquées afin que la mesure ne dépasse pas $2^{-n+1}$. Il est alors clair que $(\mathcal{V}_n)_{n \in \mathbb{N}}$ forment un test de Solovay.
Supposons à présent que le temps d'entrée de Z dans

$$
\mathcal{U}_n = \{ X : \bigwedge_{a \in I_n} \Phi(X, a) \downarrow \}
$$

(il s'agit du plus petit $t$ tel que $Z \in \mathcal{U}_n[t]$) soit infiniment souvent inférieur
au temps d'énumération de $n$ dans $\emptyset'$. Souvenons-nous que $Z$ est forcément
dans chaque dernière version, et que ces dernières sont non tronquées. On
en déduit que, pour chacun de ces entiers $n$, l'ensemble $Z$ appartient à $\mathcal{V}_n$,
ce qui implique que $Z$ est capturé par le test de Solovay, contredisant le
fait que $Z$ est aléatoire au sens de Martin-Löf. On en déduit que le temps
d'entrée de $Z$ dans $\mathcal{U}_n$ est pour presque tout entier $n$ supérieur au temps
d'énumération de $n$ dans $\emptyset'$. Donc, $Z$ peut savoir si un entier $n$ suffisamment
grand appartient à $\emptyset'$ en regardant simplement si $n \in \emptyset'[t]$, où $t$ est le plus
petit tel que $Z \in \mathcal{U}_n[t]$. ■

Corollaire 1.8

Si Z est fortement Martin-Löf aléatoire, alors Z n'est pas de degré PA.
En particulier, la classe des ensembles de degré PA est de mesure nulle.

Notons qu’un simple argument de « vote à la majorité », à la manière du théorème 18-3.2, permet de prouver que la classe des ensembles de degré PA est de mesure nulle.

2. Relativisation de l’aléatoire

Comme pour la plupart des notions en calculabilité, il est possible de rela-
tiviser l’aléatoire de Martin-Löf à un oracle.

Définition 2.1

Soit $X \in 2^N$. Un $X$-test de Martin-Löf est donné par $\bigcap_n \mathcal{U}_n$, un ensemble $\Pi_2^0(X)$, tel que $\lambda(\mathcal{U}_n) \le 2^{-n}$. Un ensemble $Z$ est $X$-aléatoire au sens de Martin-Löf ou MLR$(X)$ s'il passe tous les $X$-tests de Martin-Löf.

◊

D'après la définition 17-3.3 et ce qui précède l'exemple 17-3.8, le code
d'une classe Π₀²(X) est un entier ⟨2, 1, e⟩ pour lequel W<sub>e</sub>⁽ᵏ⁾ énumère des en-
tiers ⟨1, 0, aₙ⟩ tels que [W<sub>aₙ</sub>⁽ᵏ⁾] est la n-ième composante de notre Π₀²(X).
Notre code e peut toutefois être utilisé avec n'importe quel autre oracle Y :
l'ensemble W<sub>e</sub>⁽ᵏ⁾ énumère lui aussi des entiers. On voit sans peine comment
uniformément transformer un code e de manière à ne conserver dans les
énumérations $W_e^Y$ (pour tout oracle $Y$) que les entiers de la forme $\langle 1, 0, a \rangle$. L'objectif est que, pour tout oracle $Y$, le même $e$ code pour une classe $\Pi_2^0(Y)$.

## Classe et machine à oracle

On parlera de *classe à oracle* pour insister sur le fait que le même code $e$ définisse uniformément une classe $\Sigma_n^0(X)$ pour tout oracle $X \in 2^N$. On parlera de la même manière de *machine à oracle* pour illustrer le fait qu'une machine $M : 2^N \to 2^N$ utilisant un oracle $X$ est aussi une machine — c'est-à-dire une fonction partielle de $2^N$ dans $2^N$ — avec n'importe quel oracle $Y$.

Les différents théorèmes que nous avons vus jusqu'ici se relativisent sans problème, en particulier le théorème 18-2.1 de Levin/Schnorr, pour lequel nous relativisons aussi la notion de complexité sans préfixe.

**Définition 2.2.** Étant donné une machine à oracle $M$ telle que $M$ est sans préfixe sur son oracle $X$, on note $K_M^X(\sigma)$ la taille de la plus petite chaîne $\tau$ telle que $M(X, \tau) \downarrow= \sigma$. ◇

Notons qu'étant donné une machine à oracle $M$, il est possible que $M$ soit sans préfixe sur certains de ses oracles, mais pas sans préfixe sur d'autres. De la même manière, étant donné $\bigcap_n U_n$ une classe à oracle $\Pi_2^0$, il est possible que cette classe soit un test de Martin-Löf sur certains de ses oracles, mais pas sur tous. Pour étudier ce phénomène, nous introduisons la notation suivante.

## Notation

Pour une machine à oracle $M$, on écrira $M^X : 2^N \to 2^N$ pour la machine utilisée avec l'oracle $X$. Étant donné $\bigcap_n U_n$ une classe à oracle $\Pi_2^0$, on écrira $\bigcap_n U_n^X$ pour la classe $\Pi_2^0(X)$ correspondante.

Étant donné un oracle $X$, l'existence d'une machine à oracle sans préfixe et universelle sur l'oracle $X$ ne présente pas de difficulté. Il est toutefois possible d'aller plus loin, et de montrer l'existence d'une machine à oracle qui soit à la fois sans préfixe et universelle pour tous les oracles.

## Théorème 2.3

Il existe une machine à oracle $U$ telle que pour tout oracle $X \in 2^N$ :

(1) la machine $U^X$ est sans préfixe;

(2) pour toute machine à oracle $M$, telle que $M^X$ est sans préfixe, on a $K_U^X(\sigma) \leqslant^+ K_M^X(\sigma)$ pour toute chaîne $\sigma$.
PREUVE. Il suffit de noter qu'une relativisation de la preuve du théorème 16-2.2 donne une procédure uniforme, et définit donc une fonctionnelle Turing.

Le corollaire suivant découle de la relativisation du théorème 18-2.1 de Levin/Schnorr, qui stipule qu'une chaîne est MLR si, et seulement si, chacun de ses préfixes est incompressible.

### Corollaire 2.4

Il existe une classe $Π_2^0$ à oracle qui est un X-test de Martin-Löf universel uniformément en chaque oracle X.

PREUVE. Il suffit de considérer la classe $Π_2^0(X)$ suivante :

$$ \{Y : \forall c \exists n K^X(Y \upharpoonright_n) \le n - c\}. $$

D'après le théorème 18-2.1, cette classe est un X-test de Martin-Löf pour tout oracle X. D'après le théorème précédent, elle est uniformément $Π_2^0(X)$ pour tout oracle X.

Cette universalité uniforme en chaque oracle nous sera utile de temps à autre, nous en voyons une première utilisation avec l'élégant théorème de van Lambalgen.

### Théorème 2.5 (van Lambalgen [227])

Soit $X_0, X_1$ deux ensembles. Alors, $X_0 \oplus X_1$ est MLR si, et seulement si, $X_0$ est MLR et $X_1$ est MLR($X_0$).

PREUVE. Notons que $\lambda([\sigma_1 \oplus \sigma_2]) = \lambda([\sigma_1]) \times \lambda([\sigma_2])$, pour $\sigma_1, \sigma_2 \in 2^{<N}$ de même taille. Supposons X non MLR ou Y non MLR(X) afin de montrer $X \oplus Y$ non MLR. Par symétrie, on peut supposer Y non MLR(X). Vu le corollaire 2.4, soit $\bigcap_n U_n$ un test de Martin-Löf universel pour tous les oracles. Étant donné une chaîne $\sigma$, on notera $U_n^\sigma$ le morceau d'ouvert énuméré avec l'oracle $\sigma$.

Comme Y n'est pas MLR(X), alors $Y \in \bigcap_n U_n^X$. Pour tous n, m, on définit alors la classe $\Sigma_1^0$ suivante :

$$ U_{n,m} = \bigcup_{|\tau|=m} \{[\tau] \oplus [\sigma] : [\sigma] \subseteq U_n^\tau \text{ et } |\sigma| = |\tau|\}. $$

Pour tous entiers m, n on a

$$ \lambda(U_{n,m}) \le \sum_{|\tau|=m} \lambda([\tau]) \times \lambda(U_n^\tau) \le \lambda(U_n) \sum_{|\tau|=m} \lambda([\tau]) \le \lambda(U_n) \le 2^{-n}. $$

De plus, on a l'inclusion $U_{n,m} \subseteq U_{n,m+1}$ pour tous entiers m, n, ce qui implique $\lambda(\bigcup_m U_{n,m}) \le 2^{-n}$ pour tout n. Par ailleurs, $X \oplus Y \in \bigcup_m U_{n,m}$. Dès lors, $\bigcap_n \bigcup_m U_{n,m}$ est un test de Martin-Löf qui capture $X \oplus Y$.
Supposons à présent $X \oplus Y$ non MLR et capturé par un test de Martin-Löf $\cap_n U_n$. Soit $\mathcal{U}_n^\sigma$ la classe $\Sigma_1^0$ donnée par $\{Y : [\sigma \oplus Y |_{|\sigma|}] \subseteq U_n\}$. Soit $\mathcal{V}_n^X$ la classe $\Sigma_1^0(X)$ donnée par $\cup_{\sigma<X} \mathcal{U}_{2n}^\sigma$. Supposons d'abord $\lambda(\mathcal{V}_n^X) \le 2^{-n}$ pour tout $n$ suffisamment grand. Alors, $\cap_n \mathcal{V}_n^X$ est un X-test de Martin-Löf qui capture $Y$. Sinon, il y a une infinité de $n$ tels que $\lambda(\mathcal{V}_n^X) > 2^{-n}$. Pour tout $n$, on définit $S_n$ comme étant la classe $\Sigma_1^0$ égale à $\{Z : \lambda(\mathcal{V}_n^Z) > 2^{-n}\}$. Montrons alors que, pour tout $n$, on a $\lambda(S_n) \le 2^{-n}$. Soit $W_n$ un ensemble sans préfixe minimal qui décrit $S_n$. On a par définition :

$$ \sum_{\tau \in W_n} \lambda(\tau) \times \lambda(\mathcal{U}_{2n}^{\tau}) \le \lambda(\mathcal{U}_{2n}) \sum_{\tau \in W_n} \lambda(\tau) \le \lambda(\mathcal{U}_{2n}) \le 2^{-2n}; $$

or, pour tout $\tau \in W_n$, on a $\lambda(\mathcal{U}_{2n}^\tau) > 2^{-n}$, ce qui nous donne :

$$ \sum_{\tau \in W_n} \lambda(\tau) \times 2^{-n} \le \lambda(\mathcal{U}_{2n}) \le 2^{-2n}. $$

On en déduit $\sum_{\tau \in W_n} \lambda(\tau) \le 2^{-n}$, et donc $\lambda(S_n) \le 2^{-n}$ pour tout $n$. Il s'ensuit que $(S_n)_{n \in \mathbb{N}}$ est un test de Solovay, capturant tous les ensembles qui sont dans une infinité de $S_n$. Ainsi, $X$ n'est pas MLR. $\blacksquare$

**Corollaire 2.6**

Soient $X, Y$ deux ensembles MLR. Alors, $X$ est MLR($Y$) si, et seulement si, $Y$ est MLR($X$).

Le corollaire précédent implique en particulier que si $X$ est aléatoire, alors il est atypique de rendre $X$ non aléatoire.

**Corollaire 2.7**

Soit $X$ un ensemble MLR. Alors, $\{Y \in 2^\mathbb{N} : X \text{ est non MLR}(Y)\}$ est une classe de mesure 0.

PREUVE. Si l'ensemble $X$ est non MLR($Y$), alors soit $Y$ est non MLR, soit $Y$ est MLR, et dans tous les cas $Y$ est non MLR($X$). En particulier, la classe $\{Y \in 2^\mathbb{N} : X \text{ est non MLR}(Y)\}$ est incluse dans la réunion de deux classes de mesure 0. $\blacksquare$

La relativisation de l'aléatoire de Martin-Löf nous permet évidemment d'obtenir des notions plus fortes d'aléatoire. N'importe quel oracle $X$ avec suffisamment de puissance de calcul pourra « dé-aléatoiriser » quelque chose. Mais de quelle puissance a-t-on besoin exactement pour rendre non aléatoire quelque chose qui l'était ? Existe-t-il au fond un ensemble $X$ non calculable et malgré tout trop faible pour capturer des ensembles MLR dans un X-test ? Ces questions nous amènent à la notion suivante.
**Définition 2.8.** Un ensemble $X$ est low pour l'aléatoire de Martin-Löf si tout ensemble MLR est MLR($X$). ◇

Nous verrons que la classe des ensembles low pour l'aléatoire de Martin-Löf est un peu plus grande que celle des calculables. Il s'agit d'un des résultats les plus beaux et les plus difficiles de l'aléatoire algorithmique : cette classe coïncide avec celle des ensembles K-triviaux.

## 3. Les 2-aléatoires

Martin-Löf s'autorise des tests $\Pi_2^0$. Pourquoi au fond cette restriction ? On pourrait tout à fait considérer des classes de mesure 0 de complexité arbitraire afin de capturer plus d'ensembles. Nous voyons ici le premier niveau de cette hiérarchie.

**Définition 3.1.** Un ensemble $Z$ est 2-aléatoire s'il n'appartient à aucun ensemble $\Pi_3^0$ de la forme $\bigcap_n B_n$ tel que $\lambda(B_n) \le 2^{-n}$ pour tout $n$. ◇

Il existe une caractérisation équivalente, qui est souvent celle utilisée.

**Théorème 3.2**

Les ensembles 2-aléatoires sont exactement les ensembles MLR($\emptyset'$).

**PREUVE.** Considérons d'abord $\bigcap_n U_n$, une classe $\Pi_2^0(\emptyset')$. Chaque $U_n$ est donc une classe $\Sigma_1^0(\emptyset')$ décrite par un ensemble $\Sigma_1^0(\emptyset')$ $W_n \subseteq 2^{<N}$. D'après le corollaire 5-5.4 et la proposition 5-3.3, l'ensemble $W_n$ est $\Sigma_2^0$, c'est-à-dire $W_n = \{\sigma \in 2^{<N} : \exists x_1 \forall x_2 R(\sigma, x_1, x_2)\}$ pour un prédicat calculable $R$. On définit $F_{x_1,\sigma}$ comme étant la classe $\Pi_1^0$ égale à $[\sigma]$ si $\forall x_2 R(\sigma, x_1, x_2)$, et égale à l'ensemble vide sinon. On a $U_n = \bigcup_{x_1,\sigma} F_{x_1,\sigma}$, qui est donc un ensemble $\Sigma_2^0$. Donc, $\bigcap_n U_n$ est une classe $\Pi_3^0$.

Considérons à présent une classe $\Pi_3^0$ de la forme $\bigcap_n B_n$, où chaque $B_n$ est une classe $\Sigma_2^0$ pour laquelle $\lambda(B_n) < 2^{-n}$. D'après le théorème 17-4.4, pour chaque classe $B_n$, on peut trouver uniformément une classe $\Pi_2^0(\emptyset')$ de la forme $\bigcap_m U_m^n$ telle que $B_n \subseteq \bigcap_m U_m^n$ et pour laquelle $\lambda(U_m^{n} \setminus B_n) \le 2^{-m}$ pour tout $m$. On a donc $\lambda(U_{n+1}^{n+1}) \le 2^{-(n+1)} + 2^{-(n+1)} = 2^{-n}$. Il s'ensuit que $\bigcap_n U_{n+1}^{n+1}$ est un $\emptyset'$-test de Martin-Löf contenant $\bigcap_n B_n$. ■

**Exercice 3.3.** (⋆) Un ensemble est $n$-aléatoire s'il n'appartient à aucune classe $\Pi_{n+1}^0$ de la forme $\bigcap_n B_n$, avec $\lambda(B_n) \le 2^{-n}$.

Montrer que l'on peut itérer le théorème 3.2 : un ensemble est MLR($\emptyset^n$) si, et seulement si, il est $n$-aléatoire. ◇
Cette notion d'aléatoire plus forte nous permet de montrer que la classe des ensembles calculatoirement dominés est atypique.

**Théorème 3.4**

Aucun 2-aléatoire n'est calculatoirement dominé. En particulier les réels calculatoirement dominés forment une classe de mesure 0.

On utilisera pour montrer le théorème 3.4 le lemme suivant.

**Lemme 3.5 (Monin [158])**

Toute classe $\Sigma_2^0$ qui intersecte n'importe quelle classe $\Pi_1^0$ non vide contient tous les ensembles calculatoirement dominés. $\star$

PREUVE. Soit $\bigcup_n \mathcal{F}_n$ une classe $\Sigma_2^0$ qui intersecte toutes les classes $\Pi_1^0$ non vides. Supposons par l'absurde qu'il existe $X$ calculatoirement dominé avec $X \notin \bigcup_n \mathcal{F}_n$. Soit $\bigcap_n U_n$ le complémentaire de $\bigcup_n \mathcal{F}_n$. On définit la fonction $X$-calculable $f : \mathbb{N} \to \mathbb{N}$ qui sur $n$ renvoie le plus petit $t$ tel que $X \in U_n[t]$. Soit $g > f$ une fonction calculable. Alors, $X$ appartient à la classe $\Pi_1^0$ donnée par $\bigcap_n U_n[g(t)]$ et qui est disjointe de $\bigcup_n \mathcal{F}_n$, ce qui est une contradiction. $\blacksquare$

Passons à la preuve du théorème 3.4.

PREUVE DU THÉORÈME 3.4. Nous allons construire pour tout $n$ une classe $\Sigma_2^0$ qui intersecte n'importe quelle classe $\Pi_1^0$ non vide, et de mesure inférieure à $2^{-n}$. Nous allons décrire un ensemble calculatoirement énumérable $W$ de codes pour les classes $\Pi_1^0$ qui constituent notre $\Sigma_2^0$. Soit $\mathcal{F}_0, \mathcal{F}_1, \dots$ une énumération de toutes les classes $\Pi_1^0$.

Pour tout $e$, soit $\sigma_e$ la plus petite chaîne dans l'ordre lexicographique de taille $n + e + 1$. À l'étape $t$, pour tout $e \le t$, si $\mathcal{F}_e[t] \cap [\sigma_e] = \emptyset$, on change $\sigma_e$ qui devient la prochaine chaîne de taille $n + e + 1$ dans l'ordre lexicographique (sauf si c'est la dernière possible, auquel cas on ne fait rien). Puis, on énumère un code de $\mathcal{F}_e \cap [\sigma_e]$ dans $W$.

Il est clair que si $\mathcal{F}_e$ est non vide, alors on aura un code de $\mathcal{F}_e \cap [\sigma_e]$ énuméré dans $W$ pour la première chaîne $\sigma_e$ de taille $n + e + 1$ telle que $\mathcal{F}_e \cap [\sigma_e] \ne \emptyset$. Donc, $W$ intersecte toutes les classes $\Pi_1^0$ non vides. Par ailleurs, pour chaque $e$, on ajoute à la classe $\Sigma_2^0$ quelque chose de mesure bornée par $2^{-n-e-1}$. La mesure totale de la classe $\Sigma_2^0$ est dès lors bornée par $\sum_e 2^{-n-e-1} = 2^{-n}$.

On construit donc de la sorte un test $\Pi_3^0$ de la forme $\bigcap_n \bigcup_e \mathcal{F}_{e,n}$ tel que
$$ \lambda\left(\bigcup_e \mathcal{F}_{e,n}\right) < 2^{-n}. $$

Le test ne contient donc aucun 2-aléatoire. En revanche, il contient par le lemme 3.5 tous les ensembles calculatoirement dominés. $\blacksquare$
D'après une relativisation du théorème 18-4.1, tout ensemble 2-aléatoire calcule une fonction DNC(Ø'). Il est alors possible d'améliorer le théorème précédent.

**Exercice 3.6. (★★)** Montrer qu'aucun ensemble de degré DNC(Ø') n'est calculatoirement dominé (on pourra utiliser une technique similaire à celle présentée dans la preuve ci-dessus). ◇

Jockusch et Stephan [103] ont montré quelque chose de plus fort que dans l'exercice précédent : aucun ensemble X tel que X' est de degré DNC(Ø') n'est calculatoirement dominé. Voyons à présent une preuve alternative de l'existence d'un ensemble high ne calculant pas Ø'. Il suffit de considérer ΩØ', le nombre Ω de Chaitin relativisé à Ø'.

**Proposition 3.7.** L'ensemble ΩØ' est high, mais ne calcule pas Ø'. ★

**PREUVE.** En utilisant le même algorithme que celui de la preuve du théorème 16-2.13, avec les n premiers bits de ΩØ', et l'aide de Ø', on peut savoir quelles sont les chaînes σ de taille inférieure à n telles que U(Ø', σ) ↓. On a dès lors ΩØ' ⊕ Ø' ≥$_T$ Ø''. En revanche, d'après le théorème 1.5, le réel ΩØ' étant 2-aléatoire, il ne calcule pas Ø'.

La classe des 2-aléatoires permet également de mettre en évidence une propriété d'analyse bien connue : soit f une fonction limite de fonctions continues, alors il existe des fermés de mesure arbitrairement grande sur lesquels la restriction de f est continue. Il s'agit d'un résultat qui fait écho à son analogue catégorique : toute limite de fonctions continues est continue sur un ensemble co-maigre. Nous l'avons montré avec le théorème 10-3.20 qui dit que tout ensemble 1-générique est low généralisé. Nous montrons à présent un théorème équivalent, mais pour l'aléatoire.

**Théorème 3.8 (Kautz [108])**

Les ensembles 2-aléatoires sont low généralisés.

**PREUVE.** Étant donné un code e, on veut savoir si Z appartient à la classe

$$ \mathcal{U}_e = \{X : \Phi_e(X, e) \downarrow\}. $$

Notons que $\mathcal{U}_e$ est une classe $\Sigma_1^0$. En utilisant Ø', on calcule le Ø'-test de Martin-Löf suivant : pour tout e, on cherche le plus petit $t_e$ tel que

$$ \lambda(\mathcal{U}_e \setminus \mathcal{U}_e[t_e]) < 2^{-e}. $$

On pose ensuite $\mathcal{V}_e = \mathcal{U}_e \setminus \mathcal{U}_e[t_e]$. La classe $\bigcap_d \bigcup_{e>d} \mathcal{V}_e$ est un Ø'-test de Martin-Löf. Il existe donc d tel que, pour tout $e > d$, l'ensemble Z n'appartient pas à $\mathcal{V}_e$.
Pour tout entier $e > d$, pour savoir si $Z \in \mathcal{U}_e$, il suffit alors de regarder si $Z \in \mathcal{U}_e[t_e]$. Si c'est le cas, alors $\Phi_e(X, e) \downarrow$; et, si ce n'est pas le cas, alors comme également $Z \notin \mathcal{U}_e \setminus \mathcal{U}_e[t_e]$, on a $Z \notin \mathcal{U}_e$, et donc $\Phi_e(Z, e) \uparrow$. ■

Notons que dans le cas de la théorie des catégories, la même fonctionnelle est utilisée pour calculer $G'$ à partir de $\emptyset' \oplus G$ pour tout ensemble 1-générique $G$. Pour le théorème ci-dessus, il n'y a pas une unique fonctionnelle qui donne le bon résultat pour n'importe quel ensemble 2-aléatoire $Z$: cela dépend de la plus petite composante $\mathcal{W}_e$ d'un $\emptyset'$-test de Martin-Löf auquel $Z$ n'appartient pas. Il faut de plus écrire « en dur » les $e$ premiers bits de $Z'$. Cette étape peut toutefois être uniformisée grâce à la redondance d'information de l'arrêt : pour connaître $Z'(n)$ pour $n < e$, il suffit d'utiliser le lemme 3-5.1 de remplissage pour trouver un code $m > e$ équivalent à $n$. Reste que la procédure dépend toujours de $e$: plus celui-ci est grand, plus proche de 1 sera la classe des 2-aléatoires sur lesquels la fonctionnelle donnera le bon résultat. Ces idées ont été précisément formalisées par Hoyrup et Rojas [94] via les notions de déficit d'aléatoire et de fonctions calculables par couches.

**Corollaire 3.9**

La classe des ensembles high est de mesure 0.

PREUVE. D'après le théorème 3.8, si $Z$ est 2-aléatoire, alors $Z' \ge_T \emptyset''$ si, et seulement si, $Z \oplus \emptyset' \ge_T \emptyset''$. Aussi, par une relativisation de la preuve du théorème 18-3.2 de Sacks, on a $\lambda(\{X : X \oplus \emptyset' \ge_T \emptyset''\}) = 0$. La classe des ensembles high est donc de mesure 0. ■

# 4. Aléatoires incomplets

Les aléatoires incomplets — qui ne calculent pas $\emptyset'$ — forment une notion d'aléatoire intéressante, juste un peu plus forte que MLR et bien plus faible que fortement MLR. Leur étude a réellement été initiée par Franklin et Ng qui ont découvert la notion de test de différence, permettant de les capturer.

**Définition 4.1 (Franklin et Ng [61]).** Un test de différence est donné par $\bigcap_n \mathcal{U}_n$ une classe $\Pi_2^0$ et $\mathcal{F}$ une classe $\Pi_1^0$ telles que $\lambda(\mathcal{U}_n \cap \mathcal{F}) \le 2^{-n}$ pour tout $n$. Un ensemble $Z$ est capturé par le test si $Z \in \bigcap_n \mathcal{U}_n \cap \mathcal{F}$. Sinon, $Z$ passe le test. Un ensemble $Z$ est un aléatoire de différence si $Z$ passe tous les tests de différence. ◇

La notion de test différence correspond en quelque sorte après avoir énuméré une chaîne $\sigma$ dans un ouvert le composant, à se réserver le droit de changer d'avis, et finalement d'enlever cette chaîne de l'énumération. On ne peut en revanche pas changer d'avis une seconde fois et décider finalement de remettre la chaîne $\sigma$.
**Théorème 4.2 (Franklin et Ng [61])**

Soit Z un ensemble MLR. Les énoncés suivants sont équivalents.

(1) Z calcule $\emptyset'$.

(2) Z n'est pas un aléatoire de différence.

Afin de montrer le théorème 4.2 nous utiliserons un lemme qui a son intérêt propre : si $X$ est un ensemble MLR, alors « peu » d'ensembles permettent de calculer des préfixes de $X$.

**Lemme 4.3.** Soit $Z$ un ensemble MLR et soit $\Phi$ une fonctionnelle. Alors, il existe une constante $c \in \mathbb{N}$ telle que $\lambda(\{X : \Phi(X) \succeq Z \upharpoonright_n\}) \leq 2^{-n} \times 2^c$ pour tout $n \in \mathbb{N}$.

**PREUVE.** Supposons que, pour toute constante $c \in \mathbb{N}$, il existe $n \in \mathbb{N}$ tel que

$$ \lambda(\{X : \Phi(X) \succeq Z \upharpoonright_n\}) > 2^{-n} \times 2^c. $$

Montrons que $Z$ n'est pas aléatoire au sens de Martin-Löf. Soit $\mathcal{U}_c$ la classe $\Sigma_1^0$ générée par les chaînes $\sigma$ telles que $\lambda(\{X : \Phi(X) \succeq \sigma\}) > 2^{-|\sigma|} \times 2^c$. Soit $W$ un ensemble minimal de chaînes sans préfixe tel que $\mathcal{U}_c = [W]$. En particulier, tout $\sigma \in W$ satisfait l'inégalité ci-dessus. Alors,

$$ \lambda(\mathcal{U}_c) = \sum_{\sigma \in W} 2^{-|\sigma|} \leq 2^{-c} \sum_{\sigma \in W} \lambda(\{X : \Phi(X) \succeq \sigma\}). $$

Comme la classe $W$ est sans préfixe, alors pour deux chaînes distinctes $\sigma_1, \sigma_2$ de $W$ on a $\{X : \Phi(X) \succeq \sigma_1\} \cap \{X : \Phi(X) \succeq \sigma_2\} = \emptyset$. Par additivité de la mesure, on a donc $\sum_{\sigma \in W} \lambda(\{X : \Phi(X) \succeq \sigma\}) \leq 1$, et donc $\lambda(\mathcal{U}_c) \leq 2^{-c}$. On peut à présent capturer $Z$ par le test de Martin-Löf donné par $\bigcap_c \mathcal{U}_c$.■

On peut à présent montrer la caractérisation de Franklin et Ng.

**PREUVE DU THÉORÈME 4.2.** Supposons que $Z$ calcule $\emptyset'$. Alors, $Z$ calcule également l'ensemble $\Omega$ de Chaitin via une fonctionnelle $\Phi$. Soit $c$ la constante du lemme 4.3 telle que $\lambda(\{X : \Phi(X) \succeq \Omega \upharpoonright_n\}) < 2^{-n} \times 2^c$ pour tout $n$. Soit $\mathcal{C}_{n,s}$ la classe $\Sigma_1^0$ donnée par $\{X : \Phi(X) \succeq \Omega_s \upharpoonright_n\}$, où $\Omega_s$ est l'approximation de $\Omega$ à l'étape $s$. Soit à présent $\mathcal{C}'_{n,s}$ la classe $\mathcal{C}_{n,s}$ pour laquelle on bloque l'énumération si nécessaire afin que la mesure ne dépasse pas $2^{-n} \times 2^c$.

Soit $\mathcal{U}$ la réunion des classes $\mathcal{C}'_{n,s}$ pour tous $n$ et $s$ tels que $\Omega_s \upharpoonright_n \neq \Omega_{s+1} \upharpoonright_n$. Notons qu'aucun élément de $\mathcal{U}$ ne calcule $\Omega$ via $\Phi$, car si $\Omega_s \upharpoonright_n \neq \Omega_{s+1} \upharpoonright_n$, alors $\Omega_s \upharpoonright_n \neq \Omega \upharpoonright_n$. En particulier, $Z$ ne peut pas être dans $\mathcal{U}$. Enfin, pour tout $n$, soit $\mathcal{U}_n$ la réunion des classes $\mathcal{C}'_{n,s}$ pour tout $s$, et soit $\mathcal{F}$ le complémentaire de $\mathcal{U}$.
Soit $s_n$ tel que $\Omega_{s_n} \rfloor_n = \Omega \rfloor_n$. Alors, $Z \in C_{n,s_n}$, et d'après le choix de la constante $c$, l'ensemble $Z$ appartient aussi à $C'_{n,s_n}$. Il est donc clair que $Z$ est dans $\bigcap_n U_n$, et comme $Z$ n'est pas dans $U$, il est clair que $Z \in \mathcal{F} \cap \bigcap_n U_n$. Par ailleurs, les éléments de $\mathcal{F} \cap U_n$ sont uniquement ceux qui appartiennent à $C'_{n,s_n}$, et l'on a par définition $\lambda(C'_{n,s_n}) \le 2^{-n} \times 2^c$. Donc, $\mathcal{F} \cap \bigcap_n U_n$ est un test de différence qui contient $Z$.

Supposons à présent que $Z$ est capturé par un test de différence $\mathcal{F} \cap \bigcap_n U_n$. Pour tout $n$, soit $\mathcal{V}_n$ la classe $\Sigma_1^0$ suivante : si $n$ est énuméré dans $\emptyset'$ à l'étape $t$, alors $\mathcal{V}_n$ est défini comme étant $U_n[t] \cap \mathcal{F}[s_t]$ où $s_t$ est le plus petit entier tel que $\lambda(U_n[t] \cap \mathcal{F}[s_t]) \le 2^{-n}$. Si $n$ n'est jamais énuméré, alors $\mathcal{V}_n$ reste vide. La suite $(\mathcal{V}_n)_{n \in \mathbb{N}}$ forme un test de Solovay. En particulier, il existe $n$ tel que pour tout $m > n$, $Z \notin \mathcal{V}_m$. On peut alors calculer $\emptyset'$ à l'aide de $Z$ de la manière suivante : pour tout $m > n$, il suffit de chercher le plus petit $t$ tel que $Z \in U_m[t]$ et de voir si $m \in \emptyset'[t]$. Si ce n'est pas le cas, alors $m \notin \emptyset'$, car on aurait alors dans le cas inverse $Z \in \mathcal{V}_m$. $\blacksquare$

MLR approchable par la gauche

La preuve du théorème 4.2 fonctionne en remplaçant $\Omega$ par n'importe quel MRL approchable par la gauche. En particulier, tout MLR approchable par la gauche est capturé par un test de différence, donc est complet, comme nous en avions discuté dans la section 16-2.4.

Nous voyons à présent une application de la notion de test de différence et d'aléatoire incomplet. Avec l'apparition de la notion de mesure, est apparue en analyse la notion de propriété satisfaite « presque partout ». Ainsi, une propriété sur les réels est vraie presque partout si l'ensemble des réels pour laquelle elle est fausse a pour mesure 0. Un théorème classique nous dit par exemple qu'une fonction $f: \mathbb{R} \to \mathbb{R}$ de graphe borélien est continue presque partout.

Un des champs d'études de l'aléatoire algorithmique consiste à déterminer, pour les théorèmes qui sont vrais presque partout, le niveau exact d'aléatoire pour lequel un tel théorème est vrai. Nous en voyons ici un exemple, avec le théorème de densité de Lebesgue et les aléatoires de différence. Cette étude nous sera par ailleurs utile dans le chapitre à venir sur les ensembles K-triviaux.

Voyons pour commencer le théorème de densité de Lebesgue. Nous n'avons pour le moment exposé que le lemme de densité de Lebesgue, que nous rappelons ci-après.

**Lemme (18-3.1 de densité de Lebesgue).** Soit $\mathcal{B}$ un ensemble Borélien de mesure positive. Alors, pour tout $\varepsilon > 0$, il existe un cylindre $[\sigma]$ tel
que $\lambda(\mathcal{B} | [\sigma]) > 1 - \varepsilon$.

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

Le théorème de densité de Lebesgue est un renforcement de ce lemme-là. Nous introduisons pour cela le concept de valeur asymptotique de la densité d'un borélien le long des préfixes d'un ensemble.

**Définition 4.5.** Soit $\mathcal{B} \subseteq 2^\mathbb{N}$ un borélien et soit $Z \in 2^\mathbb{N}$.

(1) On note $\rho(\mathcal{B} | Z)$ la limite inférieure de la densité qu'occupe $\mathcal{B}$ à l'intérieur des préfixes de $Z$, c'est-à-dire

$$ \underline{\rho}(\mathcal{B} | Z) = \liminf_{\sigma \prec Z} \lambda(\mathcal{B} | [\sigma]). $$

(2) On note de manière similaire $\bar{\rho}(\mathcal{B} | Z)$ la limite supérieure de la densité qu'occupe $\mathcal{B}$ à l'intérieur des préfixes de $Z$, c'est-à-dire

$$ \bar{\rho}(\mathcal{B} | Z) = \limsup_{\sigma \prec Z} \lambda(\mathcal{B} | [\sigma]). $$

On dira que $\underline{\rho}(\mathcal{B} | Z)$ est la densité inférieure de $Z$ dans $\mathcal{B}$, et $\bar{\rho}(\mathcal{B} | Z)$ sa densité supérieure. ◇

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

On peut à présent énoncer le théorème annoncé de densité de Lebesgue.

**Théorème 4.6 (Théorème de densité de Lebesgue)**

Soit $\mathcal{B} \subseteq 2^\mathbb{N}$ une classe borélienne de mesure positive.

Alors, la classe $\{Z \in \mathcal{B} : \underline{\rho}(\mathcal{B} | Z) = 1\}$ a la même mesure que $\mathcal{B}$.

Nous utiliserons pour le montrer le lemme suivant.

**Lemme 4.7.** Soit $\mathcal{F}$ une classe fermée, et soit $\sigma \in 2^{<\mathbb{N}}$ une chaîne telle que

$$ \lambda(\mathcal{F} | [\sigma]) \geq \varepsilon. $$

Alors, il existe $X \in \mathcal{F} \cap [\sigma]$ tel que $\lambda(\mathcal{F} | [X \upharpoonright_n]) \geq \varepsilon$ pour tout $n > |\sigma|$. ★

**PREUVE.** Il suffit de voir que pour toute chaîne $\tau$ et tout borélien $\mathcal{A}$, si $\lambda(\mathcal{A} | [\tau]) \geq \varepsilon$, alors pour $i = 0$ ou $i = 1$ on aura $\lambda(\mathcal{A} | [\tau i]) \geq \varepsilon$. En effet, si $\mathcal{A}$ occupe pour moins de $\varepsilon$ de mesure dans $[\tau 0]$ et dans $[\tau 1]$, il occupera aussi moins de $\varepsilon$ de mesure dans $[\tau]$. On construit alors de cette manière un ensemble $X \supset \sigma$ tel que $\lambda(\mathcal{F} | [X \upharpoonright_n]) \geq \varepsilon$ pour tout $n > |\sigma|$. Comme $\mathcal{F}$ est une classe fermée et que $\mathcal{F} \cap [X \upharpoonright_n]$ est non vide pour tout $n$, alors $X \in \mathcal{F}$. ■

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

**PREUVE DU THÉORÈME 4.6.** Supposons par l'absurde que la classe

$$ \mathcal{B}' = \{Z \in \mathcal{B} : \underline{\rho}(\mathcal{B} | Z) < 1\}. $$

est de mesure positive.
Soit $\mathcal{B}'_\varepsilon = \{Z \in \mathcal{B} : \underline{\rho}(\mathcal{B} | Z) < 1 - \varepsilon\}$. Comme $\mathcal{B}' = \bigcup_{\varepsilon \in \mathbb{Q} \cap [0,1]} \mathcal{B}'_\varepsilon$, il
doit exister par additivité dénombrable de la mesure $\varepsilon$ tel que la mesure
de $\mathcal{B}'_\varepsilon$ est positive. Soit enfin, en utilisant le théorème 17-4.4, une classe
fermée $\mathcal{F} \subseteq \mathcal{B}'_\varepsilon$ de mesure positive. Notons que, pour tout $Z \in \mathcal{F}$, on a
également $\underline{\rho}(\mathcal{F} | Z) < 1 - \varepsilon$, car $\underline{\rho}(\mathcal{F} | [\sigma]) \le \underline{\rho}(\mathcal{B} | [\sigma])$ pour toute chaîne $\sigma$.

À présent, d'après le lemme 18-3.1 de densité de Lebesgue, il doit exister
une chaîne $\sigma$ telle que $\lambda(\mathcal{F} | [\sigma]) > 1 - \varepsilon$. D'après le lemme 4.7, il existe
alors $Z \in \mathcal{F}$ tel que $\lambda(\mathcal{F} | [Z \upharpoonright_n]) \ge 1 - \varepsilon$ pour tout $n > |\sigma|$, et donc
tel que $\underline{\rho}(\mathcal{F} | Z) \ge 1 - \varepsilon$, ce qui contredit $\underline{\rho}(\mathcal{F} | Z) < 1 - \varepsilon$. Ainsi, la
classe $\mathcal{B}' = \{Z \in \mathcal{B} : \underline{\rho}(\mathcal{B} | Z) < 1\}$ est de mesure 0. $\blacksquare$

On ne peut bien sûr pas attendre d'une notion d'aléatoire fixe de satisfaire
le théorème de densité de Lebesgue pour n'importe quelle classe borélienne,
mais on peut le faire pour un certain niveau dans la hiérarchie borélienne
effective. Nous nous limiterons au cas le plus simple : les classes $\Pi_1^0$.

**Définition 4.8.** Un ensemble $Z \in 2^\mathbb{N}$ est dit de densité inférieure (resp. supérieure) positive si $\underline{\rho}(\mathcal{F} | Z) > 0$ (resp. $\bar{\rho}(\mathcal{F} | Z) > 0$), pour toute classe $\Pi_1^0$ $\mathcal{F}$ contenant $Z$. Un ensemble $Z$ est dit de densité inférieure (resp. supérieure) 1 si $\underline{\rho}(\mathcal{F} | Z) = 1$ (resp. $\bar{\rho}(\mathcal{F} | Z) = 1$), pour toute classe $\Pi_1^0$ $\mathcal{F}$ contenant $Z$. $\diamond$

**Exercice 4.9. (★★)** Montrer que les ensembles MLR sont de densité supé-rieure 1. $\diamond$

Nous donnons à présent une caractérisation des ensembles aléatoires in-complets, en rapport avec le théorème de densité de Lebesgue.

Théorème 4.10 (Bienvenu, Hölz, Miller, Nies [18])

Soit $Z$ un ensemble MLR. Alors, les énoncés suivants sont équivalents.

1. Z est un ensemble incomplet (c'est-à-dire avec $Z \nsubseteq_T \emptyset'$).

2. Z est un ensemble de densité inférieure positive.

PREUVE. Supposons $Z$ de densité inférieure nulle, et soit $\mathcal{F}$ une classe $\Pi_1^0$
telle que $\underline{\rho}(\mathcal{F} | Z) = 0$. Soit $U_n$ la classe $\Sigma_1^0$ générée par les chaînes $\sigma$
telles que $\lambda(\mathcal{F} | [\sigma]) < 2^{-n}$. Il est clair que $\lambda(U_n \cap \mathcal{F}) \le 2^{-n}\lambda(\mathcal{F}) \le 2^{-n}$.
Comme $\underline{\rho}(\mathcal{F} | Z) = 0$, alors $Z$ est capturé par le test $\mathcal{F} \cap \bigcap_n U_n$. Donc, $Z$
est capturé par un test de différence. D'après le théorème 4.2, $Z \ge_T \emptyset'$.

Supposons à présent que $Z \ge_T \emptyset'$. Alors, d'après le théorème 4.2, $Z$ est cap-
turé par un test de différence $\mathcal{F} \cap \bigcap_n U_n$. Montrons que l'on a $\underline{\rho}(\mathcal{F} | Z) = 0$.
Pour chaque $r \in \mathbb{N}$, nous allons construire un test de Martin-Löf $\bigcap_n V_n$ tel
que pour tout $X \in 2^N$, si $X \in \mathcal{F} \cap \bigcap_n U_n$ et $X \notin \bigcap_n V_n$, alors il existe un préfixe $\sigma \prec X$ tel que $\lambda(\mathcal{F} | [\sigma]) < 2^{-r}$. On définit $V_0 = U_0$, puis une fois $V_n$ défini, pour toute chaîne $\sigma$ énumérée dans $V_n$ on énumère dans $V_{n+1}$ les chaînes de $U_{|\sigma|+r+1} \cap [\sigma]$ en bloquant si besoin l'énumération pour ne pas dépasser une mesure de $2^{-|\sigma|}(1-2^{-r-1})$. On a $\lambda(V_{n+1}) \le (1-2^{-r-1})\lambda(V_n)$, et l'on peut donc borner la mesure de $V_n$ par une fonction calculable et décroissante qui tend vers 0. On peut alors aisément transformer $\bigcap_n V_n$ en un test de Martin-Löf. Comme $Z$ est MLR, alors $Z \notin \bigcap_n V_n$. Soit $n$ le plus petit entier tel que $Z \notin V_n$, et soit $\sigma \prec Z$ tel que $\sigma$ est énuméré dans $V_{n-1}$. Comme $Z \in \bigcap_n U_n$, cela signifie que l'énumération de $V_n$ a été bloquée et que l'on a $\lambda(U_{|\sigma|+r+1} | [\sigma]) > 1 - 2^{-r-1}$. Supposons à présent par l'absurde $\lambda(\mathcal{F} | [\sigma]) > 2^{-r}$. Alors, $\lambda(U_{|\sigma|+r+1} \cap \mathcal{F} | [\sigma]) > 2^{-r-1}$, et donc $\lambda(\mathcal{F} \cap U_{|\sigma|+r+1}) > 2^{-|\sigma|-r-1}$, ce qui contredit

$$ \lambda(\mathcal{F} \cap U_{|\sigma|+r+1}) < 2^{-|\sigma|-r-1}. $$

Donc, $\lambda(\mathcal{F} | [\sigma]) < 2^{-r}$.

Comme on peut faire la même chose pour tout $r$, il existe pour tout $r$ un préfixe $\sigma \prec Z$ tel que $\lambda(\mathcal{F} | [\sigma]) < 2^{-r}$, et $Z$ est donc de densité inférieure nulle dans $\mathcal{F}$. ■
Chapitre 20

# Les K-triviaux

Les K-triviaux constituent une des classes les plus fascinantes de l'aléatoire algorithmique, et qui n'a pas cessé de surprendre au fur et à mesure des découvertes la concernant. Le théorème central est sans aucun doute le suivant : un ensemble $A$ est K-trivial si, et seulement si, il est low pour l'aléatoire. Nous commençons notre aventure par une étude de la notion d'être low pour l'aléatoire, qui connaîtra son point culminant avec la re-marquable preuve dite « des ensembles affamés ».

## 1. Lowness et bases pour l'aléatoire

Nous avons vu avec la définition 19-2.8 le concept d'oracle ne modifiant pas la classe des aléatoires de Martin-Löf. Nous voyons ici un concept *a priori* plus fort encore : les oracles ne modifiant pas la complexité sans préfixe.

### 1.1. Lowness

De manière générale, toute propriété relativisable $P$ induit une notion de lowness, où $X$ est low pour $P$ ssi $P^X$ et $P^\emptyset$ coïncident. Par exemple, un ensemble $X$ est low (pour le saut Turing) si $X' = \emptyset'$. De même, un ensemble $X$ est low pour l'aléatoire de Martin-Löf si tout ensemble MLR est MLR($X$). Nous définissons la notion correspondante pour la complexité sans préfixe.

**Définition 1.1.** Un ensemble $A \in 2^\mathbb{N}$ est low-pour-K si $K^A(\sigma) \leq^+ K(\sigma)$ pour toute chaîne $\sigma$. ◇
Il est clair que tout ensemble calculable est low-pour-K, et il est possible
de montrer que ce ne sont pas les seuls.

**Exercice 1.2. (★★)** En utilisant la même technique que celle de la preuve du théorème 16-4.5, montrer qu'il existe des ensembles c. e. non calculables et low-pour-K.

◇

Voyons tout de suite deux implications faciles à montrer : si $A$ est low-pour-K, alors il est K-trivial, et aussi low pour l'aléatoire de Martin-Löf.

**Proposition 1.3.** Si $A$ est low-pour-K, alors $A$ est K-trivial.

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

PREUVE. Pour tout oracle $X$, on a $K^X(X \upharpoonright_n) \leq^+ K^X(n) \leq^+ K(n)$, pour tout $n$. Pour la première inégalité, étant donné $n$, il suffit d'utiliser l'oracle $X$ pour produire $X \upharpoonright_n$. Pour la deuxième inégalité, si une machine peut produire $n$ sans oracle, elle le peut aussi avec oracle. Si $A$ est un ensemble $A$ low-pour-K, on a de plus $K(A \upharpoonright_n) \leq^+ K^A(A \upharpoonright_n)$, donc $K(A \upharpoonright_n) \leq^+ K(n)$ pour tout $n$.

■

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

**Proposition 1.4.** Si $A$ est low-pour-K, alors $A$ est low-pour-MLR.

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

PREUVE. Supposons que $A$ soit low-pour-K, et considérons un $A$-test de Martin-Löf $\bigcap_n U_n$. D'après le théorème 18-2.1 relativisé, pour tout $X$ dans $\bigcap_n U_n$, pour tout $c$ il existe $m$ tel que $K^A(X \upharpoonright_m) \leq m-c$, et donc tel que $K(X \upharpoonright_m) \leq m-c+d$, pour une certaine constante $d$ indépendante de $m$. Donc, pour tout $X$ dans $\bigcap_n U_n$, pour tout $c$ il existe $m$ tel que $K(X \upharpoonright_m)$ est $\leq m-c$. D'après le corollaire 18-2.2, le $A$-test de Martin-Löf $\bigcap_n U_n$ est alors inclus dans le test de Martin-Löf universel (sans oracle).

■

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

**Exercice 1.5. (★)** Montrer que tout ensemble low-pour-K est de degré low.

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

**1.2. Base pour l'aléatoire et ensembles affamés**

Nous voyons à présent que la classe des low-pour-K coïncide avec celle des
low pour l'aléatoire de Martin-Löf. Nous utilisons pour cela une troisième
notion qui présente son intérêt propre.

**Définition 1.6.** Un ensemble $A \in 2^\mathbb{N}$ est une *base pour l'aléatoire de Martin-Löf* s'il existe un ensemble $Z \in \text{MLR}(A)$ qui calcule $A$. ◇

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

Nous avons vu avec le théorème 18-3.2 que pour $A$ non calculable, la classe des ensembles qui calculent $A$ est de mesure 0. De plus, pour une fonctionnelle $\Phi$ fixée, la classe $\{X \in 2^\mathbb{N} : \forall n \Phi(X, n) \downarrow= A(n)\}$ est une classe $\Pi_2^\Phi(A)$ de mesure 0.
On en déduit que pour tout $A$ non calculable aucun ensemble calculant $A$ n'est fortement MLR$(A)$. On ne peut pas en revanche toujours montrer qu'un tel ensemble n'est jamais MLR$(A)$. Il suffit en effet de considérer un ensemble $A$ non calculable et low pour l'aléatoire de Martin-Löf, et d'après le théorème 18-3.4, il existe un ensemble MLR, et donc MLR$(A)$ qui calcule $A$. En particulier, si $A$ est low-pour-K alors $A$ est une base pour l'aléatoire. Le théorème suivant montre que la réciproque est vraie, en utilisant une construction sophistiquée et astucieuse, baptisée « preuve des ensembles affamés ».

**Théorème 1.7 (Hirschfeldt, Nies et Stephan [90])**

Si $A$ est une base pour l'aléatoire, alors $A$ est low-pour-K.

**PREUVE.** Le lecteur pourra s'aider de la figure 1.8 pour suivre la preuve. Soit $Z$ un ensemble MLR$(A)$ tel que $\Phi(Z) = A$ pour une fonctionnelle $\Phi$. Soit $U$ la machine à oracle sans préfixe universelle du théorème 19-2.3. On peut voir $U$ comme une énumération de triplets $(\rho, \tau, x)$ signifiant alors $U^{\rho}(\tau) \downarrow = x$.

On peut considérer sans perte de généralité que si $U^X(\tau) \downarrow = x$ pour un ensemble $X$, alors il y a un unique préfixe $\rho < X$ tel que $U^\rho(\tau) \downarrow = x$.

Nous allons décrire un algorithme paramétré par un entier $d$. Aussi pour tout $d$ l'algorithme énumérera-t-il un ensemble borné de requêtes $L_d$, et nous montrerons que pour $d$ suffisamment grand, la machine sans préfixe $M_d$ issue de cet ensemble de requêtes sera telle que $K_{M_d}(\sigma) \le + K^A(\sigma)$, pour toute chaîne $\sigma$. Durant l'algorithme, pour chaque triplet $(\rho, \tau, x)$, nous allons énumérer des « ensembles affamés » $C_{\tau,x}^{\rho} \subseteq 2^{<N}$ qui demandent à être nourris par des chaînes finies jusqu'à être repus. Un ensemble affamé continuera à « manger » des chaînes finies tant qu'il n'est pas rassasié, mais il refusera en revanche de manger quoi que ce soit qui le nourrirait plus que de raison : chaque ensemble $C_{\tau,x}^{\rho}$ veut atteindre un poids de $2^{-d}2^{-|\tau|}$, mais refusera toujours de dépasser ce poids.

L'algorithme avec paramètre $d$ est le suivant : à une étape de calcul $t$, pour tout $(\rho, \tau, x) \le t$, si $U^\rho(\tau)[t] \downarrow = x$, on considère alors l'ensemble ouvert/fermé $U = \{X : \Phi(X)[t] \ge \rho\}$. Soit $W$ un ensemble de chaînes sans préfixe tel que $[W] = U$. L'objectif est de rajouter chaque chaîne $\sigma \in W$ dans $C_{\tau,x}^{\rho}$, mais tout en gardant les ensembles affamés — vus comme des ouverts — deux à deux disjoints. Donc, si un préfixe de $\sigma$ est dans un autre ensemble affamé, on n'énumérera rien du tout; et si une extension de $\sigma$ est dans un autre ensemble affamé, on énumérera seulement les extensions de $\sigma$ qui ne sont encore dans aucun d'entre eux. Formellement, pour chaque chaîne $\sigma \in W$, on cherche deux ensembles de chaînes finies $B_{0,\sigma}$ et $B_{1,\sigma}$ tels que $[B_{0,\sigma}] \cup [B_{1,\sigma}] = [\sigma]$, tels que $[B_{0,\sigma}] \cap [B_{1,\sigma}] = \emptyset$, et tels que $[t]$ est inclus
dans un ensemble affamé pour chaque $\iota \in B_{0,\sigma}$ et $[\iota]$ a une intersection vide avec tous les ensembles affamés pour chaque $\iota \in B_{1,\sigma}$. Finalement, pour tout $\sigma \in W$ et toute chaîne $\iota \in B_{1,\sigma}$, on énumère dans l'ordre $\iota$ dans $C_{\tau,x}^{\rho}$, à condition que l'on conserve toujours $\lambda([C_{\tau,x}^{\rho}]) \le 2^{-d} \times 2^{-|\tau|}$. Si l'énumération d'une chaîne fait passer la mesure de $[C_{\tau,x}^{\rho}]$ au-dessus de $2^{-d} \times 2^{-|\tau|}$, alors on ne l'énumère pas. Enfin, si après l'énumération de toutes ces chaînes on a $\lambda([C_{\tau,x}^{\rho}]) \ge 2^{-d-1} \times 2^{-|\tau|}$, on énumère $\langle x, |\tau| + d + 1 \rangle$ dans l'ensemble borné de requêtes $L_d$. Cela conclut la construction.

Montrons que $L_d$ est bien un ensemble borné de requêtes pour tout $d$. On énumère au plus un élément $\langle x, |\tau| + d + 1 \rangle$ dans $L_d$ pour chaque ensemble affamé, auquel cas cette énumération arrive au moment où l'ensemble $C_{\tau,x}^{\rho}$ correspondant est $\ll$ à moitié repu $>$, c'est-à-dire vérifie $\lambda([C_{\tau,x}^{\rho}]) \ge 2^{-d-1-|\tau|}$. On a en particulier

$$ \text{poids}(L_d) = \sum_{\langle x, |\tau| + d + 1 \rangle \in L_d} 2^{-d-1} \times 2^{-|\tau|} \le \sum_{\langle \rho, \tau, x \rangle} \lambda([C_{\tau,x}^{\rho}]). $$

Il suffit alors de remarquer que par construction les ouverts $[C_{\tau,x}^{\rho}]$ sont deux à deux disjoints. On a alors en particulier par additivité dénombrable de la mesure :

$$ \text{poids}(L_d) \le \sum_{\langle \rho, \tau, x \rangle} \lambda([C_{\tau,x}^{\rho}]) = \lambda(\bigcup_{\langle \rho, \tau, x \rangle} [C_{\tau,x}^{\rho}]) \le 1. $$

L'ensemble $L_d$ est donc bien un ensemble borné de requêtes.

Pour $d$ fixé, on définit $\mathcal{U}_d^A = \bigcup_{\rho<A, \tau, x} [C_{\tau, x}^{\rho}]$, où les ensembles $C_{\tau,x}^{\rho}$ sont ceux produits par l'algorithme avec $d$ comme paramètre. Montrons que $\bigcap_d \mathcal{U}_d^A$ est un A-test de Martin-Löf. On a

$$ \lambda(\mathcal{U}_d^A) \le \sum_{\rho<A, U^\rho(\tau)\downarrow=x} \lambda([C_{\tau,x}^\rho]) \le \sum_{\rho<A, U^\rho(\tau)\downarrow} 2^{-d} \times 2^{-|\tau|} \le 2^{-d} \times \Omega^A \le 2^{-d}. $$

Donc, $\bigcap_d \mathcal{U}_d^A$ est bien un A-test de Martin-Löf.

Finissons à présent la preuve : comme $Z \notin \mathcal{U}_d^A$. Montrons que pour un tel $d$, pour tous $\tau, x$ tels que $U^\rho(\tau)\downarrow=x$ pour $\rho<A$, l'ensemble $C_{\tau,x}^{\rho}$ est toujours $\ll$ à moitié repu $>$, i.e. que la mesure de $[C_{\tau,x}^{\rho}]$ atteint forcément $2^{-d-1} \times 2^{-|\tau|}$. Notons que si c'est bien le cas, alors aussi pour tous $\tau, x$ tels que $U^A(\tau)\downarrow=x$, on énumère $\langle x, |\tau| + d + 1 \rangle$ dans $L_d$, ce qui implique bien $K_{M_d}(\sigma) \le K^A(\sigma)$ pour toute chaîne $\sigma$. Soient $\tau, x$ et $\rho < A$ tels que $U^\rho(\tau)\downarrow=x$. Supposons par l'absurde que

$$ \lambda([C_{\tau,x}^{\rho}]) < 2^{-d-1} \times 2^{-|\tau|}. $$

Soit $\sigma < Z$ suffisamment grand tel que $2^{-|\sigma|} < 2^{-d-1} \times 2^{-|\tau|}$ et tel que $\Phi(\sigma) \succeq \rho$. Si à ce moment une chaîne $\sigma'$ telle que $\sigma' < \sigma$ ou tel que $\sigma < \sigma' < Z$ est déjà énumérée dans un ensemble affamé $C_{\tau', x'}^{\rho'}$, ce sera forcément pour $\rho' < A$ puisque $\Phi(Z) = A$. Dans ce cas, $Z \in \mathcal{U}_d^A$, ce qui est
une contradiction. Sinon, il existera une chaîne $\iota$ avec $\sigma \preceq \iota \prec Z$ tel que [$\iota$] admet à ce moment une intersection vide avec tous les ensembles affamés. Comme l'énumération de $\iota$ dans $C_{\tau,x}^{\rho}$ laisse la mesure de $[C_{\tau,x}^{\rho}]$ en dessous de $2^{-d} \times 2^{-|\tau|}$, alors $\iota$ est énuméré dans $C_{\tau,x}^{\rho}$ et $Z \in \mathcal{U}_d^A$, ce qui est encore une contradiction. Donc, pour tous $\tau, x$ et pour $\rho \prec A$ tels que $U^{\rho}(\tau) \downarrow = x$, la mesure de l'ensemble $[C_{\tau,x}^{\rho}]$ atteint forcément $2^{-d-1} \times 2^{-|\tau|}$, et par conséquent $\langle x, |\tau| + d + 1 \rangle$ est énuméré dans $L_d$. Ainsi, la machine $M_d$ construite à partir de $L_d$ est telle que $K_{M_d}(\sigma) \leq^+ K^A(\sigma)$ pour toute chaîne $\sigma$. Par suite, $A$ est low-pour-K. $\blacksquare$

<figure><img src="image_131.png" /><figcaption>FIGURE 1.8 – Illustration du mécanisme des ensembles affamés. Quand $U^{\rho_3}(\tau_3)[t] = x_3$, on cherche à remplir l'ensemble affamé $C_{\tau_3, x_3}^{\rho_3}$ avec des chaînes $\sigma$ telles que $\Phi(\sigma) \succeq \rho_3$, tout en gardant les ensembles affamés deux à deux disjoints. C'est pour cela que l'on découpe $\sigma$ en deux parties $B_{0,\sigma}$ et $B_{1,\sigma}$, où $B_{1,\sigma}$ contiendra le morceau de $\sigma$ qui n'est pas déjà dans un ensemble affamé. Si un jour $C_{\tau_3, x_3}^{\rho_3}$ est à moitié rempli (c'est-à-dire atteint un poids de $2^{-|\tau_3|-d-1}$), on énumère $\langle x_3, |\tau_3| + d + 1 \rangle$ dans notre ensemble borné de requêtes $L_d$.</figcaption></figure>
### Corollaire 1.9 (Hirschfeldt, Nies and Stephan [90])

Les trois énoncés suivants sont équivalents.

(1) A est low-pour-K.

(2) A est low-pour-MLR.

(3) A est une base pour l'aléatoire.

**PREUVE.** (1) $\rightarrow$ (2) vient de la proposition 1.4. Montrons (2) $\rightarrow$ (3). Supposons A low-pour-MLR. D'après le théorème 18-3.4, il existe un MLR Z tel que $Z \geq_{T} A$. Comme A est low-pour-MLR, alors Z est aussi MLR($A$), et donc A est une base pour l'aléatoire. Pour finir, (3) $\rightarrow$ (1) est donné par le théorème précédent. ■

Il est temps à présent de rentrer dans le vif du sujet, et de montrer que les ensembles K-triviaux sont tous low-pour-K.

## 2. Le processus d'or

La preuve des ensembles affamés aura peut-être ouvert l'appétit du lecteur pour les constructions complexes. Que ce dernier se rassure, nous abordons à présent la construction la plus difficile de l'aléatoire algorithmique, dite « du processus d'or », et dont l'objectif sera de montrer le théorème suivant.

### Théorème 2.1 (Hirschfeldt, Nies [166])

Les ensembles K-triviaux coïncident avec les ensembles low-pour-K.

Le lecteur préférant la simplicité peut toutefois se rassurer : il existe une autre preuve du fait que tous les ensembles K-triviaux sont low-pour-K, qui elle ne repose pas sur une construction si compliquée et que nous présentons à la fin de ce chapitre. Insistons toutefois sur le fait que cette deuxième preuve n'est pas réellement « plus simple » : elle utilise une série de résultats intermédiaires —dont la preuve des ensembles affamés— tous plus simples à montrer, et qui mis bout à bout arrivent au résultat final. Il est en revanche parfaitement impossible avec cette deuxième preuve de comprendre *pour-quoi* les ensembles K-triviaux sont tous low-pour-K. La première preuve que nous présentons ci-après est certes difficile, mais honnête et sans détours. La construction du *processus d'or*, pour aussi complexe qu'elle soit, montre parfaitement les mécanismes à l'œuvre, et toute personne suffisamment vaillante pour en comprendre les rouages saura réellement pourquoi et comment les ensembles K-triviaux sont tous low-pour-K. La deuxième preuve a bien entendu elle aussi ses avantages, ne serait-ce que parce que chaque résultat intermédiaire de cette preuve détournée a son intérêt propre.
La présente section est entièrement consacrée à la preuve du théorème 2.1. Soit $\mathcal{U}$ la machine à oracle sans préfixe universelle du théorème 19-2.3. Soit $\mathcal{A}$ un ensemble K-trivial via une constante $c$, c'est-à-dire tel que

$$K(A \upharpoonright_n) \le K(n) + c, \text{ pour tout } n.$$

Nous allons prouver qu'un tel ensemble $\mathcal{A}$ est forcément low-pour-K, c'est-à-dire que l'on a aussi $K(\sigma) \le K^A(\sigma)$ pour toute chaîne $\sigma$. Nous construirons à cet effet une machine sans préfixe $M$ telle que $K_M(\sigma) \le K^A(\sigma)$ pour toute chaîne $\sigma$.

**Idée générale.** Comme $\mathcal{A}$ est K-trivial, nous savons d'après le corol- laire 16-4.9 qu'il est $\Delta_2^0$. Nous allons donc utiliser l'approximation de $\mathcal{A}$ pour construire notre machine $M$, dont le but sera de faire aussi bien —à constante près— que la machine universelle $\mathcal{U}$ sur l'oracle $\mathcal{A}$. Pour ce faire, dès que l'on a $U^\rho(\tau)[s] = \sigma$ à une étape de calcul $s$ pour $\rho < A_s$ et pour des chaînes $\tau$ et $\sigma$, on aimerait énumérer le couple $(\sigma, |\tau|)$ dans un ensemble borné de requêtes. Le problème est évidemment que $\rho < A_s$ — l'approxi- mation courante de $\mathcal{A}$ utilisée pour envoyer $\tau$ sur $\sigma$ — n'est peut-être pas la bonne. Si cette dernière change, on aura pour ainsi dire « perdu » l'en- voi d'une chaîne de taille $|\tau|$ vers $\sigma$, sans que cela ne corresponde à ce qui se passe avec le vrai oracle $\mathcal{A}$. Nous dirons alors que l'on perd la quan- tité $2^{-|\tau|}$, qui sera décomptée de notre ensemble borné de requêtes, dont le poids, rappelons-le, ne doit pas dépasser 1.

Afin d'éviter trop de perte, nous n'allons pas tout de suite énumérer le couple $(\sigma, |\tau|)$ dans notre ensemble borné de requêtes. Nous demanderons d'abord à l'approximation courante de $\mathcal{A}$, des « preuves » de sa solidité. Cela se fera via la construction d'une machine tierce $M_d$, construite elle aussi via un ensemble borné de requêtes $L_d$. Soit $c_d$ un entier tel que

$$K(\sigma) \le K_{M_d}(\sigma) + c_d, \text{ pour toute chaîne } \sigma.$$

On va énumérer dans $L_d$ le couple $(n, l)$ pour une certaine taille $l$ et un certain $n \ge |\rho|$, puis attendre d'avoir $K(A_s \upharpoonright_n)[s] \le l + c + c_d$ (rappelons que $c$ est la constante de K-trivialité de notre ensemble $\mathcal{A}$). Notons que si $L_d$ est réellement un ensemble borné de requêtes, on doit avoir $K_{M_d}(n) \le l$. Donc, $K(n) \le K_{M_d}(n) + c_d \le l + c_d$. Comme $K(A \upharpoonright_n) \le K(n) + c$, on doit avoir aussi $K(A \upharpoonright_n) \le l + c + c_d$.

Si durant cette attente de validation le préfixe $\rho < A_s$ reste inchangé, alors il aura prouvé sa solidité, et seulement à ce moment-là nous énumérerons le couple $(\sigma, |\tau|)$ dans notre ensemble borné de requêtes. Bien sûr, une fois que $\rho$ a été validé, cela ne signifie pas qu'il ne changera plus, mais à chaque fois qu'il change on a forcé $K(A_s \upharpoonright_n)$ à être en dessous d'une certaine valeur, pour un mauvais préfixe de $A_s$, l'objectif est de faire en sorte que cela ne puisse pas arriver trop souvent sans que l'on ait $\sum_{\sigma} 2^{-K(\sigma)} > 1$.
La construction utilisera un arbre de processus, à branchement infini, mais de hauteur finie. Chacun de ces processus s'efforcera de construire une machine M telle que $K_M(\sigma) \leq^+ K^A(\sigma)$. Si chaque processus travaillera à sa propre tentative de montrer que A est low-pour K, via sa propre machine, tous les processus partagerons en revanche un même ensemble borné de requêtes $L_d$ dont le rôle est discuté ci-dessus. L'algorithme dans sa globalité utilise le théorème du point fixe pour avoir accès à la constante $c_d$ associée à la machine $M_d$ que nous construisons.

**Notion de i-ensemble.** On dit qu'un ensemble $E \subseteq \mathbb{N} \times \mathbb{N}$ est un *i-ensemble* à l'étape $s$ si tout $(n,l) \in E$ a été énuméré dans $L_d$ à une étape $t \leqslant s$ et si l'on a $i$ approximations distinctes $A_r \upharpoonright_n$, avec $t \leqslant r \leqslant s$, qui sont chacune telle que $K(A_r \upharpoonright_n) \leqslant l + c + c_d$. Le poids d'un *i*-ensemble est donné par poids($E$) = $\sum_{(n,l) \in E} 2^{-l}$. On suppose de plus que, pour deux éléments distincts $(n_1, l_1)$, $(n_1, l_2) \in E$, on a $n_1 \neq n_2$.

On fixe $k = 2^{c+d+1}$. Chacun de nos processus va créer un *i*-ensemble pour $i \leqslant k$. Le point de départ du futur argument du processus d'or est le lemme suivant.

**Lemme 2.2.** Si $E$ est un $k$-ensemble, alors poids($E$) < $\frac{1}{2}$. ★

**PREUVE.** Pour tout $(n, l)$ dans $E$, on a $k$ chaînes distinctes $\rho_1, \dots, \rho_k$ de taille $n$ telles que $K(\rho_i) \leq l + c + c_d$ pour $i \leq k$, et donc telles que

$$2^{-l-c-c_d} \leq 2^{-K(\rho_i)}, \text{ pour } i \leq k.$$

En particulier, $k \times 2^{-l-c-c_d} \leq \sum_{i \leq k} 2^{-K(\rho_i)}$. De plus, les éléments de $E$ sont tous distincts deux à deux sur leur première coordonnée. On a donc

$$k \times \sum_{(n,l) \in E} 2^{-l-c-c_d} \leq \sum_{\rho} 2^{-K(\rho)} < 1.$$

Par suite, $k \times 2^{-c-c_d} \times \text{poids}(E) < 1$. Comme $k = 2^{c+d+1}$, on a par conséquent poids($E$) < $\frac{1}{2}$. ■

Nous allons donner d'ici peu la description de $k$ programmes $P_1, \dots, P_k$ distincts, où chaque instance de $P_i$ sera un processus chargé de produire un *i*-ensemble.

**Arbre des processus.** L'algorithme consistera en un arbre dynamique de processus, où chaque nœud de hauteur $i$ sera une instance du programme $P_{k-i}$. Dans cet arbre, les processus fils d'un nœud correspondent aux processus appelés par ce nœud. Chaque nœud reste dans l'arbre tant que son processus correspondant tourne, et disparaît avec tous ses fils quand le processus s'arrête, ou bien est stoppé par un de ses processus ascendants.
L'algorithme commence par exécuter une unique instance de $P_k$, qui sera la racine de notre arbre. Cette instance de $P_k$ appellera une infinité de processus fils, chacun étant une instance de $P_{k-1}$, chacun de ses processus fils appellera à son tour des instances de $P_{k-2}$ et ainsi de suite. Les feuilles de cet arbre seront donc des instances de $P_1$.

Chaque instance du programme $P_i$ aura la charge d'énumérer son propre i-ensemble, avec l'aide des processus fils qu'il appelle. Ainsi, chaque instance de $P_1$ — les feuilles de l'arbre — entamera l'énumération d'un 1-ensemble. Chaque instance de $P_2$ entamera l'énumération d'un 2-ensemble, avec l'aide des 1-ensembles énumérés par ses processus fils, puis chaque instance de $P_3$ entamera l'énumération d'un 3-ensemble, avec l'aide des 2-ensembles énumérés par ses processus fils, et ainsi de suite.

**Paramètres des processus.** Chaque programme $P_i$ prend trois paramètres en entrée.

1. Le paramètre de seuil $p$: il s'agit d'un nombre rationnel plus petit que 1, qui correspond à un seuil à atteindre pour $P_i$, c'est-à-dire que $P_i$ essaiera d'énumérer un i-ensemble $F_i$ de poids $p$.

2. Le paramètre de pas $\delta$: il s'agit d'un rationnel $\le p$ et qui correspond à « la vitesse » à laquelle $P_i$ essaiera d'atteindre son seuil $p$, c'est-à-dire qu'il énumérera dans son i-ensemble des couples $(n, -\log_2(\delta))$. Pour cette raison, on demande donc que $p$ soit un multiple de $\delta$.

3. Le paramètre de taille $w$: le dernier paramètre de $P_i$ correspond à la taille d'un préfixe d'une certaine approximation de $A$, cette taille devant augmenter au fur et à mesure des appels récursifs. Cela sera clarifié par la suite.

Expliquons brièvement l'idée du paramètre de seuil $p$. Quand le poids du i-ensemble d'un processus atteint son seuil $p$, ce processus s'arrête, et arrête récursivement tous ses processus fils : les éléments de son i-ensemble sont à présent prêts à être promus en éléments du $(i+1)$-ensemble de son processus parent. Cela arrivera si jamais l'approximation d'un préfixe de $A$ — d'une taille bien spécifique, que l'on détaillera par la suite — change à nouveau.

Expliquons brièvement l'idée du paramètre de pas $\delta$. Par définition, avant d'énumérer $(n, l)$ dans un i-ensemble, on doit d'abord l'énumérer dans $L_d$. Le souci est que le poids $2^{-l}$ correspondant à $(n, l)$ est susceptible d'être « dépensé pour rien ». Cela arrive si après l'énumération de $(n, l)$ dans $L_d$, l'approximation correspondante de $A_s \upharpoonright_n$ de $A \upharpoonright_n$ change avant que l'on ait $K(A_s \upharpoonright_n) \le l+c+c_d$. Une instance de $P_i$ va donc remplir son i-ensemble petit à petit avec un pas de $\delta$, où $\delta$ correspond à une perte potentielle. L'ensemble de tous les paramètres $\delta$ à choisir doit donc être tel que le poids total qui peut être perdu — c'est-à-dire la somme des paramètres $\delta$ — n'est pas trop importante.
Expliquons enfin l'idée du paramètre taille $w$. Il s'agit de la taille du préfixe courant de $A$ qui est en attente de validation par le processus parent. Il sera nécessaire pour le processus courant de ne faire valider que des préfixes de taille supérieure à $w$, et ainsi de suite, jusqu'aux processus feuilles.

**Le processus d'or.** Le cœur de la preuve réside dans l'idée du processus d'or. Chaque instance de $P_i$ essaiera de créer sa propre machine $M$, via un ensemble borné de requêtes $L$, telle que $K_M(\sigma) \le + K^A(\sigma)$ pour toute chaîne $\sigma$. Le $i$-ensemble d'une instance de $P_i$ ne sert pas uniquement comme étape à la création du $(i+1)$-ensemble de son processus parent. Il correspond également au poids qui est « perdu » pour cette instance lors de sa tentative de création d'une machine $M$ telle que $K_M(\sigma) \le + K^A(\sigma)$ pour toute chaîne $\sigma$.

Nous avons vu que le poids du $k$-ensemble du processus racine de l'arbre reste toujours en dessous de $1/2$. De ce fait, ce qui est perdu par le processus racine est borné, et c'est là tout l'objectif : le poids qui est perdu est celui qui a été dépensé pour essayer de faire aussi bien que la machine universelle $U^A$, mais sur de mauvais préfixes de $A$. Si cette quantité perdue est toujours plus petite que $1/2$, alors il reste « la moitié » de la place totale pour réellement faire aussi bien que $U^A$ — à constante près, bien sûr. On ne peut toutefois pas en conclure que le processus racine réussira à énumérer la machine $M$ désirée : il se pourrait que la validation d'un certain préfixe de $A$ ne vienne jamais, et il suffit pour cela qu'une instance d'un processus fils n'atteigne lui-même jamais son seuil. Néanmoins, si cela arrive, ce processus fils sera lui-même un candidat pour la création d'une machine $M$ telle que $K_M(\sigma) \le + K^A(\sigma)$, pour toute chaîne $\sigma$. Cela fonctionnera si toutes ses demandes de validations aboutissent — tant que $A$ ne change pas en cours de validation, bien sûr —, c'est-à-dire si tous ses processus fils sont soit stoppés avant validation, ou alors atteignent eux-mêmes leur seuil. Si l'un d'eux n'atteint jamais son seuil, on descend alors encore dans l'arbre jusqu'à arriver à des instances de $P_2$, pour lesquelles nous montrerons que les validations aboutissent toujours.

Ainsi, un processus qui n'est jamais stoppé par un de ses nœuds ascendants, qui n'atteint jamais son seuil et pour lequel toutes ses demandes de validation aboutissent sera un processus d'or, qui aboutira à la création d'une machine $M$ telle que $K_M(\sigma) \le + K^A(\sigma)$ pour toute chaîne $\sigma$.

**Les étapes spéciales de calcul.** Afin de simplifier la description de l'algorithme, nous travaillerons avec des étapes de calcul spéciales, c'est-à-dire des étapes pour lesquelles l'ensemble *A* semble K-trivial. Formellement, on a $s_0 = 1$ et $s_{n+1}$ est le plus petit temps de calcul strictement plus grand que $s_n$ et tel que $K(A_{s_{n+1}}[m])[s_{n+1}] \le K(m)[s_{n+1}] + c$, pour tout $m \le s_n$. Nous noterons *étapes de calcul* (en italique) ces étapes de
calcul spéciales $s_0, s_1, s_2, \dots$, et l'algorithme se restreindra à ces étapes spéciales.

La raison de ces étapes de calcul est qu'une fois $K(A_s \upharpoonright_n)[s] \le l+c+c_d$ pour un certain $l$, si $A_{s+1} \upharpoonright_n \ne A_s \upharpoonright_n$ on veut mettre $(n,l)$ dans un 2-ensemble, mais cela n'est possible que si l'on a aussi $K(A_{s+1} \upharpoonright_n)[s+1] \le l+c+c_d$. Pour cette raison-là, à la place de chercher une étape de calcul $s$ telle que $K(A_s \upharpoonright_n)[s] \le l+c+c_d$, on cherchera à la place une étape $s > n$ telle que $K(n)[s] \le l+c_d$. De cette manière, tant que l'on ne travaille que sur nos étapes de calcul, on aura toujours $K(A_t \upharpoonright_n)[t] \le K(n)[t] + c \le l+c+c_d$, pour n'importe quelle étape $t \ge s$.

**Description de l'algorithme.** Nous commençons par rappeler ici les différentes notations utilisées pour l'algorithme :

▷ $A$ est notre ensemble $\Delta_2^0$ et $K$-trivial via la constante $c$,

▷ $U^A$ est la machine universelle qui définit notre complexité $K^A$ et pour laquelle on essaye de construire $M$ telle que $K_M(\sigma) \le^+ K^A(\sigma)$ pour toute chaîne $\sigma$.

L'algorithme global crée un arbre de processus en commençant par appeler une instance du programme $P_k$ décrit ci-dessous, avec comme paramètre de seuil $p = \frac{3}{4}$, comme paramètre de pas $\delta = \frac{1}{4} \times 2^{-1}$ et comme paramètre taille $w = 0$. L'instance de $P_k$ appellera à son tour des instances du programme $P_{k-1}$, qui elles-mêmes appelleront des instances du programme $P_{k-2}$, et ainsi de suite.

Chaque processus appelé participe à la création d'un ensemble borné de requêtes commun $L_d$, qui sert lui-même à construire une machine $M_d$. À l'aide du théorème du point fixe, l'algorithme global utilise une constante $c_d$ telle que $K(\sigma) \le K_{M_d}(\sigma) + c_d$ et pour laquelle on a $k = 2^{c+c_d+1}$.

On termine avec une dernière considération sur les étapes de calcul et la manière dont s'effectue le parallélisme entre les différents processus. En pratique, un « agenceur global » simule le parallélisme en répartissant les différentes étapes de calcul entre les différents processus à exécuter. Pour simplifier la présentation, cet agencement est implicite, et le déroulement de chaque processus est décrit étape par étape. Nous donnons juste la contrainte suivante pour l'agenceur global : une étape $s$ d'un processus parent est exécuté avant la même étape $s$ de ses processus fils.

Il sera enfin utile, pour la création de l'ensemble borné de requêtes $L_d$ qui sera partagé entre tous les processus, d'avoir accès à un entier unique par processus et temps de calcul. Nous utiliserons pour cela le temps de calcul de l'agenceur global et pour une étape de calcul $s$ au sein d'un processus, on notera $s^*$ l'étape de calcul globale correspondante. Sans plus tarder voici, sur la page ci-après, l'algorithme.
Programme $P_i$ pour $1 < i \le k$

**Entrée:** Le seuil $p$, le pas $\delta$ et la taille $w$

**Sortie :** Un $i$-ensemble $F_i$ et un ensemble borné de requêtes $L$

**Pour toute étape $s$ faire**

**Pour toute sous-étape $\langle \tau, \sigma \rangle \le s$ faire**

**Si $\langle \tau, \sigma \rangle$ est marqué comme disponible alors**

**Si $\exists \rho \preceq A_s$ tel que $U^\rho(\tau)[s] = \sigma$ alors**
Soit $\rho_{\tau,\sigma}$ le plus petit préfixe de $A_s$ de taille plus grande
que $\min(w, |\rho|)$.

Soit $w_{\tau,\sigma}$ la taille de $\rho_{\tau,\sigma}$.

Soit $\delta'$ le plus grand rationnel plus petit que $\frac{1}{4} \times 2^{-s^*}$
tel que $2^{-|\tau|} \times \delta$ est un multiple de $\delta'$.

On appelle alors le programme $P_{i-1}(2^{-|\tau|} \times \delta, \delta', w_{\tau,\sigma})$.
On note $P_{i-1,\tau,\sigma}$ le processus correspondant et $F_{i-1,\tau,\sigma}$ son $(i-1)$-ensemble.

On marque $\langle \tau, \sigma \rangle$ comme indisponible.

**Fin**

**Fin**

**Si**

$\langle \tau, \sigma \rangle$ est marqué comme indisponible après un appel à $P_{i-1,\tau,\sigma}$
**alors**

**Si le processus $P_{i-1,\tau,\sigma}$ est terminé alors**
On énumère $(\sigma, |\tau| - \log_2(\frac{\delta}{p+\delta}))$ dans $L$.

**Fin**

**Si $A_s \upharpoonright_{w_{\tau,\sigma}}$ est différent de $\rho_{\tau,\sigma}$ alors**
On marque $\langle \tau, \sigma \rangle$ comme disponible.

Si le processus $P_{i-1,\tau,\sigma}$ n'est pas terminé, on l'annule
ainsi que tous ses sous-processus (en
conservant $F_{i-1,\tau,\sigma}$)

On énumère les éléments de $F_{i-1,\tau,\sigma}$ dans $F_i$.

**Si poids($F_i$) $\ge p$ alors**
On arrête le programme ainsi que tous ses
sous-processus.

**Fin**

**Fin**

**Fin**

**Fin**

**Fin**
Programme $P_1$

Entrée: Le seuil $p$, le pas $\delta$ et la taille $w$

Sortie : Un 1-ensemble $F_1$

Pour toute étape $s > w$ faire

Soit $n = s^*$ (que l'on suppose aussi plus grand que $w$).

On énumère $(n, -\log_2(\delta))$ dans $L_d$.

On attend une étape $t > n$ telle que $K(n)[t] \le -\log_2(\delta) + c_d$

On énumère $(n, -\log_2(\delta))$ dans $F_1$

Si poids($F_1$) $\ge p$ alors

On arrête le programme.

Fin

Fin

Passons à présent à la vérification formelle.

**Montrons que la sortie $F_i$ de chaque instance de $P_i$ est un i-ensemble.** Commençons par le fait suivant.

(1) Soient $(n_1, l_1)$, $(n_2, l_2)$ deux couples énumérés dans n'importe quel 1-ensemble durant l'algorithme à des étapes différentes ou par des processus différents. Alors, $n_1 \ne n_2$.

Cela vient du fait que de tels couples $(n_1, l_1)$, $(n_2, l_2)$ sont énumérés à deux étapes globales distinctes $s_1^* \ne s_2^*$ qui seront par construction telles que $n_1 = s_1^*$ et $n_2 = s_2^*$. Montrons que chaque ensemble $F_1$ énuméré par une instance de $P_1$ est un 1-ensemble à chaque étape de calcul. Tout d'abord (1) permet de satisfaire l'une des conditions pour être un 1-ensemble, c'est-à-dire avoir des éléments deux à deux distincts sur leur première coordonnée.

Pour l'autre condition, si à une étape $s$ on énumère $(n, l)$ dans un 1-ensemble, cela signifie que $K(n)[t] \le l + c_d$. Comme $t$ est une étape de calcul, alors $K(A_t \rfloor_n)[t] \le K(n)[t] + c \le l + c + c_d$, et l'on satisfait donc bien l'autre condition pour être un 1-ensemble.

Supposons à présent que chaque ensemble $F_{i,\tau,\sigma}$ associé à une instance $P_{i,\tau,\sigma}$ de $P_i$ soit un *i*-ensemble à chaque étape de calcul. Supposons qu'à une étape $s$, on promeut un élément $(n, l)$ d'un *i*-ensemble $F_{i,\tau,\sigma}$ vers le $(i+1)$-ensemble $F_{i+1}$ d'une instance de $P_{i+1}$. D'après (1), tous les éléments de $F_{i+1}$ après cette énumération restent deux à deux distincts sur leur première coordonnée.
Par construction, on a également :

▷ une étape $t < s$ et un entier $w_{\tau,\sigma} < n$ tels que $A_t \upharpoonright_{w_{\tau,\sigma}} \neq A_s \upharpoonright_{w_{\tau,\sigma}}$;

▷ une étape $r$ avec $t < r < s$ telle que $K(n)[r] \le l + c_d$ (et donc telle que $(n,l)$ entre dans un 1-ensemble);

▷ une étape entre $r$ et $s$ telle que le couple $(n,l)$ arrive dans le *i*-ensemble $F_{i,\tau,\sigma}$.

On a $K(A_s \upharpoonright_n)[s] \le K(n)[s] + c \le K(n)[r] + c \le l + c + c_d$, car $s$ est une étape de calcul plus grande que $r$. Donc, $A_s \upharpoonright_n$ est un bon candidat pour faire de $(n,l)$ l'élément d'un $(i+1)$-ensemble. On doit toutefois vérifier que $A_s \upharpoonright_n$ est différent de toutes les autres chaînes $\rho_1, \dots, \rho_i$ de taille $n$ qui font de $(n,l)$ l'élément du *i*-ensemble $F_{i,\tau,\sigma}$. N'oublions pas en effet qu'une approximation $\Delta_2^0$ peut revenir à une valeur déjà rencontrée par le passé. Il suffit de montrer que $A_t$ partage ses $w_{\tau,\sigma}$ premiers bits avec chaque $\rho_j$ pour $j \le i$. Si c'est bien le cas, comme on a $A_t \upharpoonright_{w_{\tau,\sigma}} \neq A_s \upharpoonright_{w_{\tau,\sigma}}$, alors $A_s \upharpoonright_n$ sera bien une chaîne distincte de chaque $\rho_j$. Il suffit pour cela de voir que $s$ est, au sein de notre instance de $P_{i+1}$, la plus petite étape telle que $A_t \upharpoonright_{w_{\tau,\sigma}} \neq A_s \upharpoonright_{w_{\tau,\sigma}}$ et de se souvenir que les étapes des processus parents sont traités avant les étapes des processus fils.

**Montrons que $L_d$ est bien un ensemble borné de requêtes.** Le poids total qui est énuméré dans $L_d$ par un processus $P_{1,\tau,\sigma}$ exécuté avec paramètre $(p, \delta, w)$ est borné par le poids de son 1-ensemble plus $\delta$. En effet, par construction, pour chaque $(n, -\log_2(\delta))$ énuméré dans $L_d$, on énumère aussi $(n, -\log_2(\delta))$ dans le 1-ensemble à moins que le processus ne soit stoppé par un de ses nœuds ascendants, ce qui n'arrive qu'une fois. Le poids que l'on perd est alors de $\delta$.

Étant donné une instance de $P_{i+1}$ exécutée avec paramètre $(p, \delta, w)$, soit $C$ l'ensemble des éléments qui sont énumérés dans le *i*-ensemble d'un processus fils de l'instance de $P_{i+1}$, mais qui ne sont pas énumérés dans son $(i+1)$-ensemble. Notons que des éléments sont dans $C$ si l'instance de $P_{i+1}$ est annulée par un de ses nœuds ascendants. Montrons que le poids de $C$ est borné par $\delta$. Au moment où l'instance de $P_{i+1}$ est annulée, soit $(P_{i,\tau_j,\sigma_j})_{j \in \mathbb{N}}$ l'ensemble des processus fils qui ne sont pas terminés. Notons que les $\tau_j$ sont forcément dans le domaine de $U^\rho$ pour des chaînes $\rho$ deux à deux compatibles : ces chaînes $\rho$ sont des préfixes d'une certaine approximation de $A_s$, et quand cette approximation change le processus fils correspondant est annulé par $P_{i+1}$ lui-même. Soit $\rho$ la plus grande de toutes ces chaînes. Comme le poids du *i*-ensemble correspondant à $P_{i,\tau_j,\sigma_j}$ est borné par $2^{-\tau_j}\delta$, alors le poids total est borné par $\delta \sum_{U^\rho(\tau) \downarrow} 2^{-|\tau|} \le \delta$.

En itérant cette idée, on obtient que la somme des poids totaux de tous les 1-ensembles est bornée par le poids du *k*-ensemble du processus racine de
l'arbre, plus la somme de tous les paramètres de pas $\delta$. Aussi ces paramètres sont-ils choisis de manière à ce que leur somme soit inférieure à 1/4. Comme le poids du k-ensemble du processus racine est toujours inférieur à 1/2, le poids total de ce qui est énuméré dans $L_d$ est bien inférieur à 1.

**Fin de la preuve : le processus d'or.** Montrons à présent qu'il y a un processus $P_{i,\tau,\sigma}$ appelé avec paramètre $(p, \delta, w)$, qui n'est jamais stoppé par un de ses nœuds ascendants, qui n'atteint jamais son seuil $p$, et tel que chaque processus qu'il appelle termine à moins qu'il ne soit stoppé par $P_{i,\tau,\sigma}$.

On sait que le processus racine ne peut pas être stoppé par un autre processus et n'atteint jamais son seuil, par le lemme 2.2. Si chacun de ses processus fils se termine ou est annulé, alors le processus racine est le processus d'or. Sinon, au moins un des processus fils de la racine n'est jamais annulé et n'atteint jamais son seuil. Soit il s'agit du processus d'or, soit également un de ses fils n'est jamais stoppé et n'atteint jamais son seuil. Si l'induction se poursuit jusqu'à un processus de la forme $P_{2,\tau,\sigma}$, ce processus est alors nécessairement le processus d'or, car il n'est jamais annulé, n'atteint jamais son seuil, et tous les processus feuilles de l'arbre atteignent nécessairement leur objectif à moins qu'ils ne soient stoppés par un processus ascendant.

Soit à présent un processus d'or donné par une instance de $P_i$, appelée avec paramètre $(p, \delta, w)$. Soit $F_i$ son i-ensemble et soit $L$ l'ensemble énuméré par ce processus.

**Montrons que $L$ est bien un ensemble borné de requêtes.** Pour chaque couple

$$ (\sigma, |\tau| - \log_2 \left( \frac{\delta}{p + \delta} \right)) $$

énuméré dans $L$, on a $U^\rho(\tau) = \sigma$ pour $\rho \prec A_s$ pour un certain $s$. Ce couple appartient à un $(i-1)$-ensemble créé par le processus fils $P_{i-1,\tau,\sigma}$. Deux cas se présentent.

**Cas 1.** La chaîne $\rho$ est un préfixe de $A$. Si l'on considère la somme des poids des couples associés aux préfixes de $A$, on obtient alors

$$ \sum_{U^A(\tau)\downarrow} 2^{-|\tau|+\log_2\left(\frac{\delta}{p+\delta}\right)} = \frac{\delta}{p+\delta} \sum_{U^A(\tau)\downarrow} 2^{-|\tau|} \le \frac{\delta}{p+\delta}. $$

**Cas 2.** La chaîne $\rho$ n'est pas un préfixe de $A$. Ainsi, lors d'une étape $s$ future, $A_s \upharpoonright_{|\rho|} \ne \rho$, donc le $(i-1)$-ensemble créé par le processus fils $P_{i-1,\tau,\sigma}$ va être intégré au $i$-ensemble $F_i$ créé par le processus d'or $P_i$. La somme des poids des couples associées aux $\rho$ qui ne sont pas préfixes de $A$ est bornée
par la somme suivante, que nous allons simplifier :

$$
\begin{align*}
\sum_{P_{i-1,\tau,\sigma}} 2^{-|\tau|+\log_2\left(\frac{\delta}{p+\delta}\right)} &= \frac{\delta}{p+\delta} \times \frac{\sum_{P_{i-1,\tau,\sigma}} 2^{-|\tau|+\log_2(\delta)}}{\delta} \\
&= \frac{\delta}{p+\delta} \times \frac{\sum_{P_{i-1,\tau,\sigma}} \text{poids}(F_{i-1,\tau,\sigma})}{\delta} \\
&= \frac{\delta}{p+\delta} \times \frac{\text{poids}(F_i)}{\delta}.
\end{align*}
$$

Le poids total de $L$ sera donc borné par

$$
\frac{\delta}{p + \delta} + \frac{\delta}{p + \delta} \times \frac{\text{poids}(F_i)}{\delta}.
$$

Comme $F_i$ n'atteint jamais son seuil, qui est $p$, on a donc :

$$
\frac{\delta}{p + \delta} \left( 1 + \frac{\text{poids}(F_i)}{\delta} \right) \le \frac{\delta}{p + \delta} \left( 1 + \frac{p}{\delta} \right) \le 1.
$$

Donc, $L$ est bien un ensemble borné de requêtes. Soit $M$ la machine cor-
respondante.

Montrons que $K_M(\sigma) \le + K^A(\sigma)$, pour toute chaîne $\sigma$. À présent,
si $U^\rho(\tau)[s] = \sigma$ tel que $A_s \upharpoonright_{|\rho|} \text{ne changera plus jamais, alors le pro-}$
cессus $P_{i-1,\tau,\sigma}$ ne sera jamais annulé. Il atteindra donc son seuil, et l'on
énumérera alors $(\sigma, |\tau| - \log_2(\delta/(p+\delta)))$ dans $L$. Cela conclut la preuve,
car alors

$$
K_M(\sigma) \le K^A(\sigma) - \log_2(\delta/(p+\delta)) \text{ pour toute chaîne } \sigma.
$$

2.1. Conséquences du théorème et de sa preuve

Nous avons à présent terminé la preuve du processus d'or. Voyons-en tout
de suite une conséquence intéressante.

Théorème 2.3 (Nies [166])

La classe des K-triviaux forme un idéal Turing :

(1) si $A$ est $K$-trivial alors tout $B \le_T A$ est $K$-trivial;

(2) si $A_0, A_1$ sont $K$-triviaux, alors $A_0 \oplus A_1$ est $K$-trivial.

PREUVE. Nous avons vu avec l'exercice 16-4.7 que les ensembles K-triviaux sont clos par jointure Turing. Il est clair que les ensembles low-pour-K sont clos par le bas dans les degrés Turing.

■

Remarquons que dans le théorème précédent, ni (1) n'est évident pour les ensembles K-triviaux, ni (2) pour les ensembles low-pour-K. Le fait que les deux classes coïncident est remarquable, et nous donne ce joli résultat.
Souvenons-nous un instant de la preuve du théorème 16-4.5, où l'on construit un ensemble c. e. A non calculable tel que $K(A \upharpoonright_n) \leq^+ K(n)$ pour tout $n$. Durant l'approximation, on assignait le poids $2^{-K(n)[s]}$ à chaque préfixe $A_s \upharpoonright_n$ de l'approximation courante de A pour $n \leq s$, c'est-à-dire la taille à l'étape $s$ de la plus petite chaîne produisant $n$. Cette assignation correspond à ce que l'on place dans un ensemble borné de requêtes pour produire $A_s \upharpoonright_n$. Si à l'étape $s+1$ un entier $x_s < s$ est énuméré dans A, alors on a perdu tout ce que l'on avait assigné à $A_s \upharpoonright_n$ pour $x_s < n \leq s$. La construction garantie alors que la somme totale de tout ce qui est perdu est finie.

Pour construire un ensemble A c. e. non calculable et low-pour-K, on procède de même, mais où l'on assigne cette fois un poids de $\Omega_s^{A_s \upharpoonright n} - \Omega_s^{A_s \upharpoonright n-1}$ à chaque préfixe $A_s \upharpoonright_n$ de l'approximation courante de A. Ici, $\Omega_s^{A_s \upharpoonright n} - \Omega_s^{A_s \upharpoonright n-1}$ est la somme des $2^{-|\tau|}$ tels que $U^{A_s}(\tau)[s] \downarrow$ avec un usage de $A_s$ exactement de $n$. Comme pour la construction d'un ensemble c. e. K-trivial, si $x_s < s$ est énuméré dans A à l'étape $s+1$, on voit alors que l'on perd pour tout $x_s < n \leq s$ la quantité $\Omega_s^{A_s \upharpoonright n} - \Omega_s^{A_s \upharpoonright n-1}$, c'est-à-dire tout ce que l'on a assigné à de mauvais préfixes de A. On peut abstraire ce raisonnement et considérer ce que l'on appelle une *fonction de coût*.

**Définition 2.4.** Une *fonction de coût* est donnée par $c: \mathbb{N} \to \mathbb{Q}$, une fonction $\Delta_2^0$ telle que $\sum_n c(n) < 1$ et telle que $\sum_n c_s(n) < 1$ pour toute approximation $c_s$. L'approximation $(c_s)_{s \in \mathbb{N}}$ d'une fonction de coût peut éventuellement dépendre d'une approximation $\Delta_2^0 (A_s)_{s \in \mathbb{N}}$ d'un ensemble A auquel cas la fonction sera dite *adaptative*. ♦

La fonction de coût pour construire un ensemble K-trivial est $c(n)=2^{-K(n)}$. Celle utilisée pour construire un ensemble low-pour-K est adaptative, et donnée par l'approximation $c_s(n) = \Omega_s^{A_s \upharpoonright n} - \Omega_s^{A_s \upharpoonright n-1}$. Dans les deux cas, on peut construire un ensemble c. e. non calculable tel que ce que l'on perd est fourni par la fonction de coût, donc est finie. Cela nous donne la définition suivante.

**Définition 2.5.** Soit $(A_s)_{s \in \mathbb{N}}$ une approximation $\Delta_2^0$ d'un ensemble A. Soit $S = \{s \in \mathbb{N} : A_s \neq A_{s+1}\}$ et, pour $s \in S$, soit $x_s < s$ le plus petit entier tel que $A_{s+1} \upharpoonright_{x_s} \neq A_s \upharpoonright_{x_s}$. L'approximation de A satisfait une fonction de coût $c$ —éventuellement adaptative— si $\sum_{s \in S} \sum_{x_s < n \leq s} c_s(n)$ est fini. ♦

La preuve du *processus d'or* peut être adaptée pour montrer que l'on peut accélérer l'approximation $\Delta_2^0$ de tout ensemble K-trivial, de manière à montrer qu'elle satisfait n'importe quelle fonction de coût fixée à l'avance. Cela nous donne le théorème suivant.
**Théorème 2.6 (Nies [166])**

Soit $c$ une fonction de coût éventuellement adaptative. Tout ensemble K-trivial $A$ admet une approximation $\Delta_2^0 (A_s)_{s \in N}$ qui satisfait $c$.

On peut alors utiliser cela pour montrer une plusieurs propriétés intéres-
santes, par exemple le fait que tout K-trivial admet une approximation avec
peu de changements.

**Théorème 2.7 (Nies [166])**

Tout ensemble K-trivial admet une approximation $\Delta_2^0$ telle que chaque préfixe de taille $n$ change au plus $n^2 \times d$ fois pour une certaine constante $d$.

PREUVE. Par la proposition 16-2.5, il existe un $d$ tel que $K(n) \le 2\log_2(n)+d$ pour tout $n$. On peut considérer sans perte de généralité que, pour tout $s$, on a $K(n)[s] \le 2\log_2(n)+d$. Il suffit alors d'utiliser la fonction de coût donnée par $c_s(n) = 2^{-K(n)[s]}$. Soit $(A_s)_{s \in N}$ une approximation de $A$ qui satisfait cette fonction de coût et soit $e$ la somme totale du coût qui est perdu. À chaque fois qu'un préfixe de $A$ de taille $n$ change à une étape $s$, cela coûte au moins $2^{-K(n)[s]} \ge 2^{-2\log_2(n)-d} = n^{-2} \times 2^{-d}$. Cela ne peut donc pas arriver plus de $n^2 \times 2^d \times e$ fois sans faire passer le coût au-dessus de $e$. $\blacksquare$

Il est également possible d'utiliser la technique des fonctions de coût pour montrer que tout ensemble K-trivial est borné dans les degrés Turing par un K-trivial c. e. On définit pour cela l'ensemble c. e. C tel que $C$ énumère $\langle n, i \rangle$ à l'étape $s$ si le préfixe de taille $n$ de $A$ change pour la $i$-ième fois à l'étape $s$. On vérifie sans peine que $C \ge_T A$. En effet, pour déterminer le segment initial de $A$ de longueur $n$, il suffit de chercher le plus grand $i$ tel que $\langle n, i \rangle \in C$, et d'exécuter l'approximation de $A$ jusqu'à ce que $A_s \upharpoonright_n i$ ait changé $i$ fois. On montre alors que si une approximation de $A$ satisfait la fonction de coût donnée par $c(n) = 2^{-K(n)}$, alors l'approximation de $C$ doit aussi satisfaire cette fonction de coût, ce que l'on peut utiliser pour montrer que $C$ est lui aussi K-trivial. Nous verrons une preuve alternative de ce fait avec le théorème 4.4.

3. Caractérisation des K-triviaux c. e.

Nous continuons ici notre étude des K-triviaux avec la présentation d'une question qui resta ouverte un certain temps, et dont l'étude amena de nombreux développements, qui entre autres choses permirent de donner une autre preuve du fait que tout K-trivial est low-pour-K.
**3.1. La question**

La question qui vient de l'étude des bases pour l'aléatoire s'est posée après la découverte de la proposition suivante et de son corollaire.

**Proposition 3.1.** Soit $A$ un ensemble c. e., et soit $Z$ un ensemble MLR mais non MLR$(A)$. Alors, $Z \oplus A \geq_T \emptyset'$.

**PREUVE.** Soit $\bigcap_n U_n^A$ un $A$-test de Martin-Löf tel que $Z \in \bigcap_n U_n^A$. Notons que l'on peut supposer d'après le théorème 19-2.3 que $\bigcap_n U_n^X$ est un test de Martin-Löf pour tout ensemble $X$. On décrit à présent $(\mathcal{V}_n)_{n \in \mathbb{N}}$ des classes $\Sigma_1^0$ utilisées pour créer un tel test. Si $n$ est énuméré dans $\emptyset'$ à l'étape $t$, on énumère alors $U_n^{A_t}[t]$ dans $\mathcal{V}_n$. Si $n$ n'est jamais énuméré dans $\emptyset'$, alors $\mathcal{V}_n$ reste vide. Comme $Z$ est MLR, il existe donc $n$ tel que $Z \notin \bigcup_{m \ge n} \mathcal{V}_m$. On peut à présent décider si un entier $m \ge n$ appartient à $\emptyset'$ à l'aide de $Z \oplus A$ de la manière suivante. Soit $t$ le plus petit temps de calcul tel que $Z \in U_m^A[t]$, et soit $\rho$ le préfixe de $A$ tel que $U_m^\rho[t] = U_m^A[t]$. On cherche alors $t'$ le plus petit temps de calcul tel que $A_{t'} \upharpoonright_{|\rho|} A \upharpoonright_{|\rho|}$. On a alors $m \in \emptyset'$ ssi $m \in \emptyset'[\max(t, t')]$. En effet, si $m$ rentre dans $\emptyset'$ à un temps de calcul $s > \max(t, t')$, alors on aura toujours $A_s \upharpoonright_{|\rho|} A \upharpoonright_{|\rho|}$, car $A$ est c. e., et l'on a donc $Z \in U_m^\rho[s] \subseteq U_m^{A_s}[s] = \mathcal{V}_m$, ce qui contredit $Z \notin \mathcal{V}_m$. $\blacksquare$

**Corollaire 3.2 (Hirschfeldt, Nies and Stephan [90])**

Soit $Z$ un ensemble MLR incomplet, et soit $A$ un ensemble c. e. tel que $Z \ge_T A$. Alors, $A$ est K-trivial.

**PREUVE.** Puisque $Z \ge_T A$ et que $Z$ est incomplet, alors $Z \oplus A \not\ge_T \emptyset'$. Donc, d'après la proposition 3.1, $Z$ est MLR$(A)$, et $A$ est alors une base pour l'aléatoire. D'après le théorème 1.7, $A$ est donc low-pour-K, et dès lors K-trivial. $\blacksquare$

Qu'en est-il de la réciproque du corollaire 3.2 ? Les ensembles K-triviaux c. e. sont-ils nécessairement calculables par un ensemble MLR incomplet ? Cette question a fait l'objet de nombreux travaux et développements, pour ne citer que [13] [17] [18] [19] [43], aboutissant à une réponse positive, permettant au passage, conjointement avec d'autres résultats, de donner une preuve alternative du fait que les ensembles K-triviaux sont, comme il se doit, tous low-pour-K.

**Exercice 3.3.** (⋆) Montrer que le corollaire 3.2 ne peut pas être étendu aux ensembles $\Delta_2^0$. ◇
## 3.2. L'aléatoire d'Oberwolfach

Oberwolfach est une petite commune de quelques milliers d'habitants, perdue au cœur de la Forêt noire du Pays de Bade, en Allemagne. C'est ici qu'émergera durant la Seconde Guerre mondiale un centre de recherche en mathématiques, qui deviendra l'un des plus célèbres et des plus importants au monde. Toute l'année, des mathématiciens de tous les pays s'y retrouvent pour des conférences. Le calme de l'endroit et de sa nature environnante en font un lieu propice à la concentration et au travail mathématique. De ce fait, en plus de ses conférences, le centre de recherche d'Oberwolfach organise en parallèle des programmes de « research in pairs » : un petit groupe de deux à cinq mathématiciens s'y retrouve pour quelques semaines afin de travailler sur un sujet précis. C'est ainsi qu'en 2012, Laurent Bienvenu (chargé de recherche au CNRS), Noam Greenberg (professeur à l'université de Wellington), Antonin Kučera (professeur à l'université de Prague), André Nies (professeur à l'université d'Auckland) et Dan Turetsky (post-doctorant au centre de recherche Kurt Gödel à Vienne) se retrouvent à Oberwolfach pour s'attaquer à la question de la réciproque du corollaire 3.2.

Si leurs travaux n'aboutiront pas tout de suite à la résolution de cette question-là, ils constitueront néanmoins une avancée fondamentale, via le concept qu'ils baptisèrent en l'honneur du lieu qui les accueillait : *l'aléatoire d'Oberwolfach*. Nous avons vu avec le théorème 19-1.5 que si $X$ est MLR mais non fortement MLR, alors $X$ calcule un ensemble c. e. non calculable. Nous avons vu avec le théorème 19-4.2 que si $X$ est MLR mais non aléatoire de différence, alors $X$ calcule le problème de l'arrêt. Étant donné un K-trivial c. e. $A$, l'idée est alors de rechercher une notion d'aléatoire qui se situerait entre aléatoire de différence et aléatoire de Martin-Löf fort, telle que tous les MLR qui ne sont pas aléatoires pour cette notion calculeraient forcément $A$.

### Définition 3.4 (BGKNT [15])

Un test d'Oberwolfach est donné par $\bigcap_n U_n$, une classe $\Pi_2^0$, et un réel positif approchable par la gauche $r < 1$ tels que $\lambda(U_n) \le r - r_n$, où $(r_n)_{n \in \mathbb{N}}$ est l'approximation de $r$. Un ensemble $Z$ est *aléatoire au sens d'Oberwolfach* si $Z$ n'appartient à aucun test d'Oberwolfach. ◇

La condition de convergence de la mesure des ouverts vers 0 est donc relaxée dans un test d'Oberwolfach par rapport à un test de Martin-Löf. En effet, si $r$ n'est pas calculable, alors la borne $r - r_n$ ne le sera pas non plus. Il y a malgré tout une restriction sur la convergence des ouverts vers 0, et il est de fait possible de montrer que cette notion d'aléatoire est strictement plus faible que l'aléatoire de Martin-Löf fort, pour lequel il n'y a aucune restriction. Nous verrons avec le théorème 3.7 que tout ensemble aléatoire au
sens d'Oberwolfach est aléatoire de différence. Le théorème suivant montre
que l'objectif de l'aléatoire d'Oberwolfach est rempli d'un seul coup pour
tous les K-triviaux.

**Théorème 3.5 (BGKNT [15])**

Soit Z un ensemble MLR et non aléatoire au sens d'Oberwolfach. Alors, Z
calcule tous les K-triviaux c. e.

Nous avons besoin pour montrer le théorème 3.5 d'un lemme qui au premier
abord peut sembler sibyllin, mais qui prend tout son sens quand on le place
dans le contexte des fonctions de coût, que l'on a vues avec la définition 2.4.
Le lemme suivant nous dit que pour tout réel r approchable par la gauche,
tout K-trivial c. e. admet une approximation c. e. qui satisfait la fonction
de coût calculable donnée par $c(s) = r_s - r_{s-1}$. Il s'agit bien entendu d'une
conséquence du théorème 2.6, mais que l'on peut montrer ici directement.

**Lemme 3.6 (BGKNT [15])**

Soit A un K-trivial c. e. avec une constante d. Soit $r < 1$ un réel positif approchable par la gauche avec son approximation $(r_s)_{s \in \mathbb{N}}$. Alors, il existe une approximation $(A_s)_{s \in \mathbb{N}}$ de A telle que la somme

$$
\sum_{s \in S} (r_s - r_{x_s}) \text{ est finie,}
$$

où $S = \{s \in \mathbb{N} : A_s \neq A_{s+1}\}$ et où $x_s < s$ est le plus petit entier tel
que $A_{s+1} \upharpoonright_{x_s} \neq A_s \upharpoonright_{x_s}$ \hfill \*

PREUVE. Soit la fonction

$$
f : \mathbb{N} \rightarrow \mathbb{N}, \quad f(s) = -\log_2(r_{s+1} - r_s).
$$

On a en particulier $\sum_s 2^{-f(s)} = r < 1$. D'après le théorème 16-3.1, il existe
une constante $c$ telle que $2^{-f(s)} \le 2^{-K(s)} \times 2^c$, pour tout $s$. Comme $A$ est K-
trivial avec constante $d$, on peut donc accélérer son approximation $(A_s)_{s \in \mathbb{N}}$
afin d'avoir $K(A_s \upharpoonright_t [s]) \le f(t) + c + d$, pour tout $s$ et tout $t \le s$. On a alors,
pour $s \in S$,

$$
r_s - r_{x_s} = \sum_{x_s \le t < s} 2^{-f(s)} \le \sum_{x_s \le t < s} 2^{-K(A_s \upharpoonright_t)} \times 2^{c+d}
$$

Comme A est c. e., alors si $A_s \upharpoonright_{x_s} \neq A_{s+1} \upharpoonright_{x_s}$ on a aussi $A_s \upharpoonright_{x_s} \neq A_{s'} \upharpoonright_{x_s}$, pour tout $s' > s+1$. En particulier, on a $A_s \upharpoonright_{x_s} \neq A_{s'} \upharpoonright_{x_s'}$ pour $s, s'$ distincts appartenant à S, et donc

$$
\sum_{s \in S} r_s - r_{x_s} \le \sum_{s \in S} \sum_{x_s \le t < s} 2^{-K(A_s \upharpoonright_t)} \times 2^{c+d} \le \sum_{U(\tau) \downarrow} 2^{-|\tau|} \times 2^{c+d} \le \Omega \times 2^{c+d} \le 2^{c+d}.
$$

Cela conclut la preuve.

■
PREUVE DU THÉORÈME 3.5. Soit $Z$ un ensemble MLR et capturé par un test d'Oberwolfach $\bigcap_n U_n$, avec $\lambda(U_n) \le r-r_n$ pour un réel positif $r < 1$ approachable par la gauche. Soit $A$ un K-trivial c. e. En utilisant le lemme 3.6, on peut supposer que l'énumération $(A_s)_{s \in \mathbb{N}}$ de $A$ est telle que $\sum_{s \in S} r_s - r_{x_s}$ est finie, où $S = \{s \in \mathbb{N} : A_s \ne A_{s+1}\}$ et où pour $s \in S$ l'entier $x_s$ est le plus petit tel que $A_{s+1} \rfloor_{x_s} \ne A_s \rfloor_{x_s}$. On accélère l'énumération de chaque ouvert $U_n$ de manière à avoir $\lambda(U_n[s]) \le r_s - r_n$ pour tout $s$. On définit la fonctionnelle $\Phi$ par $\Phi(X, n) = A_s(n)$, pour tout $X \in U_{n+1}[s+1] \setminus U_{n+1}[s]$. Pour voir que l'on a bien $\Phi(Z, n) = A(n)$, on définit le test de Solovay $V_s = U_{x_s}[s]$, pour tout $s \in S$. Si $s \notin S$, alors $V_s$ reste vide. Notons que l'on a $\sum_{s \in S} \lambda(V_s) = \sum_{s \in S} \lambda(U_{x_s}[s]) \le \sum_{s \in S} r_s - r_{x_s}$. Donc, $\sum_{s \in S} \lambda(V_s)$ est une quantité finie, et $(V_s)_{s \in \mathbb{N}}$ est bien un test de Solovay.

Comme $Z \in \bigcap_n U_n$, alors la fonctionnelle est bien totale sur l'oracle $Z$. Supposons que $\Phi(Z, n) \ne A(n)$ pour un entier $n$ fixé. Soit $s$ tel que

$$Z \in U_{n+1}[s+1] - U_{n+1}[s].$$

Alors, il doit exister $t > s$ tel que $A_t(n) \ne A_{t+1}(n)$. Soit $x_t \le n+1$ le plus petit tel que $A_t \rfloor_{x_t} \ne A_{t+1} \rfloor_{x_t}$. On a $V_t = U_{x_t}[t] \supseteq U_{n+1}[s+1]$, et donc $Z \in V_t$. Comme $Z$ est MLR, cela ne peut pas arriver une infinité de fois. Donc, $\Phi(Z, n) = A(n)$ pour $n$ suffisamment grand. ■

Les protagonistes de l'aléatoire d'Oberwolfach ont également montré que leur notion était la meilleure possible pour l'objectif donné : il est possible de construire un K-trivial tel que tout ensemble qui le calcule est capturé par un test d'Oberwolfach. Aucun ensemble aléatoire au sens d'Oberwolfach ne peut donc calculer tous les K-triviaux, et il existe en particulier des K-triviaux plus dégourdis que les autres, dits « K-triviaux intelligents », tels que tout aléatoire qui les calcule peut alors calculer tous les K-triviaux.

### 3.3. Résolution de la question

Nous sommes à présent proches de la résolution de la question de savoir si tout K-trivial c. e. est calculé par un aléatoire incomplet. Il s'agit de construire un ensemble qui passe tous les tests de différence — afin d'être incomplet — mais qui ne soit pas aléatoire au sens d'Oberwolfach. Une telle construction s'avère toutefois fort complexe, et n'a pu être achevée directement. La solution viendra à la place d'un détour inattendu par le théorème de densité de Lebesgue. Souvenons-nous qu'un ensemble MLR est incomplet si, et seulement si, c'est un point de densité positive dans toute classe $\Pi_1^0$ qui le contient. Bienvenu, Greenberg, Kučera, Nies et Tuřetsky ont également montré durant leur séjour à Oberwolfach que la notion d'aléatoire qu'ils y ont définie est suffisante pour satisfaire le théorème de densité de Lebesgue pour toute classe $\Pi_1^0$.
**Théorème 3.7 (BGKNT [15])**

Soit Z un ensemble aléatoire au sens d'Oberwolfach. Alors, $\underline{\rho}(\mathcal{P} | Z) = 1$ pour tout $\mathcal{P}$ classe $\Pi_1^0$ contenant Z.

PREUVE. Soit $\mathcal{P}$ une classe $\Pi_1^0$ contenant Z. Supposons $\underline{\rho}(\mathcal{P} | Z) < 1$, par l'absurde. Soit $\alpha < 1$ tel que $\underline{\rho}(\mathcal{P} | Z) < \alpha$. Soit T l'arbre calculable dont les chemins infinis sont les éléments de $\mathcal{P}$. On définit

$$U_n = \{\sigma \in T : |\sigma| \ge n \text{ et } \lambda(\mathcal{P} | [\sigma]) < \alpha\}.$$

Chaque ouvert $U_n = [U_n]$ est bien $\Sigma_1^0$, et il est clair que $Z \in \bigcap_n U_n$. Nous prétendons que $\bigcap_n U_n$ est un test d'Oberwolfach. On se doit de trouver pour cela un réel approchable par la gauche r tel que $\lambda(U_n) \le r - r_n$.

Soit $\mathcal{P}[n]$ l'approximation de $\mathcal{P}$ donnée par l'ouvert-fermé constitué des chaînes $\sigma \in T$ de taille $n$. Il est clair que l'on a $U_n \subseteq \mathcal{P}[n]$. Cherchons à présent une borne pour la mesure de $U_n \subseteq \mathcal{P}[n]$. On a

$$\lambda(\mathcal{P} \setminus U_n) \le \lambda(\mathcal{P}[n] \setminus U_n) = \lambda(\mathcal{P}[n]) - \lambda(U_n).$$

Par ailleurs, les éléments de $\mathcal{P}$ sont soit dans $U_n$, soit dans $\mathcal{P} \setminus U_n$. Par suite, $\lambda(\mathcal{P}) = \lambda(\mathcal{P} \cap U_n) + \lambda(\mathcal{P} \setminus U_n)$. De plus, si $\sigma \in U_n$, alors $\lambda(\mathcal{P} | [\sigma]) < \alpha$. On a donc $\lambda(\mathcal{P} \cap U_n) \le \alpha\lambda(U_n)$. Cela donne

$$\lambda(\mathcal{P}) = \lambda(\mathcal{P} \cap U_n) + \lambda(\mathcal{P} \setminus U_n) \le \alpha\lambda(U_n) + \lambda(\mathcal{P}[n]) - \lambda(U_n).$$

On a alors $\lambda(\mathcal{P}) - \lambda(\mathcal{P}[n]) \le (\alpha - 1)\lambda(U_n)$, et donc

$$(1 - \alpha)\lambda(U_n) \le \lambda(\mathcal{P}[n]) - \lambda(\mathcal{P}) = \lambda(\mathcal{P}^c) - \lambda(\mathcal{P}[n]^c),$$

où $\mathcal{P}^c$ et $\lambda(\mathcal{P}[n]^c)$ désignent respectivement les complémentaires des ensembles $\mathcal{P}$ et $\mathcal{P}[n]$. Ainsi,

$$\lambda(U_n) \le \frac{1}{1-\alpha} (\lambda(\mathcal{P}^c) - \lambda(\mathcal{P}[n]^c)).$$

Notre réel approchable par la gauche sera donc $r = \frac{1}{1-\alpha} \lambda(\mathcal{P}^c)$, via l'approximation $r_n = (\frac{1}{1-\alpha} \lambda(\mathcal{P}[n]^c))_{n \in \mathbb{N}}$. Il est bien entendu possible que ce réel soit plus grand que 1, auquel cas il suffit de commencer l'approximation à partir de $n$ suffisamment grand tel que $r - r_n < 1$. ■

**Corollaire 3.8**

Soit $X \in 2^\mathbb{N}$. Alors, X fortement MLR implique X aléatoire au sens d'Oberwolfach implique X différence aléatoire.

PREUVE. Il est clair que les tests d'Oberwolfach sont tous des classes $\Pi_2^0$ de mesure 0. Donc, si $X$ est fortement MLR, il est aléatoire au sens d'Oberwolfach. À présent, si $X$ est aléatoire au sens d'Oberwolfach, il est de densité 1, et donc de densité positive dans toute classe $\Pi_1^0$ de mesure positive. D'après le théorème 19-4.10, il est donc différence aléatoire. ■
Il suffirait donc pour résoudre la question de construire un aléatoire de Martin-Löf qui soit un point de densité positive dans toute classe $\Pi_1^0$, et qui ne soit pas un point de densité 1 pour au moins une classe $\Pi_1^0$, afin d'exhiber un aléatoire de Martin-Löf incomplet calculant tous les K-triviaux. C'est ce qui fut fait par Day et Miller, qui apporteront à l'aide d'un forcing approprié, un point final à la question.

### Théorème 3.9 (Day et Miller [43])

Il existe un ensemble MLR $Z \in 2^N$ tel que :

(1) $\rho(P|Z) > 0$, pour tout $P$ classe $\Pi_1^0$;

(2) $\rho(Q|Z) < 1$, pour $Q$ une classe $\Pi_1^0$ spécifique.

**PREUVE.** Soit $\mathcal{P}$ une classe $\Pi_1^0$ ne contenant que des ensembles MLR. On définit les conditions de forcing $\mathbb{P}$ par $\langle\sigma, Q\rangle \in \mathbb{P}$ si :

(1) $\sigma \in 2^{<N}$;

(2) $Q \subseteq \mathcal{P}$ est une classe $\Pi_1^0$;

(3) $[\sigma] \cap Q \neq \emptyset$ (et donc $\lambda(Q|[\sigma]) > 0$, car $Q$ ne contient que des MLR);

(4) Il existe $\delta < 1/2$ tel que pour tous $\tau \succeq \sigma$, si $[\tau] \cap Q$ est non vide, alors $\lambda(P|[\tau]) \leq \lambda(Q|[\tau]) + \delta$.

On dit que $\langle\tau, \mathcal{R}\rangle$ étend $\langle\sigma, Q\rangle$ si $\tau \succeq \sigma$ et $\mathcal{R} \subseteq Q$. Notons que $(\epsilon, \mathcal{P})$, où $\epsilon$ est la chaîne vide, est une condition avec $\delta = 0$. De même, si $(\sigma, Q)$ est une condition satisfaisant (4) pour un $\delta$, alors pour tout $\tau \succeq \sigma$ tel que $[\tau] \cap Q \neq \emptyset$, l'extension $(\tau, Q)$ de $(\sigma, Q)$ satisfait (4) pour le même $\delta$. Ainsi, tout filtre suffisamment générique contiendra des conditions $(\sigma, Q)$, avec $|\sigma|$ de longueur arbitraire.

Soit $G \subseteq \mathbb{P}$ un filtre suffisamment générique. Soit $X_G$ l'unique point limite des $\sigma_i$ pour $\langle\sigma_i, Q_i\rangle \in G$. Comme $\mathcal{P}$ est une classe fermée, il est clair que $X_G \in \mathcal{P}$, et donc $X_G$ est un ensemble MLR.

Montrons à présent que si l'ensemble $G$ est suffisamment générique, on a alors $\rho(P|X_G) < 1/2$. Soit $\langle\sigma, Q\rangle$ une condition de forcing avec $\delta$ satisfaisant la condition (4). Soit $X$ le chemin le plus à gauche de $Q \cap [\sigma]$. La classe $Q \cap [\sigma] \subseteq \mathcal{P}$ est une classe ne contenant que des ensembles MLR, si bien que $X$ est un ensemble MLR. D'après l'exercice 18-1.3, les ensembles MLR contiennent des suites de 1 arbitrairement grandes. Soit $m$ tel que $2^{-m} + \delta < 1/2$, et soit $\tau$ tel que $\sigma < \tau 1^m < X$. Comme $X$ est le chemin le plus à gauche de $Q \cap [\sigma]$, on a $\lambda(Q|[\tau]) \leq 2^{-m}$, et par conséquent $\lambda(P|[\tau]) \leq 2^{-m} + \delta \leq 1/2$. La condition de forcing $\langle\tau, Q\rangle$ étend bien $\langle\sigma, Q\rangle$. Dès lors, si le filtre $G$ est suffisamment générique, on aura $\lambda(P|X_G \upharpoonright_m) < 1/2$ pour une infinité d'entiers $m$, et donc $\rho(P|X_G) < 1/2$.
Montrons finalement que si $G$ est suffisamment générique, alors pour toute $S$ classe $\Pi_1^0$ on a $X_G \in S$ implique $\rho(S | X_G) > 0$. Soit $\langle \sigma, Q \rangle$ une condition de forcing, avec $\delta$ satisfaisant la condition (4). S'il existe $\tau \succeq \sigma$ telle que $Q \cap [\tau] \neq \emptyset$ et telle que $S \cap [\tau] = \emptyset$, on prend $\langle \tau, Q \rangle$ comme extension de forcing, et l'on aura alors $X_G \notin S$. Sinon, cela signifie $[\sigma] \cap Q \subseteq S$. Soit $\varepsilon < \min(1/2 - \delta, \lambda(Q | [\sigma]))$. Considérons la classe

$$Q' = \{ X \in Q \cap [\sigma] : \forall n \ge |\sigma| \lambda(Q | [X \upharpoonright_n]) \ge \varepsilon \}.$$

Il est clair que $\rho(Q | X) \ge \varepsilon$, pour tout $X \in Q'$. Comme $[\sigma] \cap Q \subseteq S$, alors également $\rho(S | X) \ge \varepsilon$, pour tout $X \in Q'$. Il nous reste dès lors à montrer que $\langle Q', \sigma \rangle$ est une extension valide, pour laquelle on aura par conséquent $\rho(S | X_G) \ge \varepsilon$.

Montrons d'abord que la classe $Q' \cap [\sigma]$ est non vide. Par le choix de $\varepsilon$, on a $\lambda(Q | [\sigma]) \ge \varepsilon$. Il doit donc exister d'après le lemme 19-4.7 une suite infinie $Y > \sigma$, avec $Y \in Q$ telle que $\lambda(Q | [Y \upharpoonright_n]) \ge \varepsilon$ pour tout $n \ge |\sigma|$. Donc, $Q' \cap [\sigma]$ est non vide. Soit à présent une chaîne $\tau \succeq \sigma$ telle que $Q' \cap [\tau]$ est non vide. Montrons que l'on a alors $\lambda(P | [\tau]) \le \lambda(Q' | [\tau]) + \delta + \varepsilon$ faisant de $\delta + \varepsilon < 1/2$ le rationnel satisfaisant la condition (4). Soit

$$\mathcal{U} = \{ X \succeq \sigma : \exists n \lambda(Q | [X \upharpoonright_n]) < \varepsilon \}.$$

Comme $Q' \cap [\tau]$ est non vide, on a $\lambda(Q | [\tau \upharpoonright_n]) \ge \varepsilon$, pour tout entier $n$ avec $|\sigma| < n \le |\tau|$, et donc $[\tau] \not\subseteq \mathcal{U}$. Soit $W$ l'ensemble minimal de chaînes sans préfixes décrivant $\mathcal{U}$. Comme $[\tau] \not\subseteq \mathcal{U}$, on a alors

$$\lambda(Q \cap \mathcal{U} \cap [\tau]) = \sum_{\rho \in W, \rho > \tau} \lambda(Q \cap [\rho]).$$

Par ailleurs, pour toute chaîne $\rho \in W$ on a $\lambda(Q | [\rho]) < \varepsilon$ par définition de $\mathcal{U}$. Donc,

$$\lambda(Q \cap \mathcal{U} \cap [\tau]) \le \varepsilon \sum_{\rho \in W, \rho > \tau} 2^{-|\rho|} \le \varepsilon 2^{-|\tau|}.$$

Comme on a $Q' \cap [\tau] = Q \cap [\tau] \setminus (Q \cap \mathcal{U} \cap [\tau])$, alors

$$\lambda(Q' \cap [\tau]) = \lambda(Q \cap [\tau]) - \lambda(Q \cap \mathcal{U} \cap [\tau]),$$

et donc $\lambda(Q' \cap [\tau]) \ge \lambda(Q \cap [\tau]) - \varepsilon 2^{-|\tau|}$. Ainsi, $\lambda(Q' | [\tau]) \ge \lambda(Q | [\tau]) - \varepsilon$. Comme $Q' \cap [\tau]$ est non vide, alors aussi $Q \cap [\tau]$ est non vide, et l'on a donc $\lambda(P | [\tau]) \le \lambda(Q | [\tau]) + \delta \le \lambda(Q' | [\tau]) + \delta + \varepsilon$. Donc, $\langle \sigma, Q' \rangle$ est une condition valide pour $\delta + \varepsilon < 1/2$. ■

### Corollaire 3.10 (BDGKMNT [13])

Tout ensemble K-trivial c. e. est calculable par un MLR incomplet.

**PREUVE.** Il suffit, d'après le théorème 3.9, de considérer un MLR $Z$ qui est un point de densité inférieure positive sans être un point de densité
inférieur 1. D'après le théorème 19-4.10, un tel ensemble ne peut pas calculer $\emptyset'$. D'après le théorème 3.7, un tel ensemble ne peut pas être aléatoire au sens d'Oberwolfach, car il serait sinon un point de densité inférieure 1. D'après le théorème 3.5, cet ensemble Z calcule donc tous les K-triviaux c. e. ■

# 4. Une nouvelle preuve de K-trivial implique low-pour-K

Nous montrons à présent comment combiner les résultats vus jusqu'ici pour montrer que tout K-trivial c. e. est low-pour-K, sans utiliser la preuve du processus d'or. Soit A un ensemble c. e. K-trivial. Alors, d'après le corol- laire 3.10, A est calculé par un MLR incomplet Z. Supposons par l'ab- surde que Z n'est pas MLR(A). Alors, d'après la proposition 3.1, on doit avoir $A \oplus Z \geq \emptyset'$, et donc $Z \geq \emptyset'$, ce qui contredit le fait que Z soit incom- plet. Ainsi, Z est MLR(A), et A est une base pour l'aléatoire. D'après le théorème 1.7, A est donc low-pour-K.

Il ne nous reste plus qu'à montrer que tout K-trivial est calculé par un K- trivial c. e., et ce sans utiliser non plus la preuve du processus d'or. Comme tout K-trivial c. e. est low-pour-K et que les low-pour-K sont clos par le bas dans les degrés Turing, on en déduit facilement que tout K-trivial est aussi low-pour-K. Nous faisons appel pour cela à une utilisation astucieuse d'un concept introduit par Solovay : des fonctions de compressions calculables qui font aussi bien que $K$ infiniment souvent.

**Définition 4.1.** Une fonction de Solovay est une fonction $g : \mathbb{N} \to \mathbb{N}$ calculable telle que $K(n) \leq^+ g(n)$ pour tout $n$, et telle que $g(n) \leq^+ K(n)$ pour une infinité d'entiers $n$. ◇

**Proposition 4.2.** Il existe une fonction de Solovay. ★

**PREUVE.** Soit $g_S : \mathbb{N} \to \mathbb{N}$ telle que $g_S(\langle\sigma, n, t\rangle) = |\sigma|$ si $t$ est le plus petit temps de calcul tel que $U(\sigma)[t] \downarrow= n$. Sinon, $g_S(\langle\sigma, n, t\rangle) = 2\langle\sigma, n, t\rangle$. Comme $K(\langle\sigma, n, t\rangle) \leq^+ 2\langle\sigma, n, t\rangle$, on a bien $K(n) \leq^+ g_S(n)$ pour tout $n$. Montrons que l'on a $K(n) =^+ g_S(n)$ pour une infinité d'entiers $n$.

Soit $M$ la machine sans préfixe qui sur $\sigma$ tel que $t$ est le plus petit pour le- quel $U(\sigma)[t] \downarrow= n$, renvoie $\langle\sigma, n, t\rangle$. Via $M$, on a $K(\langle\sigma, n, t\rangle) \leq^+ |\sigma|$. Comme on peut calculer $n$ à partir de $\langle\sigma, n, t\rangle$, on a également $K(n) \leq^+ K(\langle\sigma, n, t\rangle)$. Enfin, si $\sigma$ est la plus petite chaîne telle que $U(\sigma) \downarrow= n$, on a par défini- tion $|\sigma| = K(n)$.

On a donc dans ce cas $|\sigma| = K(n) \leq^+ K(\langle\sigma, n, t\rangle) \leq^+ |\sigma|$, d'où il résulte que $g_S(\langle\sigma, n, t\rangle) =^+ K(\langle\sigma, n, t\rangle)$. ■
Bienvenu et Downey ont montré que la fonction définie par Solovay pouvait être utilisée pour caractériser la K-trivialité.

**Proposition 4.3 (Bienvenu et Downey, [14]).** Soit $g_S$ la fonction de Solovay de la proposition 4.2. Si $K(A \upharpoonright_n) \le g_S(n) + c$ pour tout $n$, alors $A$ est K-trivial via une certaine constante $c+d$. $\star$

**PREUVE.** Pour tout $n$, soit $\sigma_n$ la plus petite chaîne telle que $U(\sigma_n)=n$, et soit $t_n$ le plus petit temps de calcul tel que $U(\sigma_n)[t_n] = n$. On a

$$K(A \upharpoonright_{\langle \sigma_n, n, t_n \rangle}) \le g_S(\langle \sigma_n, n, t_n \rangle) + c = |\sigma_n| + c = K(n) + c.$$

Comme on peut calculer $A \upharpoonright_n$ à partir de $A \upharpoonright_{\langle \sigma_n, n, t_n \rangle}$, on a une constante $d$ telle que $K(A \upharpoonright_n) \le K(A \upharpoonright_{\langle \sigma_n, n, t_n \rangle}) + d$, et donc telle que $K(A \upharpoonright_n) \le K(n) + d$.

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

Plus tard, Bienvenu, Merkle et Nies [20] montreront que la proposition précédente fonctionne pour toutes les fonctions de Solovay, mais il s'agit d'une preuve bien plus difficile. Nous avons à présent tous les ingrédients nécessaires pour montrer que tout K-trivial est borné dans les degrés Turing par un K-trivial c. e., résultat qui fut démontré d'abord par Nies à partir de la technique des fonctions de coût et de la preuve du *processus d'or*, et qui peut se montrer à présent de manière complètement différente.

**Théorème 4.4 (Nies [166])**

*Tout K-trivial est calculé par un K-trivial c. e.*

**PREUVE.** Soit $g_S : \mathbb{N} \to \mathbb{N}$ la fonction de Solovay de la proposition 4.2. Soit $T = \{\sigma \in 2^{<\mathbb{N}} : \forall n < |\sigma| K(X \upharpoonright_n) \le g_S(n) + c\}$ l'arbre c. e. qui représente la classe $\Pi_1^0(\emptyset')$ de l'ensemble $\{X : K(X \upharpoonright_n) \le g_S(n) + c\}$. Il est clair que $[T]$ contient tous les K-triviaux avec constante $c$, et d'après la proposition 4.3 $[T]$ ne contient que des K-triviaux avec constante $c+d$, et donc en particulier ne contient qu'un nombre fini d'éléments. Soit $A$ l'un de ces K-triviaux, et soit $\sigma \prec A$ tel que $A$ et le seul chemin infini de $T$ qui étend $\sigma$. Soit $T \upharpoonright_{\sigma}$ l'arbre $T$ restreint aux chaînes comparables avec $\sigma$. On modifie l'énumération de $T \upharpoonright_{\sigma}$ de la manière suivante : étant donné $T_s \upharpoonright_{\sigma}$ à l'étape $s$, on énumère dans $T_s \upharpoonright_{\sigma}$ une nouvelle chaîne $\tau \succeq \sigma$ uniquement si celle-ci est de taille supérieure ou égale à toutes les chaînes actuellement dans $T_s \upharpoonright_{\sigma}$ —auquel cas on énumère également tous les préfixes de $\tau$ dans $T_s \upharpoonright_{\sigma}$. Soit $T_{\sigma}$ l'arbre c. e. résultant de cette énumération.

Notons que comme $T$ contient des extensions de $\sigma$ de taille arbitrairement grande, alors notre nouvelle énumération $T_{\sigma}$ contient de même des extensions de $\sigma$ de taille arbitrairement grande. En particulier, par le lemme de König, $T_{\sigma}$ contient un chemin infini. Comme $A$ est l'unique chemin infini de $T$ qui étend $\sigma$, ce chemin infini est dès lors forcément $A$. Comme $A$ est l'unique chemin infini de $T_{\sigma}$, alors $T_{\sigma}$ permet de calculer $A$.
Montrons que $T_\sigma$ est K-trivial via sa représentation $X_\sigma$ où $X_\sigma(n) = 1$ si, et seulement si, $n$ correspond à une chaîne énumérée dans $T_\sigma$. Notons que $X_\sigma \upharpoonright_2 n$ correspond à toutes les chaînes de $T_\sigma$ de taille inférieure ou égale à $n$. Montrons $K(X_\sigma \upharpoonright_2 n) \leq^+ g_S(n)$ pour tout $n$. Pour tout $n$, soit $\sigma_n$ la dernière chaîne de taille égale à $n$ qui est énumérée dans $T$.

Notons que $\sigma_n$ permet de calculer uniformément $X_\sigma \upharpoonright_2 n$: il suffit d'attendre que $\sigma_n$ soit énumérée dans $T_\sigma$, et de renvoyer alors l'ensemble des chaînes de taille inférieure ou égale à $|\sigma_n|$ énumérées dans $T_\sigma$ jusqu'ici. Par la propriété d'énumération de $T_\sigma$, on sait qu'aucune autre chaîne de taille inférieure ou égale à $n$ ne sera énumérée par la suite. Comme $\sigma_n \in T$, par définition de $T$, $K(\sigma_n) \leq g_S(n) + c$. Enfin, comme $X_\sigma \upharpoonright_n$ est calculable à partir de $X_\sigma \upharpoonright_2 n$, on a $K(X_\sigma \upharpoonright_n) \leq^+ K(X_\sigma \upharpoonright_2 n)$. Cela nous donne

$$K(X_{\sigma} \upharpoonright_{n}) \leq^{+} K(X_{\sigma} \upharpoonright_{2^{n}}) \leq^{+} K(\sigma_{n}) \leq^{+} g_{S}(n),$$

pour tout $n$. Donc, $X_\sigma$ est K-trivial. ■

## Schéma Récapitulatif

Voici un tableau qui récapitule les différentes notions d'aléatoire abordées jusqu'ici.

<table><thead><tr><td>Aléatoire</td><td>Tests</td><td>Caractérisation</td><td>Densité dans les Π<sup>0</sup><sub>1</sub> le contenant</td></tr></thead><tbody><tr><td>Fortement MLR</td><td>Π<sup>0</sup><sub>2</sub> de mesure 0</td><td>MLR et ne calcule aucun Δ<sup>0</sup><sub>2</sub> non calculable.</td><td></td></tr><tr><td>Aléatoire d'Oberwolfach</td><td>∩<sub>n</sub> U<sub>n</sub> tel que λ(U<sub>n</sub>) &lt; r - r<sub>n</sub>, avec lim<sub>n</sub> r<sub>n</sub> = r</td><td>MLR et ne calcule pas tous les K-triviaux c. e.</td><td>densité inférieure 1</td></tr><tr><td>Aléatoire de différence</td><td>F ∩ ∩<sub>n</sub> U<sub>n</sub> tel que λ(U<sub>n</sub> ∩ F) ≤ 2<sup>-n</sup></td><td>MLR incomplet</td><td>densité inférieure positive</td></tr><tr><td>MLR</td><td>∩<sub>n</sub> U<sub>n</sub> tel que λ(U<sub>n</sub>) &lt; 2<sup>-n</sup></td><td></td><td>densité supérieure 1</td></tr></tbody></table>
Troisième partie

Mathématiques à rebours
<figure><img src="image_133.png" /></figure>