# Calculabilité

Ludovic Patey

► To cite this version:

Ludovic Patey. Calculabilité. Calvage & Mounet. Calvage & Mounet, 2022, 978-2-91-635296-1.
hal-05476567

HAL Id: hal-05476567

https://hal.science/hal-05476567v1

Submitted on 26 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
<figure><img src="image_2.png" /></figure>

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

calculabilité

DEGRÉS TURING ←

THÉORIE ALGORITHMIQUE DE L'ALÉATOIRE ←

MATHÉMATIQUES À REBOURS ←

HYPERCALCULABILITÉ ←

Benoît Monin
Ludovic Patey
<figure><img src="image_4.png" /></figure>
<figure><img src="image_5.png" /></figure>
TABLEAU NOIR
Tableau Noir

101. — Rached Mneimné. *Réduction des endomorphismes*

102. — Marc Hindry. *Arithmétique*

103. — Jean-Denis Eiden. *Géométrie analytique classique*

104. — Denis Choimet et Hervé Queffélec. *Analyse mathématique. – Grands théorèmes du vingtième siècle*

105. — Pascal Boyer. *Algèbre et géométries*

106. — Patrick Dehornoy. *La théorie des ensembles*

107. — Benoît Monin et Ludovic Patey. *Calculabilité*

108. — Gilles Godefroy. *Introduction aux méthodes de Baire* (à paraître)
# Calculabilité

Aléatoire, mathématiques à rebours
et hypercalculabilité

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

<figure><img src="image_7.png" /></figure>
BENOÎT MONIN est maître de conférences à l'université de Créteil. Ses travaux portent sur la calculabilité classique, l'aléatoire algorithmique et l'hypercalculabilité.

benoit.monin@computability.fr
https://www.lacl.fr/%7Ebenoit.monin/

LUDOVIC PATEY est chargé de recherche à l'université de Paris. Ses travaux portent sur la calculabilité classique et les mathématiques à rebours.

ludovic.patey@computability.fr
https://ludovicpatey.com/

Mathematics Subject Classification (2010) – Primary :

03-Dxx Computability and recursion theory

03D30 Other degrees and reducibilities in computability and recursion theory

03D60 Computability and recursion theory on ordinals, admissible sets, etc.

03D80 Applications of computability and recursion theory

03D10 Turing machines and related notions

03D20 Recursive functions and relations, subrecursive hierarchies

03D25 Recursively (computably) enumerable sets and degrees

03D32 Algorithmic randomness and dimension

03D55 Hierarchies of computability and definability

03D78 Computation over the reals, computable analysis

03B30 Foundations of classical theories (including reverse mathematics)

68-Qxx Theory of computing

68Q05 Models of computation (Turing machines, etc.)

68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)

03B10 Classical first-order logic

03C07 Basic properties of first-order languages and structures

03F35 Second- and higher-order arithmetic and fragments

03F40 Gödel numberings and issues of incompleteness

03F60 Constructive and recursive analysis

⊗ Imprimé sur papier permanent

© Calvage & Mounet, Paris, 2022

ISBN 978-2-91-635296-1

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

9 782916 352961
à nos familles
<figure><img src="image_9.png" /></figure>
# Table des matières

## Préambule

## Remerciements

### 1. Introduction

<table><tr><td>1-1. Qu'est-ce qu'une fonction calculable?</td><td>4</td></tr><tr><td>1-2. Quelles sont les fonctions incalculables?</td><td>5</td></tr><tr><td>1-3. Motivations</td><td>6</td></tr><tr><td>1-4. Panorama de la calculabilité</td><td>7</td></tr></table>

### 2. Infinis de Cantor

<table><tr><td>2-1. Équipotence et subpotence</td><td>15</td></tr><tr><td>2-2. Théorème de Cantor-Bernstein</td><td>16</td></tr><tr><td>2-3. Ensembles dénombrables</td><td>18</td></tr><tr><td>2-4. Argument diagonal de Cantor</td><td>21</td></tr><tr><td>2-5. Réels non calculables</td><td>23</td></tr><tr><td>2-6. Espace de Cantor</td><td>24</td></tr></table>

## I Calculabilité classique 29

### 3. Fondements de la calculabilité

<table><tr><td>3-1. Fonctions calculables</td><td>31</td></tr><tr><td>3-2. Ensembles calculables</td><td>36</td></tr><tr><td>3-3. Programme universel</td><td>37</td></tr><tr><td>3-4. Théorème SMN</td><td>38</td></tr><tr><td>3-5. Lemme de remplissage</td><td>40</td></tr><tr><td>3-6. Théorème du point fixe de Kleene</td><td>41</td></tr><tr><td>3-7. Ensembles calculatoirement énumérables</td><td>44</td></tr></table>
## 4. Degrés Turing

<table><tr><td>4-1. Les chaînes finies</td><td>51</td></tr><tr><td>4-2. Calcul avec oracle</td><td>52</td></tr><tr><td>4-3. Relativisation des preuves</td><td>54</td></tr><tr><td>4-4. Propriété de l'usage</td><td>56</td></tr><tr><td>4-5. Degrés Turing</td><td>57</td></tr><tr><td>4-6. Saut Turing</td><td>60</td></tr><tr><td>4-7. Calculabilité à la limite</td><td>61</td></tr><tr><td>4-8. Méthode des extensions finies</td><td>66</td></tr><tr><td>4-9. Degrés low</td><td>71</td></tr><tr><td>4-10. Degrés high</td><td>74</td></tr></table>

## 5. Hiérarchie arithmétique

<table><tr><td>5-1. Propriétés élémentaires</td><td>82</td></tr><tr><td>5-2. Hiérarchie arithmétique et calculabilité</td><td>87</td></tr><tr><td>5-3. Relativisation à un oracle</td><td>88</td></tr><tr><td>5-4. Degrés many-one</td><td>89</td></tr><tr><td>5-5. Théorème de Post</td><td>91</td></tr><tr><td>5-6. Théorème de Rice</td><td>93</td></tr><tr><td>5-7. Codes arithmétiques</td><td>94</td></tr></table>

## 6. La thèse de Church-Turing

<table><tr><td>6-1. L'Entscheidungsproblem et la quête du Graal</td><td>99</td></tr><tr><td>6-2. Thèse de Church-Turing</td><td>104</td></tr><tr><td>6-3. Étude détaillée des fonctions récursives</td><td>107</td></tr></table>

## 7. Immunité et croissance de fonction

<table><tr><td>7-1. Ensembles immunes</td><td>130</td></tr><tr><td>7-2. Fonctions DNC</td><td>132</td></tr><tr><td>7-3. Critère de complétude d'Arslanov</td><td>136</td></tr><tr><td>7-4. Fonctions hyperimmunes</td><td>138</td></tr><tr><td>7-5. Degrés calculatoirement dominés</td><td>140</td></tr><tr><td>7-6. Théorème de domination de Martin</td><td>147</td></tr><tr><td>7-7. Degrés High ou DNC</td><td>151</td></tr></table>

## 8. Classes $\Pi_1^0$ et degrés PA

<table><tr><td>8-1. Arbres binaires</td><td>154</td></tr><tr><td>8-2. Topologie sur l'espace de Cantor</td><td>158</td></tr><tr><td>8-3. Classes $\Pi_1^0$</td><td>165</td></tr><tr><td>8-4. Théorèmes de base</td><td>168</td></tr><tr><td>8-5. Bases pour les classes $\Pi_1^0$ parfaites</td><td>172</td></tr><tr><td>8-6. Degrés PA</td><td>174</td></tr><tr><td>8-7. Arbres à branchement fini</td><td>179</td></tr></table>
## 9. Interlude formel

9-1. Un peu d'histoire : la crise des fondements 189

9-2. La logique du premier ordre 195

9-3. Théorèmes d'incomplétudes de Gödel 212

9-4. Système ZFC 223

## 10. Forcing de Cohen

10-1. Formules de l'arithmétique du second ordre 232

10-2. Forcing $\Sigma_1^0/\Pi_1^0$ 234

10-3. Généricité effective 243

10-4. Forcing $\Sigma_n^0/\Pi_n^0$ 258

10-5. Ensembles arbitrairement génériques 266

## 11. Forcing effectif

11-1. Fondements du forcing 273

11-2. Relation de forcing 276

11-3. Forcing avec des arbres 279

11-4. Complexité calculatoire et question de forcing 283

## 12. La quête de degrés naturels

12-1. Trois problèmes indécidables emblématiques 298

12-2. Approche pour la naturalité des degrés Turing 301

12-3. Problèmes de masse 305

## 13. Méthode de priorité et degrés c. e.

13-1. Degrés c. e. 310

13-2. Méthode de permission 311

13-3. Méthode de priorité $\Sigma_1^0$ (à blessure finie) 312

13-4. Méthode de priorité $\Sigma_2^0$ 320

13-5. Méthode de priorité $\Pi_2^0$ (à blessure infinie) 323

## 14. Structure des degrés Turing

14-1. Degrés minimaux 336

14-2. Nature de $D$ 342

14-3. Universalité de $D$ 347

14-4. Théorie du premier ordre de $D$ 352

14-5. Structure des degrés c. e. 360

# II Aléatoire algorithmique

363

## 15. Introduction
## 16. Complexité de Kolmogorov et nombres aléatoires

<table><tr><td>16-1. Complexité de Kolmogorov</td><td>370</td></tr><tr><td>16-2. Nombres aléatoires à la Chaitin/Levin</td><td>379</td></tr><tr><td>16-3. Caractérisation de K</td><td>385</td></tr><tr><td>16-4. Ensembles K-triviaux</td><td>389</td></tr></table>

## 17. Boréliens, mesure et calculabilité

<table><tr><td>17-1. Un peu d'histoire</td><td>395</td></tr><tr><td>17-2. Premières intuitions sur la mesure</td><td>399</td></tr><tr><td>17-3. Classes boréliennes</td><td>402</td></tr><tr><td>17-4. Mesure de Lebesgue</td><td>407</td></tr></table>

## 18. Aléatoire au sens de Martin-Löf

<table><tr><td>18-1. Intuitions et définitions</td><td>415</td></tr><tr><td>18-2. Les aléatoires de Martin-Löf et de Chaitin/Levin coincident</td><td>418</td></tr><tr><td>18-3. Aléatoire et degré Turing</td><td>419</td></tr><tr><td>18-4. Aléatoire et degré DNC</td><td>423</td></tr></table>

## 19. Autres notions d'aléatoire

<table><tr><td>19-1. Les fortement MLR</td><td>427</td></tr><tr><td>19-2. Relativisation de l'aléatoire</td><td>432</td></tr><tr><td>19-3. Les 2-aléatoires</td><td>436</td></tr><tr><td>19-4. Aléatoires incomplets</td><td>439</td></tr></table>

## 20. Les K-triviaux

<table><tr><td>20-1. Lowness et bases pour l'aléatoire</td><td>445</td></tr><tr><td>20-2. Le processus d'or</td><td>450</td></tr><tr><td>20-3. Caractérisation des K-triviaux c. e.</td><td>462</td></tr><tr><td>20-4. Une nouvelle preuve de K-trivial implique low-pour-K</td><td>470</td></tr></table>

# III Mathématiques à rebours 473

## 21. Introduction

<table><tr><td>21-1. Quête des axiomes optimaux</td><td>475</td></tr><tr><td>21-2. Comparaison des théorèmes</td><td>479</td></tr></table>

## 22. Arithmétique du second ordre

<table><tr><td>22-1. Langage de Z<sub>2</sub></td><td>482</td></tr><tr><td>22-2. La théorie Z<sub>2</sub></td><td>484</td></tr><tr><td>22-3. Sémantiques de l'arithmétique du second ordre</td><td>486</td></tr><tr><td>22-4. Formaliser l'analyse dans Z<sub>2</sub></td><td>491</td></tr><tr><td>22-5. RCA<sub>0</sub> ou les mathématiques calculables</td><td>495</td></tr><tr><td>22-6. ACA<sub>0</sub> et la hiérarchie arithmétique</td><td>501</td></tr></table>
<table><tr><td>22-7. WKL<sub>0</sub> et l'argument de compacité</td><td>505</td></tr><tr><td>22-8. Systèmes plus puissants</td><td>511</td></tr></table>

## 23. Induction et conservation

<table><tr><td>23-1. Fonctions RCA<sub>0</sub>-prouvablement calculables</td><td>520</td></tr><tr><td>23-2. Sous-systèmes faibles de PA</td><td>522</td></tr><tr><td>23-3. Hiérarchies d'induction</td><td>528</td></tr><tr><td>23-4. Fonctions primitives récursives et RCA<sub>0</sub></td><td>535</td></tr><tr><td>23-5. Le schéma de compréhension bornée</td><td>539</td></tr><tr><td>23-6. Théorèmes de conservation</td><td>542</td></tr><tr><td>23-7. Programme de Hilbert</td><td>553</td></tr></table>

## 24. Réductions calculatoires

<table><tr><td>24-1. ω-réduction</td><td>560</td></tr><tr><td>24-2. Réduction calculatoire</td><td>565</td></tr><tr><td>24-3. Réduction Weihrauch</td><td>567</td></tr><tr><td>24-4. Jeux de réduction</td><td>571</td></tr><tr><td>24-5. Réductions fortes</td><td>573</td></tr></table>

## 25. Théorème de Ramsey

<table><tr><td>25-1. Aperçu général</td><td>578</td></tr><tr><td>25-2. Théorème de Ramsey dans la hiérarchie arithmétique</td><td>581</td></tr><tr><td>25-3. Principe infini des tiroirs</td><td>593</td></tr><tr><td>25-4. Théorème de Ramsey pour les paires</td><td>612</td></tr></table>

# IV Hypercalculabilité 625

## 26. Introduction

<table><tr><td>26-1. Motivations</td><td>628</td></tr><tr><td>26-2. Panorama de l'hypercalculabilité</td><td>630</td></tr><tr><td>26-3. Correspondance avec la calculabilité classique</td><td>631</td></tr></table>

## 27. Nombres transfinis

<table><tr><td>27-1. Motivation : itérations calculables du saut</td><td>635</td></tr><tr><td>27-2. Ordinaux</td><td>639</td></tr><tr><td>27-3. Induction et récurrence transfinie</td><td>647</td></tr><tr><td>27-4. Ordinaux dénombrables et indénombrables</td><td>653</td></tr><tr><td>27-5. Ordinaux effectifs</td><td>657</td></tr><tr><td>27-6. Relativisation</td><td>664</td></tr></table>
## 28. Ensembles hyperarithmétiques

<table><tr><td>28-1. Hiérarchie de Kleene</td><td>667</td></tr><tr><td>28-2. Les singleton Π<sup>0</sup><sub>2</sub></td><td>675</td></tr><tr><td>28-3. Relativisation</td><td>677</td></tr><tr><td>28-4. Hiérarchie borélienne effective</td><td>678</td></tr></table>

## 29. Au delà des hyperarithmétiques

<table><tr><td>29-1. Un peu d'histoire : l'école de Moscou</td><td>683</td></tr><tr><td>29-2. Quantifications du second ordre</td><td>688</td></tr><tr><td>29-3. Les Π<sup>1</sup><sub>1</sub> et les bons ordres</td><td>693</td></tr><tr><td>29-4. Analogies entre ensembles Π<sup>1</sup><sub>1</sub> et ensembles c. e.</td><td>697</td></tr><tr><td>29-5. Théorème d'équivalence de Kleene/Souslin</td><td>700</td></tr><tr><td>29-6. Autres théorèmes de majoration</td><td>707</td></tr><tr><td>29-7. Réduction hyperarithmétique</td><td>709</td></tr></table>

## 30. Classes Σ<sup>1</sup><sub>1</sub> et Π<sup>1</sup><sub>1</sub>

<table><tr><td>30-1. Représentation canonique des classes Σ<sup>1</sup><sub>1</sub></td><td>711</td></tr><tr><td>30-2. Théorèmes de base pour les classes Σ<sup>1</sup><sub>1</sub></td><td>713</td></tr><tr><td>30-3. L'hypothèse du continu pour les classes Σ<sup>1</sup><sub>1</sub></td><td>717</td></tr><tr><td>30-4. Quelques classes Π<sup>1</sup><sub>1</sub> emblématiques</td><td>720</td></tr><tr><td>30-5. Étude d'une classe Π<sup>1</sup><sub>1</sub> très spéciale</td><td>723</td></tr><tr><td>30-6. Les singleton Π<sup>1</sup><sub>1</sub></td><td>728</td></tr></table>

## 31. Les systèmes ATR<sub>0</sub> et Π<sup>1</sup><sub>1</sub>-CA<sub>0</sub>

<table><tr><td>31-1. Définitions</td><td>733</td></tr><tr><td>31-2. ATR<sub>0</sub> et Π<sup>1</sup><sub>1</sub>-CA<sub>0</sub> en hypercalculabilité</td><td>736</td></tr><tr><td>31-3. HYP n'est pas modèle de ATR<sub>0</sub></td><td>737</td></tr><tr><td>31-4. Codes d'ordinaux non standard</td><td>741</td></tr><tr><td>31-5. Séparation entre ATR<sub>0</sub> et Π<sup>1</sup><sub>1</sub>-CA<sub>0</sub></td><td>747</td></tr></table>

## A. Correction des exercices

<table><tr><td>Bibliographie</td><td>797</td></tr><tr><td>Notations</td><td>813</td></tr><tr><td>Index</td><td>819</td></tr></table>
# Préambule

Ce livre est une introduction à la théorie de la calculabilité ainsi qu’à trois de ses ramifications principales, à savoir la théorie algorithmique de l’aléatoire, les mathématiques à rebours et l’hypercalculabilité. Il s’agit d’un ouvrage principalement destiné aux étudiants et enseignants en master de recherche en informatique et mathématiques, ainsi qu’aux chercheurs désirant acquérir une solide connaissance en calculabilité.

## Raison d’être du livre

Cet ouvrage trouve ses origines dans plusieurs constats.

► La littérature francophone sur la calculabilité classique est quasiment inexistante. Il existe quelques introductions à la calculabilité en français qui s’intègrent dans le cadre d’une présentation de la théorie de la complexité, comme l’excellent ouvrage d’Olivier Carton *Langages formels, calculabilité, et complexité* [28]. Les modèles de calcul sont alors présentés comme une base solide pour développer une théorie de la complexité algorithmique. Les résultats de calculabilité à proprement parler dépassent rarement l’indécidabilité du problème de l’arrêt et la définition de la hiérarchie arithmétique.

► Il existe de nombreux livres de référence en anglais sur la calculabilité (Classical Recursion Theory : The Theory of Functions and Sets of Natural Numbers de Piergiorgio Odifreddi [169], Computability Theory de Barry Cooper [41] ou encore Turing computability : Theory and Applications de Robert Soare [208]). Concernant la théorie algorithmique de l’aléatoire, on citera Computability and Randomness d’André Nies [167], et Algorithmic Randomness and Complexity de Rodney
Downey et Denis Hirschfeldt [50]. En mathématiques à rebours, la référence historique est *Subsystems of Second Order Arithmetic* de Stephen Simpson [203]. On mentionnera l'ouvrage plus récent de Denis Hirschfeldt, *Slicing the Truth* [87], et l'ouvrage en cours de rédaction, *Reverse Mathematics* de Damir Dzhafarov et Carl Mummert. Enfin, en hypercalculabilité, les deux références sont *Higher recursion theory* de Gerald Sacks [192] et *Recursion Theory : Computational Aspects of Definability* de Chi Tat Chong et Liang Yu [35]. Chacun de ces ouvrages présente l'état de l'art de la recherche pour un sous-domaine spécifique de la calculabilité, mais il n'existe pas un unique livre qui organise une présentation cohérente de ces différents aspects.

► Le calculabilité est un sujet d'étude extrêmement vaste, comme le laisse entrevoir la profusion d'articles sur le sujet et la taille des ouvrages de référence en anglais. Cependant, ce domaine reste très peu représenté en France, aussi bien du point de vue de la recherche que de l'enseignement. Peu de cours de calculabilité sont proposés en master, et leur contenu tend à véhiculer l'idée fausse que la calculabilité est une théorie des modèles de calcul. Cet ouvrage a pour ambition de donner ses lettres de noblesse à la calculabilité en France en donnant un petit panorama de sa grande richesse, encore trop méconnue.

# Organisation du livre

Ce livre est structuré en quatre grandes parties, à savoir la calculabilité classique, l'aléatoire algorithmique, les mathématiques à rebours et l'hypercalculabilité.

## Plan général

► La calculabilité classique est l'étude des degrés Turing, autrement dit la puissance calculatoire des ensembles d'entiers naturels. Elle constitue le cœur historique de la calculabilité, et le socle épistémique sur lequel s'appuient les trois parties suivantes.

► L'aléatoire algorithmique utilise la calculabilité classique pour donner un cadre effectif à la théorie de la mesure, qui permet d'étudier individuellement les suites de bits dites « aléatoires ». Les hiérarchies induites par la calculabilité classique permettent de définir différents niveaux d'aléa, à la lumière desquels on peut, par exemple, réexaminer la signification de tel ou tel théorème probabiliste stipulant qu'une propriété est vraie presque partout.

► Les mathématiques à rebours forment un programme sur les fondements des mathématiques, qui vise à identifier les axiomes nécessaires pour
prouver les théorèmes mathématiques de la vie de tous les jours<fnref n="1" />. Elles reposent sur une théorie de base, RCA₀, dont les axiomes capturent les mathématiques « calculables » grâce à une correspondance entre la calculabilité et la définissabilité par des formules logiques.

▷ L'hypercálculabilité étend la notion de calculabilité à un cadre plus général rejoignant la théorie des ensembles. De la même manière que les opérations arithmétiques élémentaires s'étendent aux ordinaux, les machines de Turing peuvent étendre leur temps de calcul, des entiers aux ordinaux, et manipuler ainsi de plus grandes classes de réels. Il s'agit de l'approche par « modèle de calcul » de l'hypercálculabilité, qui correspond, comme pour la calculabilité classique, à certaines classes logiques.

Les trois dernières parties s'appuient toutes fortement sur la calculabilité classique, mais sont relativement indépendantes entre elles, et peuvent être pour l'essentiel, lues dans un ordre quelconque :

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

Dépendances entre les quatre grandes parties du livre

Notons tout de même la notion de « classe Borélienne » introduite dans la partie II, et fondamentale pour la compréhension de la partie IV.

## Calculabilité classique

La calculabilité classique a un rôle prépondérant en ce qu'elle fixe un cadre formel et une série d'outils qui serviront à développer les parties suivantes. Il convient donc de s'attarder sur la première partie et de détailler les dépendances de ses chapitres. Les chapitres fondamentaux sont principalement à lire linéairement, avec les exceptions suivantes : les chapitres 6 et 9 peuvent être lus indépendamment des autres, mais seront cependant utiles pour aborder sereinement la partie III du livre, sur les mathématiques à rebours. Les chapitres 12 et 14 ne seront pas absolument nécessaires pour la compréhension des parties suivantes, et visent à prendre un peu de recul

<footnote n="1">1. De la vie de tous les jours du mathématicien, s'entend.</footnote>
sur notre travail. Le chapitre 12 — moins technique — le fera à travers l'examen d'une question spécifique, à la frontière de la philosophie; et le chapitre 14 à travers une étude plus abstraite de la structure des degrés Turing, et la présentation de quelques-unes des grandes questions ouvertes du domaine.

<figure><img src="image_11.png" /><figcaption>Dépendances entre les chapitres de la calculabilité classique</figcaption></figure>

# Comment lire ce livre

## Pour les enseignants

Ce livre peut servir de support pour un cours d'introduction à la calculabilité de niveau master, ainsi que pour des cours thématiques plus avancés, parlant de théorie algorithmique de l'aléatoire, de mathématiques à rebours et d'hypercalculabilité. Les sujets abordés vont bien au-delà des connaissances en calculabilité que l'on peut attendre d'un étudiant en master. Nous allons donc proposer un plan de cours contenant les notions incontournables.

L'équivalence entre les modèles de calcul forme un socle robuste pour le développement de la calculabilité. Cependant, les preuves peuvent sembler
assez longues et fastidieuses. De nos jours, avec la démocratisation des ordinateurs, on peut s'attendre à ce que les étudiants possèdent une certaine intuition de ce qu'est un algorithme, et il semble préférable de partir de cette intuition pour faire les premiers développements afin d'éviter un formalisme relativement lourd. Nous recommandons d'aborder l'équivalence des modèles de calcul, notamment entre les fonctions générales récursives et les machines de Turing, à travers une séance de travaux dirigés, où les étudiants auront l'occasion de manipuler les formalismes en définissant des fonctions de plus en plus compliquées pour se convaincre que ces définitions permettent de capturer tous les algorithmes.

Nous invitons nos lecteurs à suivre les développements des différents chapitres 3, 4, 5, 7, 8, 10, 13 dans cet ordre. Le chapitre 3 établit les premiers théorèmes fondamentaux de la calculabilité sur la base de l'intuition que l'on a des algorithmes. Le chapitre 4 définit la notion de machine à oracle, et de degré Turing. On y trouve les définitions les plus centrales de la calculabilité, comme le saut de Turing, et la méthode des extensions finies qui est une technique très puissante pour prouver l'existence de certains degrés Turing. Le chapitre 5 sur la hiérarchie arithmétique établit un lien essentiel entre la puissance calculatoire d'ensembles d'entiers et leur définissabilité par des formules de l'arithmétique, à travers le théorème de Post.

Avec le chapitre 7, on commence l'étude de différentes propriétés calculatoires fondamentales, comme la notion de degré hyperimmune, et ses liens avec l'existence de fonctions à croissance rapide. Cette étude est poursuivie dans le chapitre 8 sur les classes $Π_1^0$, où l'on définit la notion de degré PA qui est une notion centrale en calculabilité. On la retrouve tout au long de ce livre, notamment en aléatoire algorithmique et en mathématiques à rebours.

Le chapitre 10 introduit une technique fondamentale de la calculabilité, à savoir le forcing, présentée ici comme une élaboration de la méthode des extensions finies du chapitre 4. Ce chapitre peut également servir comme le premier niveau d'une compréhension graduelle de la technique générale du forcing de la théorie des ensembles.

Le chapitre 13 introduit finalement les méthodes de priorités, une autre technique fondamentale de la calculabilité, qui permet notamment de montrer l'existence de certains degrés calculatoirement énumérables.

## Pour les étudiants

Les compétences requises pour comprendre les notions présentées dans cet ouvrage sont celles d'une première année de licence en informatique ou mathématiques. Il est nécessaire pour l'essentiel de comprendre le langage
mathématique usuel (variables, quantifications, etc.), d'avoir quelques no-
tions élémentaires de logique (preuve par contraposée, preuve par l'ab-
surde, etc.), et de comprendre les éléments du corpus mathématique de
base (comprendre ce qu'est une bijection, ce qu'est une intersection entre
deux ensembles, les fonctions puissance et logarithme, etc.). En plus de
cela, une expérience même sommaire en programmation, ou à défaut la
compréhension de ce qu'est un algorithme, est également nécessaire pour
aborder sereinement la lecture de ce livre.

Les mathématiques que nous utiliserons et qui ne sont pas enseignées dans
une première année de licence seront introduites et expliquées au fur et à
mesure des besoins (notions de base de topologie ou de théorie de la me-
sure par exemple). Ayant établi cela, notons tout de même que le degré
d'élaboration des preuves, ainsi que la technicité de certains concepts, ren-
dront sans doute cet ouvrage difficile à aborder sans une certaine maturité
mathématique.

Les techniques développées en calculabilité sont assez différentes de celles
apprises à travers un cursus mathématique standard. Cette particularité
de la calculabilité est une force et rend cette discipline plus accessible puis-
qu'elle est peu sensible aux lacunes que l'on peut avoir développé au cours
de son cursus (ou de son absence de cursus). En revanche, cette différence
peut également déstabiliser l'étudiant car cela demande de se créer un uni-
vers conceptuel. Il va sans dire qu'en l'absence de professeur, il est d'autant
plus essentiel de faire les exercices proposés au cours du livre pour bien
intégrer les concepts. Les solutions sont disponibles à la fin du livre.

La taille de cet ouvrage peut s'avérer décourageante pour un étudiant désireux de faire ses premiers pas en calculabilité. Nous rappelons que ce livre couvre des connaissances allant bien au-delà de ce que l'on attend d'un étudiant en master. Nous recommandons donc aux autodidactes de suivre la suggestion de cours de la section précédente, destinée aux enseignants.

Pour les chercheurs

Cet ouvrage est une introduction à la calculabilité et à plusieurs de ses
branches principales. Il ne faut cependant pas s'arrêter à l'aspect introduc-
tif de cet ouvrage, car la plupart des résultats présentés correspondent à
l'état de l'art de la recherche. Ce livre s'adresse donc aussi bien aux cher-
cheurs de domaines connexes désireux d'acquérir de solides connaissances
en calculabilité, qu'aux doctorants et chercheurs se destinant à la recherche
en calculabilité. En effet, les techniques et concepts de ce livre rendent di-
rectement accessibles les articles de recherche du domaine.
## Exercices

Les chapitres sont parsemés d'exercices de difficulté variable, dont la correction est donnée à la fin du livre. On ne rappellera jamais assez l'importance de faire des exercices pour bien assimiler les notions présentées dans les chapitres. L'intuition des concepts se crée en les manipulant sous toutes leurs formes. La difficulté des exercices est indiquée à l'aide d'un système d'étoiles (★) allant de 0 à 3 : un exercice sans étoile est une application directe des définitions, tandis qu'un exercice à deux étoiles demande une profonde maîtrise des concepts pour être résolu. On trouvera également quelques exercices à trois étoiles, qui sont d'un niveau << recherche >>.

À travers cet ouvrage, nous allons présenter beaucoup de propriétés calculatoires sur les ensembles d'entiers ou sur d'autres structures plus complexes. Outre les exercices donnés, il est important de faire preuve d'une curiosité intellectuelle consistant à chercher systématiquement comment se combinent ces propriétés, savoir si l'on peut construire des objets satisfaisant plusieurs d'entre elles simultanément, et ainsi de suite. De même, lorsque les théorèmes possèdent des hypothèses, il est utile de chercher des contre-exemples sans ces hypothèses, afin de mieux comprendre leur nécessité ainsi que leur usage dans la preuve.

## Errata

Il est impossible d'écrire un livre de cette taille sans laisser se glisser un certain nombre de coquilles. Cet ouvrage ne dérogera probablement pas à cette règle. Nous maintiendrons une liste des coquilles sur la page web des auteurs. Vous pouvez signaler les erreurs à l'une des adresses suivantes :

benoit.monin@computability.fr

ou

ludovic.patey@computability.fr
<figure><img src="image_12.png" /></figure>
Remerciements

Notre tout premier remerciement va à l'Agence nationale de la recherche, qui a en grande partie financé la collaboration entre les deux auteurs, notamment pendant l'écriture du livre, dans le cadre du projet « Aspects Calculatoires des Théorèmes Combinatoires – ACTC »

https://anr.fr/Projet-ANR-19-CE48-0012

Plusieurs résultats présentés dans ce livre, notamment le théorème 25-3.23 sur le principe des tiroirs ou la preuve simplifiée du théorème 25-3.24 de Liu proviennent d'articles financés par ce même projet.

Nous tenons également à remercier nos équipes et organismes de rattachement, qui nous ont fourni un vivier d'émulation intellectuelle ainsi qu'un soutien moral et financier. Pendant la rédaction de cet ouvrage, Monin était maître de conférences dans le Laboratoire d'Algorithmique, Complexité et Logique de l'Université Paris-Est Créteil et Patey chargé de recherche au CNRS, dans l'équipe Algèbre, Géométrie, Logique de l'Institut Camille Jordan à Villeurbanne.

De nombreux collègues nous ont généreusement aidé à améliorer la qualité de cet ouvrage, en donnant un regard critique sur son contenu scientifique et pédagogique, fort de leurs expertises respectives, ou bien en signalant les erreurs typographiques qui se sont inévitablement glissées dans le livre. Nous remercions donc Paul-Elliot Anglès d'Auriac, Sébastien Tavenas, Pascal Vanier, Mathieu Hoyrup, Benjamin Hellouin, Laurent Bienvenu, Bruno Durand, Denis Kuperberg, Julien Cervelle, Damir Dzhafarov, Loïc Gassmann, William Gaudelier, Denis Hirschfeldt, Quentin Le Houerou, Alexander Shen, Keita Yokoyama, Adrien Deloro, Pascal Monin et Shahin Amini.

Le contenu scientifique du livre est avant tout l'œuvre de la communauté de la calculabilité. Les auteurs ont forgé leurs intuitions en lisant les ouvrages
de leurs prédécesseurs et en ajoutant leur pierre à ce magnifique édifice
intellectuel. Nous tenons à remercier nos collègues au niveau international
pour les collaborations et les visites mutuelles ayant permis d'améliorer
notre compréhension du sujet.

Nous tenons également à remercier Laurent Bienvenu, qui par son travail
et à travers la direction de nos thèses respectives, a su nous transmettre sa
passion, et a largement contribué à introduire la calculabilité en France.

La rédaction d'un ouvrage de cette ampleur prend beaucoup de temps et
d'énergie, et n'aurait pu avoir lieu sans le soutien moral de nos familles et
amis.

Nous tenons enfin à remercier les éditions Calvage et Mounet pour leur
confiance, leur soutien et leur travail éditorial, et particulièrement Rached
Mneimné pour sa relecture minutieuse du livre.
<figure><img src="image_13.png" /></figure>
<figure><img src="image_14.png" /></figure>
Chapitre 1

Introduction

Le savant n'étudie pas la nature parce que cela est utile; il l'étudie
parce qu'il y prend plaisir et il y prend plaisir parce qu'elle est
belle. Si la nature n'était pas belle, elle ne vaudrait pas la peine
d'être connue, la vie ne vaudrait pas la peine d'être vécue. Je ne
parle pas ici, bien entendu, de cette beauté qui frappe les sens, de
la beauté des qualités et des apparences; non que j'en fasse fi, loin
de là, mais elle n'a rien à faire avec la science; je veux parler de cette
beauté plus intime qui vient de l'ordre harmonieux des parties, et
qu'une intelligence pure peut saisir.

Science et méthode, Henri Poincaré

**Qu'est-ce que la calculabilité ?** On considère classiquement la calculabilité comme l'un des quatre piliers de la logique, aux côtés de la théorie des ensembles, la théorie des modèles et la théorie de la preuve. Le domaine s'est au départ forgé sur la question de ce qui caractérise les fonctions $f: N \to N$ dont les valeurs peuvent être obtenues par un processus purement mécanisable ou algorithmique, en un temps fini, bien qu'arbitrairement grand. Nous dirons que de telles fonctions sont effectivement calculables. Bien avant l'apparition des premiers ordinateurs, la calculabilité a fondé sa base théorique sur un constat — ou plutôt un miracle — à savoir l'existence d'une définition robuste, consensuelle et indépendante de tout formalisme, de la notion épistémologique de fonction effectivement calculable.
La question initiale — à savoir « Qu'est-ce qu'une fonction calculable ? » —
ayant obtenu une réponse satisfaisante, l'étude s'est naturellement portée
vers la question de savoir, parmi les fonctions naturelles, lesquelles sont
calculables et lesquelles ne le sont pas. Par la suite, le domaine a connu
un développement considérable grâce à la notion de calculabilité relative,
la question n'étant plus de déterminer si une fonction est calculable ou
non, mais d'identifier la puissance calculatoire intrinsèque à cette fonction,
à travers des questions comme « Si cette fonction était calculable, quelles
autres fonctions pourrait-on calculer ? »

Plus récemment, le sujet d'étude s'est étendu à de très nombreux objets
mathématiques — par exemple des structures algébriques ou des sous-
ensembles de $\mathbb{R}$ — et a donné de nombreuses ramifications. Nous verrons
notamment dans ce livre que la calculabilité sert de fondement robuste à la
théorie algorithmique de l'aléatoire, et aux mathématiques à rebours, dont
les objets d'études sont les théorèmes mathématiques eux-mêmes.

De nos jours, l'appellation « calculabilité » pour un domaine qui étudie des
objets mathématiques arbitraires, dont la plupart ne sont pas calculables,
peut sembler étonnante, voire un reliquat de son sujet d'étude historique.
En vérité, ce nom est toujours judicieux, mais sa signification a changé : le
terme calculabilité ne porte plus sur le sujet de l'étude, mais sur l'angle sous
lequel le sujet est abordé. Une définition moderne de la calculabilité en une
phrase pourrait être : la calculabilité est l'étude des mathématiques
sous le prisme de leur complexité calculatoire.

1. Qu'est-ce qu'une fonction calculable ?

La principale difficulté de cette question réside dans l'obtention d'une classe
de fonctions suffisamment robuste pour ne pas dépendre du modèle d'ordi-
nateur, du choix du langage de programmation, des progrès technologiques,
ou de l'avancée de la connaissance de manière générale.

Avec l'avènement des ordinateurs, la notion d'algorithme s'est peu à peu
ancrée dans la culture scientifique. Toute personne ayant déjà eu un pre-
mier contact avec la programmation se sera déjà formée une bonne idée de
ce qu'est une tâche automatisable. Forts de notre connaissance de l'infor-
matique, la définition suivante viendrait naturellement : « Une fonction est
effectivement calculable si elle possède un algorithme, autrement dit si elle
peut être programmée dans un langage suffisamment expressif, et exécutée
par un ordinateur suffisamment puissant. »

Cette définition, si elle a l'avantage d'être en adéquation avec notre in-
tuition, ne fournit pas un cadre suffisamment formel pour raisonner sur
la classe des fonctions calculables. Une seconde approche consisterait à
fixer un ordinateur et un langage de programmation étalon, et définir une fonction comme calculable si elle est programmable dans ce langage, et exécutable par cet ordinateur en temps fini, à l'aide de suffisamment de mémoire. Si l'on ne se préoccupe pas de la rapidité d'exécution, ni de l'espace mémoire nécessaire, il apparaît rapidement que cette définition coïncide avec la précédente. En effet, la puissance et la mémoire des ordinateurs augmentent au gré des progrès technologiques, et permettent donc d'exécuter plus rapidement les programmes, mais n'augmentent pas pour autant la classe des fonctions calculables. Même les ordinateurs basés sur de nouveaux paradigmes de calcul, comme les ordinateurs quantiques ou biologiques, sont simulables — au prix d'un surcoût d'espace et de temps exponentiel — par des ordinateurs classiques, et ne changent donc pas la classe des fonctions calculables. Quant aux langages de programmation, l'existence de systèmes d'exploitation et d'interpréteurs permettent de se convaincre aisément que les principaux d'entre eux tels que C++, Java ou Python, permettent de programmer — plus ou moins élégamment — les mêmes fonctions mathématiques. Cela montre donc empiriquement une certaine robustesse dans la définition de la classe des fonctions programmables.

Un problème subsiste : quelle est la garantie que les ordinateurs actuels représentent la limite de ce qui est automatisable, ou calculable par un être humain ? Qui nous dit qu'avec les progrès de la science, nous ne découvrirons pas un nouveau paradigme de calcul ou une nouvelle manière de raisonner permettant de considérer comme calculable une plus large classe de fonctions ? C'est là le sujet d'une longue quête fondationnelle débutée au XXe siècle, et aboutissant à la fameuse thèse de Church-Turing en 1936, que nous présenterons dans le chapitre 6.

## 2. Quelles sont les fonctions incalculables ?

Au regard de notre définition précédente, pour l'instant très informelle, la plupart — si ce n'est la totalité — des fonctions mathématiques utilisées au quotidien sont calculables : l'addition, la multiplication, la fonction $(n, m) \mapsto n^m$, la fonction qui à $n$ associe le $n$-ième nombre premier, ou encore celle qui calcule le plus grand diviseur commun de deux entiers naturels, sont toutes calculables. On peut rajouter à cette liste des exemples moins triviaux : la fonction qui prend un programme informatique écrit en C++ et détermine si le programme est syntaxiquement correct — c'est ce que fait entre autres choses un compilateur pour C++ — ou encore celle qui renvoie la $n$-ième décimale de $\pi$, $\sqrt{2}$ ou du nombre d'or — chacun de ces nombres est la somme d'une suite calculable de rationnels de convergence
suffisamment rapide— ou pour finir celle qui à *n* associe le nombre de parties possibles que l'on peut faire au jeu de go sur un plateau — appelé aussi *goban* — de taille *n* × *n*. Ce dernier exemple illustre en particulier le fait suivant : on ne s'occupe pas en calculabilité du temps que prend un calcul. Seule l'existence d'un algorithme nous importe. Dans le cas du nombre de parties au jeu de go, l'algorithme en question repose sur une idée simple ; il « suffit » de lister toutes les parties possibles et de les compter. Cependant, le temps d'exécution d'un tel algorithme est tellement grand que cela le rend impossible à utiliser en pratique pour *n* > 2 <sup>1</sup>. Pour *n* = 19, qui est la taille d'un goban standard, ce nombre est compris entre 10<sup>10</sup><sup>48</sup> et 10<sup>10<sup>171</sup></sup> [225], ce qui fait clairement trop de parties à compter même si tous les ordinateurs de monde s'y attelaient pour un milliard d'années...

Même si la fonction de multiplication par 2 nous est, en un sens, bien plus accessible que celle qui compte le nombre de parties au jeu de go, il existe un algorithme qui calcule chacune d'entre elles. Ces deux fonctions ne sont donc pas différentes l'une de l'autre du point de vue de la calculabilité : elles sont toutes les deux calculables, et nous allons principalement nous intéresser aux fonctions qui ne le sont pas, c'est-à-dire les fonctions dont les valeurs ne peuvent pas être obtenues par un processus purement mécanisable ou algorithmique. La simple existence de telles fonctions n'est pas une évidence en soi, et l'une des premières tâches à laquelle nous nous attellerons sera d'en montrer l'existence. Cela sera fait dans le chapitre suivant via l'argument diagonal de Cantor. Nous donnerons ensuite tout au long du livre de très nombreux exemples de telles fonctions, la plus connue d'entre elles étant sans doute le problème de l'arrêt, défini comme la fonction qui prend en entrée un programme, et détermine si son exécution va s'arrêter, en temps fini nécessairement. Nous verrons que le problème de l'arrêt n'est pas calculable ; et il est important de comprendre qu'il s'agit bien ici d'une impossibilité théorique et fondamentale, qui ne dépend pas de la puissance ou vitesse de calcul des ordinateurs. L'incalculabilité du problème de l'arrêt n'est pas due à une ignorance de son algorithme qui pourrait être un jour découvert, mais bien à une impossibilité absolue, car l'existence d'un tel algorithme entraînerait un paradoxe.

## 3. Motivations

La calculabilité porte principalement sur l'étude des fonctions — ou objets mathématiques plus généraux — incalculables. Il est légitime de se demander si une telle étude est bien raisonnable. Si même certaines fonctions calculables nous sont inaccessibles — comme le nombre de parties possibles

<footnote n="1">1. Il y a déjà 386 356 909 593 parties possibles sur un goban de taille 2 × 2 [225] !</footnote>
au jeu de go — alors à quoi bon se donner la peine de réfléchir sur des fonctions *encore plus inaccessibles* ?

Une première motivation pour notre étude est d'ordre exploratoire. Il existe des objets inaccessibles, essayons d'en explorer l'univers. Simplement parce qu'il est là, et par curiosité sur les mystères qu'il renferme. Nos efforts seront récompensés par une série de théorèmes d'une très grande profondeur. Quiconque se plonge avec sérieux dans les développements de ce livre, une fois peut-être passé quelques difficultés d'adaptation inhérentes à toute discipline scientifique, verra un monde d'une richesse stupéfiante prendre vie dans son esprit, avec sa faune et sa flore, ses règles et mécanismes. La calculabilité est caractérisée par la nature très dynamique de ses preuves, chacune d'elles en offrant un aperçu sur le fonctionnement détaillé d'un fragment de la machinerie titanesque qui anime cet univers.

Une deuxième motivation survient tout simplement par nécessité. Les Pythagoriciens se sont retrouvés contraints et forcés d'admettre l'existence de mesures irrationnelles, comme la diagonale d'un carré de côté 1, ce qui allait à l'encontre de leur compréhension du monde, qu'ils pensaient explicable uniquement en se fondant sur les rapports entre nombres entiers. Mais si l'on admet l'existence des entiers, et l'existence du carré, on est forcé d'admettre celle de quantités *incommensurables*, que l'on appelle aujourd'hui irrationnelles, comme $\sqrt{2}$. De la même manière, nous verrons que si l'on admet l'existence des objets calculables, on est forcé aussi d'admettre l'existence d'objets qui ne le sont pas, et qui apparaissent malgré tout naturellement dans toute une série de situations.

Une dernière motivation enfin est d'ordre pratique. La calculabilité, via la compréhension qu'elle donne des objets incalculables, a obtenu des succès majeurs en fournissant un cadre formel pour l'étude de questions à la frontière entre science et philosophie. Nous en verrons deux : la recherche de la définition d'objets aléatoires avec la partie II, et la compréhension de ce que signifie la force d'un théorème, notamment par rapport à un autre, avec la partie III. La partie IV de ce livre amènera quant à elle la calculabilité vers la frontière qu'elle partage avec la théorie des ensembles.

# 4. Panorama de la calculabilité

La calculabilité peut se décomposer en plusieurs sous-domaines, qui s'appuient tous sur la même notion robuste de fonction effectivement calculable.

## 4.1. Domaines couverts par ce livre

Cet ouvrage est décomposé en quatre parties, chacune d'entre elles couvrant une ramification de la calculabilité : la calculabilité classique, l'aléatoire algorithmique, les mathématiques à rebours, et l'hypercalculabilité.
## Calculabilité classique

Comme nous l'avons spécifié, la calculabilité porte avant tout sur des objets que l'on ne peut pas calculer. La calculabilité classique se concentre sur les fonctions $f : N \to N$ ainsi que sur les ensembles d'entiers $E \subseteq N$. Remarquons qu'un tel ensemble peut aussi être représenté par sa fonction caractéristique $\chi_E : N \to N$ définie par $\chi_E(x) = 1$ si $x \in E$, et $\chi_E(x) = 0$ sinon.

Les développements de la calculabilité classique s'articulent autour d'un outil fondamental qui nous permettra de comparer ou encore de mesurer le degré d'incalculabilité d'une fonction, appelé aussi degré d'insolubilité ou encore degré Turing, en référence au mathématicien Alan Turing qui introduisit la notion. Fixons une fonction non calculable $g : N \to N$. Il est naturel de se demander « Si j'étais capable de calculer $g$, quelles autres fonctions pourrais-je calculer ? » On dit qu'une fonction $f : N \to N$ est calculable relativement à $g$ (ou $g$-calculable) s'il existe un algorithme permettant de calculer $f$ dans un langage de programmation étendu, où l'on aurait rajouté la fonction $g$ comme primitive : une instruction spéciale nous permet d'appeler la fonction $g$ sur un paramètre $n$ dans notre programme, comme si elle existait réellement, et d'en récupérer le résultat. Si $f$ est $g$-calculable, rien ne nous indique comment calculer $g$, mais si l'on disposait d'un « oracle » nous permettant de calculer les valeurs de $g$, il serait possible de calculer les valeurs de $f$.

Cette notion de calculabilité relative nous permet de définir un pré-ordre partiel entre les fonctions, notant $f \leq_T g$ si la fonction $f$ est $g$-calculable. Il s'agit de la réduction Turing. Différentes fonctions peuvent porter la même puissance calculatoire, au sens où elles sont mutuellement calculables. On définit donc le degré Turing d'une fonction $f : N \to N$ l'ensemble deg$_T$ f de toutes les fonctions $g$ telles que $f \leq_T g$ et $g \leq_T f$. La notion de degré Turing représente une puissance calculatoire, au sens où deux fonctions de même degré Turing sont indistinguishables du point de vue de la calculabilité. Le pré-ordre partiel sur les fonctions induit un ordre partiel sur les degrés Turing.

La calculabilité classique porte principalement sur l'étude des degrés Turing munis de la relation d'ordre partielle définie ci-dessus. Existe-t-il une infinité de puissances calculatoires ? Sont-elles linéairement ordonnées ? Plus généralement, quelles sont les propriétés de cet ordre partiel ? Il s'avère que cette structure est extrêmement riche et complexe, comme nous aurons l'occasion de le voir.

## Aléatoire algorithmique

La théorie classique des probabilités étudie les phénomènes probabilistes, modélisés avec succès via la notion de mesure qui sert à définir formellement
les lois de probabilité. Cette théorie n'a en revanche pas les outils nécessaires — et ce n'est pas là son objectif — pour parler d'objets aléatoires individuellement. C'est ce point précis que la théorie algorithmique de l'aléatoire se propose d'éclaircir, en s'appuyant sur la calculabilité. Voyons à travers un exemple de quoi il s'agit.

Représentons un nombre réel $R \in [0, 1]$ par son développement binaire, de la forme $R = 0.b_0b_1b_2b_3...$ où $(b_n)_{n \in \mathbb{N}}$ est une suite de bits. Supposons que le réel $R$ soit obtenu en tirant ses bits *au hasard* par une suite de tirage à pile ou face. On suppose bien entendu que chaque tirage est *équiprobable* : nous avons une chance sur deux d'obtenir pile et une chance sur deux d'obtenir face. L'intuition nous dicte que le réel $R$ ainsi obtenu est *aléatoire*. Que cela signifie-t-il exactement ? On ne s'attend par exemple pas à n'obtenir que des « pile » sur les cent mille premiers lancers : si chaque tirage est équiprobable, cela ne peut arriver, ou en tout cas avec une probabilité tellement faible que l'on peut la considérer comme négligeable. On ne s'attend pas non plus à obtenir deux fois plus de « pile » que de « face ». Là encore, la probabilité que cela arrive sur cent mille tirages est tellement faible que l'on supposera les tirages biaisés plutôt que d'être témoin d'un événement si improbable. On peut de fait identifier une première propriété que l'on est en droit d'attendre d'une suite de tirages équiprobables : la suite obtenue devrait respecter la loi des grands nombres, c'est-à-dire que les nombres de tirages « pile » et « face » doivent à peu près être les mêmes.

Cela est-il pour autant suffisant ? Supposons à présent par exemple que sur chaque tirage numéro $n$, si $n$ est un nombre premier on obtient systématiquement un « pile ». Dans l'hypothèse où une certaine obsession des nombres premiers nous conduirait à remarquer ce curieux phénomène, nous serons là encore en face d'une énigme — un peu absurde — et l'on sera amené à penser que d'une manière ou d'une autre, quelque chose d'anormal est en train de se produire. Mais prenons encore plus de recul. Au fond, et peu importe la suite de bit obtenue, on peut identifier des nombres $n_1 < n_2 < n_3 < ...$ tels que les tirages numéros $n_1, n_2, n_3, ...$ sont tous des tirages « pile ». Dans le cas où notre suite $n_1, n_2, n_3, ...$ contient les nombres premiers, cela nous semble relever d'un « bug probabiliste », mais pourquoi cela devrait-il être acceptable si $n_1, n_2, n_3, ...$ sont des nombres entiers quelconques ? C'est là que la calculabilité entre en jeu, et va nous permettre de formaliser précisément les propriétés que devrait avoir — en accord avec notre intuition humaine — une suite de bits aléatoire.

## Mathématiques à rebours

La notion de théorème est relative à un système d'axiomes. Lorsque l'on omet de mentionner le système de référence, il est communément admis que l'on se réfère au système de Zermelo Fraenkel (ZF), qui représente
un ensemble d'axiomes consensuels servant de fondement à l'ensemble des mathématiques. Le système ZF est cependant très puissant, et nous n'avons aucune garantie de son absence de contradiction.

Les mathématiques à rebours visent à trouver les axiomes nécessaires et suffisants pour prouver les théorèmes des mathématiques de tous les jours. Il s'agit donc d'étudier des théorèmes existants, pour en trouver des preuves plus élémentaires, ou au contraire pour montrer l'optimalité de leur preuve. Mieux comprendre les hypothèses des théorèmes permet de mieux maîtriser leur « fragilité » face à une potentielle contradiction du système de preuves. Il s'agit donc d'une démarche méta-mathématique visant à répondre à la question « Quelle confiance peut-on avoir en nos mathématiques ? »

Au premier abord, cette démarche n'est pas liée à la calculabilité. Cependant, les mathématiques à rebours se réfèrent à une théorie de base, RCA₀, capturant les mathématiques calculables, et qui représente une base de confiance plus en lien avec le monde concret, car ses objets étant calculables, ils peuvent être représentés par un algorithme, donc possèdent une description finitaire. Les mathématiques à rebours consistent donc, étant donné un théorème T, à chercher des axiomes A tels que RCA₀ prouve l'équivalence entre A et T. Par le choix de la théorie de base RCA₀, les équivalences sont des procédés calculatoires faisant appel aux outils de la calculabilité.

## Hypercalculabilité

Une des raisons du succès de la calculabilité en tant qu'outil d'analyse des mathématiques réside dans l'existence d'une solide intuition de la notion de calcul, permettant ainsi de guider la manipulation des concepts et de prouver des théorèmes sans s'embarrasser d'un lourd formalisme. L'hypercalculabilité vise à étendre la portée de ces outils à des modèles de calcul plus puissants, qui peuvent être vus comme des machines ayant la possibilité de poursuivre leur exécution pendant un temps de calcul infinit (formellement en temps de calcul ordinal). Tout comme les notions de calculabilité classique peuvent être capturées par des formules logiques, il en va de même pour l'hypercalculabilité. Par exemple, là où les ensembles d'entiers que l'on peut énumérer (dans le désordre) par un programme informatique sont ceux qui peuvent être décrits par une formule dite Σ<sub>1</sub><sup>0</sup> de l'arithmétique, ceux qui sont énumérables par un programme informatique hypercalculable sont ceux qui peuvent être définis par une formule dite Π<sub>1</sub><sup>1</sup> de l'arithmétique.

Nous verrons que cet aspect des choses rapproche l'hypercalculabilité de la théorie descriptive des ensembles, une branche de la théorie des ensembles qui classifie ces derniers selon le degré de difficulté à les décrire. L'hypercalculabilité peut être vue comme un pont entre la théorie descriptive des ensembles et la calculabilité classique.
## 4.2. Autres branches de la calculabilité

Afin de permettre à cet ouvrage de conserver une taille raisonnable, nous avons fait le choix de faire l'impasse sur deux branches importantes de la calculabilité, à savoir la théorie des structures calculables et l'étude des degrés d'énumération.

### Théorie des structures calculables

Il s'agit d'une branche de la calculabilité qui étudie dans quelle mesure les propriétés algébriques d'une structure mathématique affectent leur complexité descriptive. Par structure, on entend des ensembles munis d'opérations, comme les groupes, les anneaux et les corps, mais également toute structure au sens de la théorie des modèles. Cette branche emprunte ses techniques à la fois à la théorie des modèles et à la calculabilité classique pour répondre à cette question.

Concrètement, cette théorie étudie des structures dénombrables et pose des questions de la forme « Étant donné une structure calculable $\mathcal{A}$, quels sont les degrés Turing possibles des structures isomorphes à $\mathcal{A}$ ? » ou bien « Étant donné deux structures calculables et isomorphes, de quelle puissance calculatoire a-t-on besoin pour calculer leur isomorphisme ? » Par exemple, les instances calculables des ordres denses sans extrémités sont toutes deux à deux calculatoirement isomorphes. On les appelle calculatoirement catégoriques.

### Degrés d'énumération

La calculabilité classique place « le calculable » comme puissance calculatoire de référence. Mais certains problèmes s'expriment de manière naturelle sous forme d'ensembles non calculables, dont les éléments peuvent toutefois être énumérés dans le désordre par un processus calculable. On appelle ces ensembles calculatoirement énumérables (c. e.). En particulier, si $E$ est un ensemble d'entiers c. e. et si $n \in E$, il est possible de s'en rendre compte en un temps fini, en lançant la procédure d'énumération et en attendant que $n$ apparaisse. En revanche, si $n \notin E$, alors il ne sera pas possible en général de le savoir en un temps fini. Par exemple, l'ensemble des équations diophanitiennes (des équations à coefficients entiers, comme $3x^3 - 2y^2 + x - 2 = 0$) qui admettent des solutions entières est calculatoirement énumérable, car il suffit de chercher exhaustivement des solutions, et d'énumérer l'équation si une telle solution existe.

Les degrés d'énumération placent « le calculatoirement énumérable » comme puissance de référence. On peut définir une réduction d'énumération $A \leq_e B$ si toute énumération des éléments de $B$ calcule une énumération des éléments de $A$. Cette réduction est une pré-ordre partiel, qui induit une
notion de *degré d'énumération* : le degré d'énumération de $A$ est l'ensemble $\text{deg}_e(A)$ de tous les ensembles $B$ tels que $A \leq_e B$ et $B \leq_e A$. L'étude des degrés d'énumération munis de l'ordre partiel $\leq_e$ constitue une branche active de recherche en calculabilité.
## Chapitre 2

# Infinis de Cantor

Si l'on devait donner une date à la nais-sance de la logique moderne, nous si-tuerions sans hésiter celle-ci en 1872, date à laquelle Georg Cantor expose sa première démonstration du théo-rème 4.1 à venir, où il établit la non-dénombrabilité des nombres réels. Cantor isolera plus tard la quintessence de cette première preuve à travers son fa-meux *argument diagonal*, qui aura une place centrale en calculabilité.

Les travaux de Cantor sur l'infini marquent le début d'une théorie des ensembles « complexe », qui jouera un grand rôle dans la quête fondationnelle des mathématiques du début du XXe siècle, dont nous parlerons en détail en première partie du chapitre 9, sur la fameuse « crise des fondements ». Cette crise débouchera sur le développement de la logique mathématique telle que nous la connaissons aujourd'hui, avec la théorie des ensembles moderne, dite ZFC, mais aussi avec le développement des premières théories du calcul, utilisées par Gödel pour montrer son fameux théorème d'inc-complétude, que l'on peut considérer comme une déclinaison sophistiquée de l'argument diagonal de Cantor.

<figure><img src="image_15.png" /><figcaption>Georg Cantor, 1845-1918</figcaption></figure>
De quoi s'agit-il exactement ? Cantor montre que les ensembles infinis n'ont pas tous la même « taille ». Il y a strictement plus de nombres réels que de nombres entiers, dans un sens que nous définirons précisément dans quelques lignes. Cantor se basera sur cette découverte pour développer une étude mathématique de l'infini. Il créera notamment les nombres transfinis, qui constitueront la colonne vertébrale des définitions mathématiques, et que nous aborderons dans le chapitre 27.

Cantor ne fut cependant pas le premier à remarquer que l'infini n'obéissait pas aux mêmes règles que le fini. En particulier, une caractéristique surprenante des ensembles infinis est que le tout n'est pas forcément plus grand que ses parties. Galilée en fait une exposition lumineuse dans son ouvrage « Discours concernant deux sciences nouvelles » [71] à travers un dialogue savoureux entre deux personnages, Salviati et Simplicio :

- Salviati. *J'estime que les épithètes comme « plus grand », « plus petit » et « égal » ne conviennent pas aux grandeurs infinies, dont il est impossible de dire que l'une est plus grande, plus petite ou égale à une autre. Mais voici pour le prouver un raisonnement qui me revient à l'esprit : vous savez parfaitement je suppose quels nombres sont carrés et quels nombres ne le sont pas.*

- Simplicio. *Je sais parfaitement qu'un nombre carré provient de la multiplication d'un autre nombre par lui-même; ainsi quatre, neuf, etc. sont des nombres carrés résultant de la multiplication de deux, trois, etc. par eux-mêmes.*

- Salviati. *Fort bien, quant aux nombres qui ne proviennent pas de nombres multipliés par eux-mêmes, ce ne sont pas des carrés. Par conséquent, si je dis que les nombres pris dans leur totalité, en incluant les carrés et les non-carrés, sont plus nombreux que les carrés seuls, j'énoncerai, n'est-ce pas, une proposition vraie ?*

- Simplicio. *Très certainement.*

- Salviati. *Si je demande maintenant combien il y a de nombres carrés, on peut répondre sans se tromper qu'il y en a autant que de racines correspondantes, attendu que tout carré a sa racine et toute racine son carré, qu'un carré n'a pas plus d'une racine et une racine pas plus d'un carré.*

- Simplicio. *Exactement.*

- Salviati. *Mais si je demande combien il y a de racines, on ne peut nier qu'il y en a autant que de nombres, puisque tout nombre est la racine de quelque carré il faudrait admettre que les carrés sont aussi nombreux que tous les nombres pris ensemble.*
On observe à la lecture du dialogue de Galilée le piège du paradoxe se refermer sur Simplicio. Galilée utilise pour cela un concept qui sera repris par Cantor : deux ensembles $A$ et $B$ << ont le même nombre d'éléments >> si l'on peut faire correspondre exactement les éléments de $A$ et les éléments de $B$, autrement dit s'il existe une bijection entre les deux ensembles.

# 1. Équipotence et subpotence

Rappelons qu'une fonction $f : E \to F$ est *injective* si

$$ \forall x, y \quad x \neq y \Rightarrow f(x) \neq f(y), $$

surjective si son image est l'ensemble $F$ tout entier, et *bijjective* si elle est à la fois injective et surjective.

**Définition 1.1.** Deux ensembles $E$ et $F$ sont équipotents s'il existe une bijection entre eux. On écrira alors $|E| = |F|$. ◇

<figure><img src="image_16.png" /><figcaption>FIGURE 1.2 – L’argument de Galilée pour dire qu’il y a << autant >> d’entiers que de carrés</figcaption></figure>

Selon notre définition les entiers, et les carrés d'entiers ont donc la même cardinalité : il y a autant d'éléments dans les deux ensembles. Ce qui semble paradoxal, c'est que les carrés d'entiers forment une partie stricte de l'ensemble des entiers. Le paradoxe est résolu de la manière la plus simple qui soit : l'intuition que l'on a sur les ensembles finis, qui veut qu'une sous-partie stricte d'un ensemble contienne moins d'éléments n'est tout simplement plus vraie pour les ensembles infinis.
**Remarque**

La notation $|E| = |F|$ semble suggérer l'égalité entre deux objets $|E|$ et $|F|$, que l'on nomme respectivement *cardinalité* de E et *cardinalité* de F. Il est possible de donner une définition précise de $|E|$, en tant qu'objet mathématique. Nous nous contenterons pour le moment de définir la cardinalité comme la notion informelle de taille d'un ensemble, et si l'objet $|E|$ n'est pas clairement défini, l'énoncé $|E| = |F|$ l'est, et suffit à notre traitement de l'infini.

Notons que Galilée utilise son idée pour expliquer justement pourquoi il n'y a aucun sens à comparer la taille des ensembles infinis. C'est là qu'intervient tout le génie de Cantor, qui découvrira que contrairement à l'in tuition de Galilée, il est possible de donner une notion formelle de taille aux ensembles infinis : il existe des infinis « plus gros » que d'autres.

Intuitivement, un ensemble $F$ est au moins aussi gros qu'un ensemble $E$ si l'on peut faire correspondre aux éléments de $E$ des éléments distincts de $F$, autrement dit si l'on peut associer à chaque élément de $E$ un « représentant » qui lui est propre dans $F$.

**Définition 1.3.** Un ensemble $E$ est *subpotent* à un ensemble $F$ s'il existe une injection de $E$ dans $F$. On écrit alors $|E| \le |F|$. Si $E$ n'est pas subpotent à $F$, on écrit $|E| \not\le |F|$. ◇

Il est facile de vérifier que cette relation est *transitive*, c'est-à-dire, que si $|E| \le |F|$ et $|F| \le |G|$, alors $|E| \le |G|$. En effet, si les fonctions $f : E \to F$ et $g : F \to G$ sont deux injections, alors leur composition $g \circ f : E \to G$ est une injection témoignant de la relation $|E| \le |G|$. Il est cependant beaucoup moins clair que si $|E| \le |F|$ et $|F| \le |E|$, alors $|E| = |F|$. En déroulant les définitions, la question revient à savoir si, lorsqu'il existe une injection de $E$ dans $F$ et une autre de $F$ dans $E$, il existe une bijection entre $E$ et $F$. Voyons tout de suite que c'est bien le cas : il s'agit du théorème de Cantor-Bernstein.

## 2. Théorème de Cantor-Bernstein

Le cœur de la preuve du théorème de Cantor-Bernstein tient dans le lemme suivant.

**Lemme 2.1.** Si $B \subseteq A$ sont des ensembles, et $f : A \to B$ est une fonction injective, alors il existe une bijection $h : A \to B$. ★

**PREUVE.** Le lecteur pourra s'aider de la figure 2.2.
<figure><img src="image_17.png" /><figcaption>FIGURE 2.2 – Illustration de la preuve du lemme 2.1</figcaption></figure>

Soit $C_0, C_1, C_2, \dots$ la suite définie par récurrence comme suit :

$$C_0 = A \setminus B \text{ et } C_{n+1} = f(C_n).$$

On note $C = \bigcup_n C_n$. Un simple raisonnement par récurrence sur $n$ permet de montrer, à l'aide de l'injectivité de $f$, que les ensembles $C_n$ pour $n \in \mathbb{N}$ sont deux à deux disjoints, bien que cela ne soit pas nécessaire dans la preuve. Soit la fonction $h : A \to B$ définie par :

$$h(x) = \begin{cases} f(x) & \text{si } x \in C \\ x & \text{si } x \notin C. \end{cases}$$

Montrons que $h$ est injective. La fonction $f$ étant injective, la fonction $h$ restreinte à $C$ est injective. La fonction $h$ restreinte à $A \setminus C$ est la fonction identité, et est donc également injective. Enfin, l'image de $C = \bigcup_n C_n$ par $h$ est

$$\bigcup_n f(C_n) = \bigcup_n C_{n+1} \subseteq C,$$

et l'image de $A \setminus C$ par $h$ est $A \setminus C$. La fonction $h$ est la réunion de deux fonctions injectives possédant des images disjointes, et est donc injective.

Montrons enfin que $h$ est surjective. Soit $y \in B$ ; si $y \notin C$, alors $h(y) = y$ et donc $y$ a un prédécesseur par $h$. Si $y \in C$, comme $y \notin C_0$, il existe un $n \in \mathbb{N}$ tel que $y \in C_{n+1}$. Par définition de $C_{n+1} = f(C_n)$, il existe un $x \in C_n$ tel que $h(x) = f(x) = y$. ■

Nous pouvons à présent montrer le théorème annoncé.
**Théorème 2.3 (Cantor-Bernstein)**

Si $A$ et $B$ sont des ensembles, et $f : A \to B$ et $g : B \to A$ sont des fonctions injectives, alors il existe une bijection entre $A$ et $B$.

PREUVE. Soit $A' = g(B)$. L'application $g \circ f$ est une injection de $A$ dans $A'$. Par le lemme 2.1, il existe donc une bijection $h : A \to A'$. La fonction $g$ étant une bijection entre $B$ et $A'$, la fonction $g^{-1} \circ h : A \to B$ est une bijection.

■

**Corollaire 2.4**

Deux ensembles mutuellement subpotents sont équipotents.

La question de savoir s’il existe des infinis de tailles distinctes, et en particulier avec l’un d’eux strictement plus gros que l’autre, revient donc à savoir si l’on peut trouver deux ensembles $A, B$ pour lesquels $|A| \le |B|$ mais $|B| \le \overline{|A|}$. Nous allons voir que c’est bien le cas.

**3. Ensembles dénombrables**

L’ensemble infini par excellence est bien entendu $\mathbb{N}$, l’ensemble des nombres entiers. On utilise dans ce cas un vocabulaire spécifique.

**Définition 3.1.** Un ensemble infini $A$ est dit *dénombrable* s’il existe une bijection $f : \mathbb{N} \to A$, autrement dit si $A$ et $\mathbb{N}$ sont équipotents. Un ensemble infini $A$ est dit *indénombrable* s’il n’existe pas de bijection $f : \mathbb{N} \to A$. $\diamond$

**Remarque**

Certains auteurs utilisent le terme « dénombrable » pour désigner un ensemble subpotent à $\mathbb{N}$, autrement dit un ensemble fini, ou en bijection avec $\mathbb{N}$. Ils parlent alors d’ensemble *infini dénombrable* pour désigner les ensembles dénombrables tels que nous les avons introduits.

Intuitivement, l’infini des entiers naturels est le plus petit infini, au sens où il est subpotent à tout ensemble infini.

**Proposition 3.2.** L’ensemble $\mathbb{N}$ est subpotent à tout ensemble infini. $\star$

PREUVE. Soit $A$ un ensemble infini. Nous allons définir une fonction injective $f : \mathbb{N} \to A$ par récurrence sur $\mathbb{N}$. Soit $f(0)$ un élément quelconque de $A$. Supposons que les valeurs $f(0), \dots, f(n)$ soient définies. En particulier, $B = \{f(0), \dots, f(n)\} \subseteq A$ est un ensemble fini tandis que $A$ est infini.
Il existe donc nécessairement un élément dans $A \setminus B$. Soit $f(n + 1)$ cet élément. Par construction, $f$ est injective. ■

Notons qu'en toute généralité, la preuve précédente utilise l'axiome du choix, dont nous reparlerons dans la section 9-4, et qui est nécessaire afin de choisir à chaque étape un élément de $A \setminus B$. Toutefois, dans la plupart des cas (comme dans le corollaire suivant), cet axiome n'est pas absolument nécessaire.

**Corollaire 3.3**

Tout sous-ensemble infini d'un ensemble dénombrable est dénombrable.

**PREUVE.** Soit $A$ un ensemble dénombrable, et soit $B \subseteq A$ un sous-ensemble infini. L'ensemble $A$ étant équipotent à $\mathbb{N}$, il est donc subpotent à $\mathbb{N}$. Comme $B \subseteq A$, il est subpotent à $A$, donc à $\mathbb{N}$. En outre, par la proposition 3.2, $\mathbb{N}$ est subpotent à $B$. Par le théorème de Cantor-Bernstein (théorème 2.3), $B$ et $\mathbb{N}$ sont équipotents. ■

**Exercice 3.4. (*)** Soit $A$ un ensemble dénombrable, et soit une bijection $f: \mathbb{N} \to A$. Soit enfin $B \subseteq A$ un sous-ensemble infini. Construire directement une bijection de $\mathbb{N}$ vers $B$ qui ne s'appuie pas sur l'axiome du choix. On entend par là que la définition de la fonction doit reposer sur un algorithme explicite, et non sur une procédure abstraite permettant de choisir un élément dans un ensemble non vide, sans que l'on ne sache de quel élément il s'agit. ◇

Introduisons à présent une bijection que nous utiliserons régulièrement dans ce livre, qui est celle couramment utilisée pour attester de la dénombrabilité du produit $\mathbb{N} \times \mathbb{N}$.

**Proposition 3.5.** L'ensemble $\mathbb{N} \times \mathbb{N}$ est dénombrable. ★

**PREUVE.** Soit $\alpha: \mathbb{N} \to \mathbb{N}^2$ la fonction telle que les valeurs

$$ \alpha(0) = (0,0), \quad \alpha(1) = (1,0), \quad \alpha(2) = (0,1), \dots $$

énumèrent les couples d'entiers par diagonales successives, comme dans la figure 3.6.

La fonction est injective par construction, et toute paire apparaîtra à une étape de l'énumération. Ainsi, $\alpha$ est une bijection de $\mathbb{N}$ vers $\mathbb{N} \times \mathbb{N}$ témoignant de l'équipotence entre les deux ensembles. ■

Il est possible de donner une définition analytique de la fonction réciproque de $\alpha$ définie dans la proposition précédente. Il s'agira donc d'une bijection
<figure><img src="image_18.png" /><figcaption>FIGURE 3.6 – Illustration de la preuve de la proposition 3.5</figcaption></figure>

de $\mathbb{N}^2$ vers $\mathbb{N}$, que nous appellerons $\alpha_2$ et que le lecteur pourra découvrir à travers l'exercice ci-après.

**Exercice 3.7.** ($\star$) Soit $\alpha_2 : \mathbb{N}^2 \to \mathbb{N}$ définie par :

$$ 
\begin{aligned}
\alpha_2(x, y) &= y + \sum_{i=0}^{x+y} i \\
&= y + \frac{(x + y + 1)(x + y)}{2}.
\end{aligned}
$$

1. Montrer que $\alpha_2$ est bijective.

2. Montrer que $\alpha_2(a, b) \ge a$ et $\alpha_2(a, b) \ge b$.

◇

La bijection $\alpha_2$ de l'exercice précédent sera très souvent utilisée dans les développements de ce livre, via la notation suivante.

**Notation**

On note $\langle n, m \rangle$ l'entier sur lequel est envoyé le couple $(n, m)$ via la bijection $\alpha_2$.

Notons que si l'on a une bijection $\alpha_2 : \mathbb{N}^2 \to \mathbb{N}$, on peut définir une bijection $\alpha_3 : \mathbb{N}^3 \to \mathbb{N}$ en prenant simplement $\alpha_3(x, y, z) = \alpha_2(x, \alpha_2(y, z))$. On peut continuer ainsi pour définir des bijections de $\mathbb{N}^n$ vers $\mathbb{N}$ pour tout $n \in \mathbb{N}^*$, ce qui conduit à la notation suivante.
**Notation**

On note $\langle x_1, \dots, x_k \rangle$ l'entier sur lequel est envoyé le $k$-uplet $(x_1, \dots, x_k)$
via la bijection de $\mathbb{N}^k$ vers $\mathbb{N}$ décrite ci-dessus.

Profitons de nos bijections fraîchement introduites pour en déduire le co-
rollaire suivant.

**Corollaire 3.8**

Le produit cartésien de deux ensembles dénombrables est dénombrable.

PREUVE. Soient $A$ et $B$ des ensembles dénombrables et soient $f : A \to \mathbb{N}$ et $g : B \to \mathbb{N}$ des bijections qui en témoignent. La fonction $h : A \times B \to \mathbb{N}$ définie par $h(x, y) = \langle f(x), g(y) \rangle$ est une bijection. $\blacksquare$

Terminons cette section par trois exercices, permettant de manipuler les concepts vus jusqu'ici. Nous attirons en particulier, l'attention sur le premier d'entre eux que l'on utilisera régulièrement dans les développements à venir.

**Exercice 3.9.** $(\star)$ Montrer que $\mathbb{Z}$ est un ensemble dénombrable. En déduire que $\mathbb{Z} \times \mathbb{Z}$ est un ensemble dénombrable et enfin que l'ensemble $\mathbb{Q}$ des nombres rationnels —qui s'écrivent sous la forme $p/q$ pour $p, q \in \mathbb{Z}$ avec $q \neq 0$— est lui aussi dénombrable. $\diamond$

**Exercice 3.10.** $(\star)$ Soit $f : \mathbb{N} \to A$ une fonction surjective vers un ensemble $A$ infini. Montrer que $A$ est dénombrable. $\diamond$

**Exercice 3.11.** $(\star)$ Soit $(B_n)_{n \in \mathbb{N}}$ une suite d'ensembles dénombrables avec des bijections respectives $f_n$ avec $\mathbb{N}$. Montrer que $B = \bigcup_n B_n$ est un ensemble dénombrable.

Attention : si l’on ne dispose pas des bijections $(f_n)_{n \in \mathbb{N}}$, on peut toujours montrer que $B$ est dénombrable, mais il faut utiliser l’*axiome du choix*, afin de choisir uniformément pour chaque $B_n$ une de ses bijections avec $\mathbb{N}$. Nous en reparlerons dans la section 9-4. $\diamond$

**4. Argument diagonal de Cantor**

Attelons-nous à présent au théorème annoncé au début de ce chapitre :
il existe des infinis plus gros que d'autres, et en particulier un infini plus
gros que celui des entiers. Le théorème suivant utilise le fameux argument
diagonal de Cantor, qui sera repris à de très nombreuses occasions et sous
des formes variées tout au long de ce livre.
<table><thead><tr><th>R</th><th>=</th><th>0,</th><th>9 - x<sub>00</sub></th><th>9 - x<sub>11</sub></th><th>9 - x<sub>22</sub></th><th>9 - x<sub>33</sub></th><th>9 - x<sub>44</sub></th><th>9 - x<sub>55</sub></th><th>9 - x<sub>66</sub></th></tr></thead><tbody><tr><td>f(0)</td><td>=</td><td>N<sub>0</sub>,</td><td><b>x<sub>00</sub></b></td><td>x<sub>01</sub></td><td>x<sub>02</sub></td><td>x<sub>03</sub></td><td>x<sub>04</sub></td><td>x<sub>05</sub></td><td>x<sub>06</sub></td></tr><tr><td>f(1)</td><td>=</td><td>N<sub>1</sub>,</td><td>x<sub>10</sub></td><td><b>x<sub>11</sub></b></td><td>x<sub>12</sub></td><td>x<sub>13</sub></td><td>x<sub>14</sub></td><td>x<sub>15</sub></td><td>x<sub>16</sub></td></tr><tr><td>f(2)</td><td>=</td><td>N<sub>2</sub>,</td><td>x<sub>20</sub></td><td>x<sub>21</sub></td><td><b>x<sub>22</sub></b></td><td>x<sub>23</sub></td><td>x<sub>24</sub></td><td>x<sub>25</sub></td><td>x<sub>16</sub></td></tr><tr><td>f(3)</td><td>=</td><td>N<sub>3</sub>,</td><td>x<sub>30</sub></td><td>x<sub>31</sub></td><td>x<sub>32</sub></td><td><b>x<sub>33</sub></b></td><td>x<sub>34</sub></td><td>x<sub>35</sub></td><td>x<sub>36</sub></td></tr><tr><td>f(4)</td><td>=</td><td>N<sub>4</sub>,</td><td>x<sub>40</sub></td><td>x<sub>41</sub></td><td>x<sub>42</sub></td><td>x<sub>43</sub></td><td><b>x<sub>44</sub></b></td><td>x<sub>45</sub></td><td>x<sub>46</sub></td></tr><tr><td>f(5)</td><td>=</td><td>N<sub>5</sub>,</td><td>x<sub>50</sub></td><td>x<sub>51</sub></td><td>x<sub>52</sub></td><td>x<sub>53</sub></td><td>x<sub>54</sub></td><td><b>x<sub>55</sub></b></td><td>x<sub>56</sub></td></tr><tr><td>f(6)</td><td>=</td><td>N<sub>6</sub>,</td><td>x<sub>60</sub></td><td>x<sub>61</sub></td><td>x<sub>62</sub></td><td>x<sub>63</sub></td><td>x<sub>64</sub></td><td>x<sub>65</sub></td><td><b>x<sub>66</sub></b></td></tr><tr><td>...</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>

FIGURE 4.2 – Illustration de l’argument diagonal de Cantor. On construit notre réel $R$ à partir de la diagonale du tableau, la décimale $9 - x_{ii}$ étant nécessairement différente de $x_{ii}$. Notons que le nombre $R$ illustré ici n’est pas exactement celui décrit dans la preuve, mais le résultat est le même : l’élément $R$ n’est pas dans l’image de $f$.

### Théorème 4.1 (Cantor)

L'ensemble des nombres réels est indénombrable.

PREUVE. Le lecteur peut s'aider de la figure 4.2, qui illustre l'argument de la preuve. On raisonne par l'absurde. Supposons au contraire qu'il existe une bijection $f : \mathbb{N} \to \mathbb{R}$. Nous allons construire un nombre réel $R \in \mathbb{R}$ qui n'est pas dans l'image de $f$. On définit simplement $R$ de la manière suivante : la partie entière de $R$ est 0, et pour tout $n$, si la $n$-ième décimale de $f(n)$ est différente de 0, alors la $n$-ième décimale de $R$ est égale à 0. À l'inverse, si la $n$-ième décimale de $f(n)$ est égale à 0, alors la $n$-ième décimale de $R$ est égale à 1.

Il est clair que pour tout entier $n$, notre nombre réel $R$ ne peut être égal à $f(n)$, car la $n$-ième décimale de $R$ est différente de la $n$-ième décimale de $f(n)$. ■

Que nous dit le théorème précédent ? Qu'il y a « plus » de nombres réels que de nombres entiers. Ces ensembles de nombres sont tous les deux infinis, mais l'infini des réels est « plus grand » que celui des entiers. En effet, quand on essaye de faire correspondre un nombre entier à chaque nombre réel, on s'aperçoit qu'il y a toujours des réels « en trop », qui ne correspondent à aucun entier. On a donc $|\mathbb{R}| \not\le |\mathbb{N}|$. Notons que l'on a en revanche $|\mathbb{N}| \le |\mathbb{R}|$, via l'injection identité. On pourra dans ce cas écrire $|\mathbb{N}| < |\mathbb{R}|$, signifiant qu'il y a une injection de $\mathbb{N}$ dans $\mathbb{R}$, mais pas d'injection de $\mathbb{R}$ dans $\mathbb{N}$.
Y a-t-il un infini plus grand que celui des réels ? Cantor a également répondu à cette question, par un argument similaire : pour tout ensemble $A$, il existe un ensemble $B$ tel que $|A| < |B|$.

**Théorème 4.3 (Cantor)**

Pour tout ensemble $A$, l'ensemble $\mathcal{P}(A)$ constitué des sous-ensembles de $A$ est tel que $|A| < |\mathcal{P}(A)|$.

PREUVE. L'ensemble $A$ est subpotent à $\mathcal{P}(A)$, en considérant l'injection qui à tout élément $x \in A$ associe le singleton $\{x\}$. Ainsi, $|A| \le |\mathcal{P}(A)|$. Supposons à présent par l'absurde que $|\mathcal{P}(A)| = |A|$, c'est-à-dire supposons qu'il existe une bijection $f : A \to \mathcal{P}(A)$. Considérons l'ensemble

$$B = \{x \in A : x \notin f(x)\},$$

et soit $y$ tel que $f(y) = B$. Alors, $y \in B$ ssi $y \notin f(y)$, autrement dit ssi $y \notin B$, ce qui est une contradiction. ■

On peut légitimement se demander si la cardinalité des ensembles est toujours comparable : étant donné deux ensembles $A, B$, existe-t-il toujours une injection de l'un dans l'autre ? La réponse à cette question dépend là encore de l'axiome du choix. Nous en reparlerons dans la section 9-4 ainsi que dans la section 27-4.1.

# 5. Réels non calculables

Le théorème de Cantor va nous fournir notre premier argument de l'existence de nombres réels incalculables. Nous utilisons pour la proposition et le corollaire suivants les notions pour le moment informelles de « programme informatique » et de « réel calculable ». Elles seront toutes les deux précisément définies plus loin dans ce livre; considérons pour l'instant qu'un réel est calculable s'il existe un programme informatique qui énumère dans l'ordre la liste infinie de ses décimales.

**Proposition 5.1.** L'ensemble des programmes informatiques est dénombrable. ★

PREUVE. Un programme informatique (écrit dans quelque langage de programmation que ce soit) se présente sous la forme d'une suite finie de caractères, où chaque caractère appartient à un alphabet fini (disons l'ensemble des caractères de la table ascii). Montrons qu'il existe une bijection de $\mathbb{N}$ vers l'ensemble des suites finies de caractères ascii. Pour cela, nous définissons une liste infinie de toutes les suites finies de caractères ascii : on liste d'abord toutes les suites comportant exactement un caractère ascii,
puis toutes les suites comportant deux caractères ascii, puis toutes celles en comportant trois, etc. Il est clair que n'importe quelle suite finie de caractères ascii apparaît quelque part dans notre liste infinie.

Il suffit à présent de retirer de notre liste les suites finies ne correspondant pas à un programme valide. On définit alors l'élément $f(n)$ comme étant le n-ième élément de la liste résultant de cette opération. Il est clair que $f$ est une bijection. En particulier, l'ensemble des programmes informatiques est dénombrable. ■

**Corollaire 5.2**

Il existe des nombres réels qui ne sont pas calculables.

PREUVE. Soit $P$ l'ensemble des programmes informatiques. Supposons que tout réel est calculé par un élément de $P$. Soit $p_1$ le premier programme informatique calculant un réel. Ici « premier » veut dire premier selon l'ordre obtenu via la bijection entre les programmes informatiques et $\mathbb{N}$. Supposons que $p_1, \dots, p_n$ soient définis et calculent tous un réel différent. Soit $p_{n+1}$ le premier programme informatique calculant un réel différent de ceux calculés par $p_1, \dots, p_n$. On définit par récurrence de cette manière la suite $(p_n)_{n \in \mathbb{N}}$. On obtient alors une bijection entre $\mathbb{R}$ et un sous-ensemble infini de $P$. Comme $P$ est dénombrable, ce sous-ensemble infini l'est également, ce qui donne une bijection entre $\mathbb{N}$ et $\mathbb{R}$, et dès lors une contradiction. ■

La preuve du corollaire 5.2 est non constructive : on montre l'existence de nombres incalculables sans en donner d'exemple précis. Ce sera évidemment fait à maintes reprises dans la suite de cet ouvrage, à travers une étude détaillée de différents types de nombres incalculables. Avant de nous y atteler, mentionnons deux ou trois notions importantes concernant l'étude de l'infini menée par Cantor suite à sa découverte.

# 6. Espace de Cantor

Cantor a montré qu'il n'y avait pas de plus grand infini. Parmi tous les infinis possibles, le plus petit est « le dénombrable ». Un autre infini nous intéresse également, celui des nombres réels :

**Définition 6.1.** Un ensemble $A$ est dit avoir la puissance du continu si $|A| = |\mathbb{R}|$. ◇

La puissance du continu caractérise donc l'infini des réels. Cantor conjec- tura qu'il n'y avait pas d'infini strictement compris entre $|\mathbb{N}|$ et $|\mathbb{R}|$, mais
sans réussir à le démontrer. Sa conjecture connue sous le nom *d'hypothèse du continu* sera considérée pendant près d'un siècle comme une des plus importantes questions mathématiques. Gödel montrera en 1938 [74] qu'il n'est pas possible de démontrer que l'hypothèse du continu est fausse, et Cohen mettra un point final à la question en 1963 [37] en montrant qu'il n'est pas possible non plus de montrer que l'hypothèse du continu est vraie : il s'agit d'une question indépendante du reste des mathématiques, que l'on peut considérer vraie ou fausse sans introduire de contradiction. Nous en redisputerons plus en détail dans la section 9-4.

Parmi les ensembles ayant la puissance du continu, on prêtera une attention particulière à l'ensemble des suites infinies de 0 et de 1, qui constituera l'essentiel de notre terrain de jeu tout au long de cet ouvrage. Par suite infinie de 0 et de 1, on entend suite indexée par les entiers, c'est-à-dire des suites de la forme $x_0x_1x_2x_3...$ où chaque $x_i \in \{0,1\}$.

**Définition 6.2.** On appelle *espace de Cantor* l'ensemble des suites infinies de 0 et de 1, on le note $2^N$, et ses éléments seront dénotés via des lettres majuscules, en général $A, B, C, X, Y, Z$. ◇

L'espace de Cantor a la puissance du continu.

**Proposition 6.3.** On a : $|2^N| = |[0, 1]| = |\mathbb{R}|$.

*

**PREUVE.** Montrons d'abord $|[0, 1]| = |\mathbb{R}|$. La fonction identité est une injection de $[0, 1]$ dans $\mathbb{R}$. On vérifie sans peine que la fonction

$$f(x) = \begin{cases} 1/2 + 1/(x+2) & \text{si } x \ge 0 \\ 1/2 - 1/(|x|+2) & \text{si } x < 0 \end{cases}$$

est une injection de $\mathbb{R}$ dans $[0, 1]$. Par le théorème de Cantor-Bernstein (voir le théorème 2.3), on a donc $|[0, 1]| = |\mathbb{R}|$.

Montrons à présent $|2^N| = |[0, 1]|$. Pour définir une injection de $2^N$ dans $[0, 1]$, il convient d'être prudent : certains nombres réels ont deux développements binaires possibles, ainsi $1.00000... = 0.11111...$ — où $0.11111...$ est le nombre décimal 0.99999... écrit en binaire. Il en va de même pour tout nombre réel dont le développement binaire se termine par une infinité de 0 consécutifs : celui-ci a alors un développement binaire équivalent qui se termine par une infinité de 1 consécutifs. On définira donc l'injection $f : 2^N \to \mathbb{R}$ qui à $X$ associe le nombre réel de $[0, 1]$ dont le développement ternaire, c'est-à-dire en base 3, est constitué des bits de $X$. L'usage de la représentation ternaire permet de contourner ces problèmes d'égalités et de rendre ainsi la fonction $f$ injective. L'injection $g : [0, 1] \to 2^N$ est définie en associant à tout réel $r \in [0, 1]$ son développement binaire $R$.
Lorsqu'il existe plusieurs représentations du même nombre réel, on choisira par convention celle se terminant par une infinité de 0. Par le théorème de Cantor-Bernstein, on a donc $|2^N| = |[0, 1]|$. ■

**Notation**

Étant donné $X \in 2^N$ et $n \in \mathbb{N}$, on note $X(n)$ le $n$-ième élément de la suite $X$ que l'on appellera aussi le $n$-ième bit de $X$. Ainsi, si la suite $X$ s'écrit $x_0x_1x_2\dots$, alors $X(0) = x_0$, $X(1) = x_1$, $X(2) = x_2$, ...

Le fait que certains réels aient deux représentations binaires possibles font de $|2^N|$ et $|[0, 1]|$ des espaces topologiquement différents. Par exemple, pour tous $x, y \in \mathbb{R}$ avec $x < y$, il existe un réel $z$ strictement entre les deux. En revanche, si l'on munit $2^N$ de l'ordre lexicographique $<_{lex}$ défini par

$$X <_{lex} Y \text{ si } X(n) < Y(n),$$

où $n$ est le plus petit entier tel que $X(n) \neq Y(n)$, alors les suites infinies

$$X = 0111111\dots \text{ et } Y = 100000\dots$$

n'ont aucun élément strictement entre elles pour cet ordre.

Cette différence est anecdotique du point de vue de la complexité calculatoire des éléments, et il nous arrivera parfois de parler de réel ou de suites binaires infinies indistinctement. La différence a toutefois son importance pour le développement de la calculabilité dans d'autres espaces topologiques que $2^N$. Nous en discuterons brièvement dans la section 22-4.2.

Voyons à présent qu'il existe en revanche une bijection très naturelle entre l'ensemble $\mathcal{P}(\mathbb{N})$ — l'ensemble des parties de $\mathbb{N}$ — et l'espace de Cantor. Ainsi, $\mathcal{P}(\mathbb{N})$ a la puissance du continu.

**Proposition 6.4.** On a : $|2^N| = |\mathcal{P}(\mathbb{N})|$. ★

PREUVE. Soit $f : 2^N \to \mathcal{P}(\mathbb{N})$ la fonction qui à $X \in 2^N$ associe l'ensemble $Y = \{n \in \mathbb{N} : X(n) = 1\}$. La fonction $f$ est clairement une bijection. ■

La bijection entre l'ensemble $\mathcal{P}(\mathbb{N})$ des parties de $\mathbb{N}$ et l'espace de Cantor $2^N$ est tellement élémentaire que l'on peut considérer $\mathcal{P}(\mathbb{N})$ et $2^N$ comme deux représentations du même concept mathématique. Dans la suite, nous parlerons indistinctement de sous-ensemble de $\mathbb{N}$ ou de suite infinie de 0 et de 1, et utiliserons la même notation $2^N$ pour désigner l'ensemble de ces éléments. Ainsi, étant donné $X \in 2^N$ vu comme une suite, on aura $X(n) = 1$ ssi $n$ appartient à $X$ vu comme un ensemble.
## Digression

Le nom « espace de Cantor » vient sans doute du concept éponyme d'ensemble triadique de Cantor. On définit $A_0 = [0, 1]$, puis $A_1$ est $A_0$ moins son tiers central :

$$A_1 = [0, 1/3] \cup [2/3, 1].$$

Puis $A_2$ est $A_1$ moins le tiers central de chacun de ses intervalles :

$$A_2 = [0, 1/9] \cup [2/9, 1/3] \cup [2/3, 7/9] \cup [8/9, 1].$$

De manière générale, pour passer de $A_n$ à $A_{n+1}$, on enlève le tiers central de chacun des intervalles de $A_n$. L'ensemble triadique de Cantor est le résultat à la limite, de l'application de cette opération, c'est-à-dire l'ensemble $\bigcap_{n \in \mathbb{N}} A_n$.

L'espace de Cantor $2^\mathbb{N}$ défini plus haut, est topologiquement équivalent à l'ensemble triadique de Cantor. En particulier, chaque point de $\bigcap_{n \in \mathbb{N}} A_n$ peut être décrit comme une suite de 0 et de 1 de la manière suivante : le n-ième bit d'un point correspond à déterminer s'il est à droite ou à gauche du n-ième tiers que l'on enlève de l'intervalle courant. On peut également voir l'espace de Cantor comme l'ensemble des réels de $[0, 1]$ dont la représentation ternaire évite le chiffre 1.
<figure><img src="image_19.png" /></figure>
Première partie

Calculabilité classique
<figure><img src="image_20.png" /></figure>
Chapitre 3

Fondements de la calculabilité

Notre objectif est de mener une étude mathématique de la calculabilité. Pour ce faire, il est d'usage de définir mathématiquement ce que l'on entend par fonction calculable. Cette quête d'une définition formelle capturant ce concept épistémologique a constitué la genèse de la calculabilité, et abouti à ce que l'on appelle de nos jours la thèse de Church-Turing. Cette thèse énonce que tout processus calculable peut être exécuté avec une machine de Turing, un modèle de calcul imaginé par Alan Turing en 1936 et qui peut être considéré comme un précurseur des ordinateurs modernes. D'autres approches que celle des machines de Turing permettent de capturer la notion de fonction calculable, parmi lesquelles nous citerons les fonctions générales récursives et le λ-calcul. Ces différents modèles seront présentés plus en détail dans l'interlude sur la thèse de Church-Turing (voir le chapitre 6), et nous adopterons pour ce chapitre une approche moins formelle.

1. Fonctions calculables

En calculabilité, le formalisme des machines de Turing tend à servir de
modèle de référence, non seulement pour des raisons historiques — Turing
fut le premier à avoir su convaincre la communauté que son modèle captu-
rait tous les processus calculables — mais également parce que ce modèle
met en relief la notion d'étape atomique de calcul, ce qui ouvre la porte à
la théorie de la complexité. Il est de coutume de débuter l'étude de la cal-
culabilité par celle de ses modèles de calcul, et de prouver leur équivalence,
afin de se convaincre de la robustesse de la notion de fonction calculable
et du bien-fondé des définitions. Il s'agit d'un développement assez long
et fastidieux. Aussi est-il facile d'être rebuté par cette étape à l'issue de
laquelle on croit trop facilement — à tort — que la calculabilité se résume
à de complexes et rébarbatives techniques de codage.

Nous avons donc fait le choix de rompre avec la tradition, et reporter la
définition et l'étude mathématique des modèles de calcul au chapitre 6, afin
de faciliter le premier contact avec la calculabilité, et d'accéder plus direct-
ement à ses concepts fondamentaux. L'avènement des ordinateurs et la
démocratisation de l'enseignement de la programmation ont ancré durable-
ment la notion d'algorithme dans la culture scientifique. Nous adopterons
donc la définition informelle suivante.

**Définition 1.1.** Une fonction $f : \mathbb{N} \to \mathbb{N}$ est calculable si elle peut être définie par un algorithme, ou autrement dit programmée dans un langage de programmation moderne. ◇

Il s'ensuit de notre choix pédagogique que les preuves de nos premiers théorèmes feront largement appel à l'intuition des propriétés que l'on attend d'une fonction calculable. Il s'agit cependant de théorèmes à part entière, dans le sens où il est possible de les prouver à partir des définitions formelles du chapitre 6.

## Entiers en informatique

Nous nous intéressons essentiellement aux fonctions de $\mathbb{N}$ dans $\mathbb{N}$. Dans la plupart des langages de programmation standard, les entiers sont bornés. Pour notre définition théorique, il est important de prendre en compte tous les entiers.

**Algorithmes.** Afin de s'accorder sur ce que l'on entend par un langage de programmation moderne ou algorithme, listons-en les principaux aspects, qui seront repris formellement dans la section 6-3 pour notre définition des programmes structurés sur le modèle des machines à registres.

(1) Le langage doit pouvoir manipuler les entiers, à l'aide de constantes, de variables entières, et des opérations arithmétiques usuelles, à savoir l'addition, la soustraction, la multiplication, et la division entière. Le lecteur pourra y ajouter d'autres types, comme les chaînes de caractères ou les nombres à virgule flottante, sans que cela ne change la puissance de calcul.

(2) Le langage doit pouvoir manipuler des expressions booléennes, et effectuer des opérations de comparaison sur les entiers.

(3) Le langage doit contenir les structures de contrôle usuelles, à savoir des instructions conditionnelles de type `if ... then ... else ...` et
des boucles « *for* » et « *while* », qui se répètent tant qu'une certaine condition est vraie.

(4) Nous supposerons que la mémoire de la machine n'est pas bornée, et qu'elle peut en utiliser autant que nécessaire (notamment pour lire son entrée, qui peut être un entier arbitrairement grand).

### Types de données

Le point (1) insiste sur le fait que l'ajout d'autres types de données que le type entier est superflu. C'est vrai à condition bien sûr de considérer que nos entiers peuvent être arbitrairement grands (pour encoder par exemple de grandes chaînes de caractères), ce qui sera par convention toujours le cas. Le lecteur pourra trouver un exemple d'encodage de tableaux par des entiers dans la proposition 6-3.26.

### Mémoire non bornée

On peut être surpris par le point (4) ci-dessus, qui autorise une mémoire non bornée. Insistons sur le fait que l'on ne s'autorise pas une mémoire infinie pour autant : un calcul qui se termine n'a effectué qu'un nombre fini d'opérations et n'a donc pu utiliser qu'une quantité finie de mémoire. Simplement, on ne s'occupe pas en calculabilité de la complexité en espace des algorithmes.

**Exemples.** Avant de commencer l'étude formelle des fonctions calculables et de leurs propriétés, listons quelques exemples de fonctions calculables, afin de commencer à nous former une intuition.

(1) Les opérations arithmétiques usuelles sont calculables. En particulier, l'addition, la multiplication, la soustraction et la division entière sont calculables.

(2) La fonction qui à *n* associe le *n*-ième nombre premier est calculable, de même que la décomposition d'un nombre en ses facteurs premiers.

(3) La fonction qui, prenant en paramètre une liste de positions de villes, renvoie un des chemins les plus courts passant par toutes ces villes une seule fois, est calculable<fnref n="1" />.

Inversement, il existe comme nous allons le voir de nombreuses fonctions non calculables. Cependant, tandis qu'il suffit de donner un algorithme pour montrer qu'une fonction est calculable, montrer qu'une fonction n'est pas calculable demande souvent un raisonnement plus élaboré, car il ne suffit pas que la fonction n'ait pas d'algorithmes connu; il faut montrer qu'il est théoriquement impossible de la programmer. Chacun des énoncés suivants est donc un théorème à part entière.

<footnote n="1">1. Il s'agit du problème bien connu du *voyageur de commerce*.</footnote>
(1) La fonction qui prend en entrée un programme informatique (codé par un entier ou une chaîne de caractères), et décide si son exécution va un jour s'arrêter, n'est pas calculable (voir le théorème 7.8).

(2) La fonction qui prend en entrée une formule dans le langage de l'arithmétique (par exemple, $\langle \forall x \forall y \forall z x^3+y^3 \neq z^3 \rangle$), et renvoie 1 s'il existe une démonstration mathématique de cette formule dans le système axiomatique de l'arithmétique, et 0 sinon, n'est pas calculable (voir le théorème 9-3.9).

(3) La fonction qui prend en entrée une équation diophantienne, i.e. une équation à coefficients entiers — par exemple $3x^2+2xy+4y^2=0$ — et décide si cette équation admet une solution entière, n'est pas calculable (voir le théorème 12-1.2).

**Fonctions partielles.** Comme expliqué dans l'encadrement $\langle$ Entiers en informatique $\rangle$ ci-dessus, on se restreindra en général aux programmes prenant en paramètre un entier, et retournant un autre entier si le calcul se termine. Il est essentiel de noter que les fonctions engendrées par les programmes informatiques sont *partielles*, au sens où le calcul peut ne jamais s'arrêter sur certaines de leurs entrées. Cette partialité est due aux structures de contrôle de type $\langle$ while $\rangle$ dont la condition de terminaison peut n'être jamais satisfaite, comme le montre l'exemple suivant, qui calcule — de la pire manière possible — la racine carrée d'un entier :

```pascal
function Racine(n) {
    r = 0;
    while (r*r != n) {
        r = r+1;
    }
    return r;
}
```

Si $n$ n'est pas le carré d'un nombre entier, la boucle `while` va s'exécuter à l'infini, et le programme ne renverra jamais de valeur. Lorsque le programme ne s'arrête pas sur une entrée $n$, on considère que la fonction de $\mathbb{N}$ dans $\mathbb{N}$ qui lui est associée n'est pas définie sur $n$. Le domaine de définition de la fonction partielle associée à un programme est donc l'ensemble des entrées sur lesquelles il s'arrête. Les fonctions définies par des programmes sont appelées *fonctions partielles calculables*. Lorsque le programme s'arrête sur toutes ses entrées, la fonction engendrée est alors appelée *fonction totale calculable*, ou tout simplement *fonction calculable*.
### Notation

Si $f$ et $g$ sont deux fonctions partielles, on notera $f(x) = g(x)$ pour signifier soit que $f$ et $g$ sont toutes les deux définies et renvoient la même valeur sur $x$, soit que ni $f$ ni $g$ ne sont définies sur $x$.

**Codes.** Dans notre étude mathématique, nous représenterons les programmes informatiques par des entiers, en supposant une fonction de codage fixée. Par programmes informatiques, il faut comprendre ici une suite finie de caractères — supposée avoir du sens dans un langage de programmation choisi au préalable. Concrètement, on dira qu'un entier $e$ code pour un programme $P$ si $e$ est l'entier codé par la représentation binaire de la chaîne de caractères correspondant au programme $P$. En particulier, ce codage est injectif et intuitivement calculable. Notons que l'on pourrait imaginer beaucoup d'autres codages possibles. Nous en verrons un autre de manière détaillée dans la preuve du théorème 6-3.27. En attendant, celui-ci conviendra parfaitement.

### Notation

On note $\Phi_e : \mathbb{N} \to \mathbb{N}$ la fonction partielle définie par le programme informatique de code $e$.

On supposera que tout entier $e$ code pour un programme valide. En pratique, il existe dans tous les langages de programmation des chaînes de caractères correspondant à des programmes mal formés. Certains entiers $e$ codent pour des suites de caractères inintelligibles. Si c'est le cas, on peut alors s'en rendre compte (cela correspond à avoir une erreur de syntaxe quand on essaye de compiler un programme) et considérer que $e$ correspond alors à un programme qui ne s'arrête pas.

### Notation

Soient $\Phi_e : \mathbb{N} \to \mathbb{N}$ une fonction partielle calculable et $x \in \mathbb{N}$ un entier. On écrira $\Phi_e(x) \downarrow$ si le programme codé par $e$ s'arrête sur l'entrée $x$ (nécessairement après un nombre fini d'étape de calcul) et renvoie un résultat entier. Dans le cas inverse, on écrira $\Phi_e(x) \uparrow$.

Le domaine de définition de la fonction partielle calculable $\Phi_e : \mathbb{N} \to \mathbb{N}$ est donc $\{x \in \mathbb{N} : \Phi_e(x) \downarrow\}$. Si $\Phi_e(x) \downarrow$, on écrira parfois $\Phi_e(x) \downarrow= y$ pour signifier que le programme de code $e$ s'arrête sur l'entrée $x$ et renvoie l'entier $y$. À l'inverse, on écrira parfois $\Phi_e(x) \uparrow \neq y$ pour signifier l'opposé, c'est-à-dire $\Phi_e(x) \uparrow \lor \Phi_e(x) \downarrow \neq y$.
**Temps de calcul.** Tout langage de programmation vient avec une notion d'étape d'exécution et de temps de calcul. Une étape d'exécution est une opération atomique du langage, indécomposable en sous-étapes. Elle correspond à une instruction élémentaire du langage. La notion d'étape d'exécution induit celle de temps de calcul, qui se définit par le nombre d'étapes d'exécution réalisées depuis le lancement du calcul. Lorsqu'un programme s'arrête sur une entrée, son temps de calcul est fini.

**Notation**

Soient $\Phi_e : \mathbb{N} \to \mathbb{N}$ une fonction partielle calculable et $x, t \in \mathbb{N}$ deux entiers. On écrira $\Phi_e(x)[t] \downarrow$ si le programme codé par $e$ s'arrête avant $t$ étapes de calcul. Dans le cas inverse, on écrira $\Phi_e(x)[t] \uparrow$.

Notons que $\Phi_e(x) \downarrow$ ssi il existe un temps de calcul $t$ tel que $\Phi_e(x)[t] \downarrow$. En outre, si $\Phi_e(x)[t] \downarrow$, alors $\Phi_e(x)[s] \downarrow$ pour tout $s \ge t$.

**Remarque**

On sera amené à manipuler des fonctions calculables à plusieurs paramètres. Pour un entier $n \in \mathbb{N}^*$ fixé, on désignera comme ci-dessus par $\Phi_e : \mathbb{N}^n \to \mathbb{N}$ la fonction partielle à $n$ paramètres entiers codée par $e$ et l'on écrira $\Phi_e(x_1, \dots, x_n) \downarrow= y$ si le programme de code $e$ s'arrête sur les entrées $x_1, \dots, x_n$ et renvoie l'entier $y$.

## 2. Ensembles calculables

L'adjectif « calculable » s'applique naturellement aux fonctions; en effet, comme décrit plus haut, tout entier $e$ code pour un programme auquel correspond une fonction partielle calculable. Le plus souvent cependant, quand on parle de fonctions calculables, on considérera qu'il s'agit de fonctions totales.

**Définition 2.1.** Soit $n \in \mathbb{N}^*$. Une fonction $f : \mathbb{N}^n \to \mathbb{N}$ est calculable s'il existe un code de programme $e$ tel que, pour tout $(x_1, \dots, x_n)$, on a $\Phi_e(x_1, \dots, x_n) \downarrow= f(x_1, \dots, x_n)$. $\diamond$

La calculabilité peut également être utilisée pour mesurer la complexité descriptive des objets mathématiques dénombrables, et en particulier celle des ensembles d'entiers. Intuitivement, un ensemble d'entiers $E \subseteq \mathbb{N}$ est calculable s'il peut être décrit par un processus calculable. Un ensemble étant totalement spécifié par ses éléments, il est calculable si sa fonction caractéristique est calculable.
**Définition 2.2.** Soit $n \in \mathbb{N}^*$. Un ensemble $A \subseteq \mathbb{N}^n$ est calculable s'il existe un code de programme $e$ tel que, pour tous $x_1, \dots, x_n$, on a

$$ \triangleright \Phi_e(x_1, \dots, x_n) \downarrow = 1 \text{ ssi } (x_1, \dots, x_n) \in A. $$

$$ \triangleright \Phi_e(x_1, \dots, x_n) \downarrow = 0 \text{ ssi } (x_1, \dots, x_n) \notin A. $$

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

On appellera parfois *prédicats* les sous-ensembles de $\mathbb{N}^n$, en utilisant alors la notation $A(x_1, \dots, x_n)$ pour signifier $(x_1, \dots, x_n) \in A$. Le terme de prédicat vient de la vision de $A \subseteq \mathbb{N}^n$ non comme un ensemble, mais comme une propriété des $n$-uplets d'entiers. Ainsi, $A(x_1, \dots, x_n)$ signifie que le $n$-uplet $(x_1, \dots, x_n)$ a la propriété $A$. À l'inverse, $\neg A(x_1, \dots, x_n)$ signifie que le $n$-uplet $(x_1, \dots, x_n)$ n'a pas la propriété $A$.

**Exercice 2.3.** Montrer que la bijection de couplage définie dans la pro-
position 2-3.5 et l'exercice 2-3.7, qui à $(a, b) \in \mathbb{N}^2$ associe $\langle a, b \rangle \in \mathbb{N}$, est
calculable. Montrer que les fonctions inverses $\pi_0, \pi_1$ telles que $a = \pi_0(\langle a, b \rangle)$
et $b = \pi_1(\langle a, b \rangle)$ sont elles aussi calculables.
$\diamond$

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

**Exercice 2.4.** Soit $A \subseteq \mathbb{N}^2$ un prédicat calculable. Montrer que les ensembles :

$$ (1) \{ (x, y) \in \mathbb{N}^2 : \forall z < y (x, z) \in A \} $$

$$ (2) \{ (x, y) \in \mathbb{N}^2 : \exists z < y (x, z) \in A \} $$

sont eux aussi calculables.

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

Ensemble récursif

Historiquement, les ensembles calculables étaient appelés *récursifs* en raison du paradigme de calcul des fonctions générales récursives dans lequel les définitions par récurrence jouent un rôle prépondérant (voir le chapitre 6). Peu à peu, avec l'amélioration de notre compréhension de la notion de calcul, la terminologie du domaine a évolué. On peut cependant régulièrement voir les termes de théorie de la récursion et d'ensemble récursif pour parler de calculabilité et d'ensemble calculable.

3. Programme universel

Le modèle de calcul imaginé par Turing en 1936 consiste à définir une
machine pour chaque fonction calculable. Si l'on compare une machine de
Turing à un dispositif physique, cela consiste, pour chaque tâche que l'on
veut accomplir, à créer un robot exécutant cette tâche spécifique.

Nous allons maintenant énoncer un premier théorème fondamental de la
calculabilité et prouvé par Turing dans son article original : l'existence
d'une machine de Turing *universelle*, capable de simuler toutes les autres machines de Turing. Ce travail est parfois considéré comme précurseur de l'architecture de von Neumann <fnref n="2" />, dont l'un des aspects est le stockage des programmes dans la mémoire. En informatique moderne, ce théorème peut être vu comme énonçant l'existence d'un programme informatique *universel*, permettant de simuler tous les autres programmes informatiques.

**Théorème 3.1**

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

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

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

En pratique, un programme universel existe très concrètement dans beaucoup de langages. Par exemple, en Java, il s'agit simplement de la machine virtuelle qui compile et exécute n'importe quel programme écrit en Java. Pour les langages n'utilisant pas de machine virtuelle, un programme universel sera simplement la donnée d'un interpréteur qui décompose le programme qu'il reçoit en une série d'instructions qu'il exécute pas à pas. Si un tel programme est bien entendu complexe à concevoir, il ne devrait faire aucun doute pour le programmeur qu'il s'agit de quelque chose de tout à fait possible : il s'agit simplement d'une machine virtuelle. Le lecteur pourra consulter la preuve du théorème 6-3.27, qui démontre l'existence d'un programme universel pour le modèle de calcul spécifique des machines à registre.

L'existence d'un tel programme nous permet de définir des fonctions qui font des manipulations sur des codes avant de les exécuter, ou exécutent dynamiquement des codes passés en paramètre. Par exemple,

$$ f(x, y) = \Phi_{x+1}(y+2) $$

est une définition valide, car elle est équivalente à $f(x, y) = \Phi_e(x+1, y+2)$, où $\Phi_e$ est le programme universel.

## 4. Théorème SMN

Le théorème SMN est notre premier théorème sur la manipulation des codes de programmes informatiques. Il ne s'agit pas de quelque chose de conceptuellement bien difficile. Soit $\Phi_e : \mathbb{N}^{m+n} \to \mathbb{N}$ la fonction de code $e$. Alors, étant donné $x_1, \dots, x_m$, on peut transformer de manière calculable

<footnote n="2">2. Qui est à peu de choses près toujours celle utilisée de nos jours.</footnote>
notre code *e* en un code *a* tel que le calcul $\Phi_a(y_1, \dots, y_n)$ donne le même résultat que le calcul $\Phi_e(x_1, \dots, x_m, y_1, \dots, y_n)$. Le point important est que la transformation de *e* en *a* est calculable en fonction de *e* et de $x_1, \dots, x_m$.

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

Pour tous $n, m \in \mathbb{N}^*$, il existe une fonction totale calculable

$$S_n^m : \mathbb{N}^{m+1} \to \mathbb{N},$$

telle que pour tous $e, x_1, \dots, x_m, y_1, \dots, y_n$,

$$\Phi_{S_n^m(e, x_1, \dots, x_m)}(y_1, \dots, y_n) = \Phi_e(x_1, \dots, x_m, y_1, \dots, y_n).$$

**PREUVE.** Décrivons la fonction $S_n^m$. Étant donné $e, x_1, \dots, x_m$, décodeur $e$ pour obtenir le programme $P_e$. Modifier calculatoirement le programme $P_e$ pour lui ajouter des instructions assignant « en dur » les valeurs $x_1, \dots, x_m$ aux variables correspondantes, puis calculer le code du nouveau programme. Par exemple, si le programme $\Phi_e : \mathbb{N}^4 \to \mathbb{N}$ est

```matlab
function MonProgramme(x1, x2, x3, x4) {
    // CODE
}
```

Le programme $\Phi_{S_2^2(e,5,3)}$ correspond à la chaîne

```matlab
function MonProgramme2(x3, x4) {
    x1 = 5;
    x2 = 3;
    // CODE
}
```

On utilisera dans la suite le théorème SMN sans faire appel à lui explicite-ment, avec des phrases comme « pour tout $x$, soit $e_x$ le code du programme qui prend $y$ en entrée et fait ... [quelque chose qui dépend de $x$ et $y$] », étant entendu alors que le processus pour obtenir $e$ à partir de $x$ est calculable. On dit aussi dans ce cas que le processus est *uniforme* en $x$.

**Codage acceptable**

Le théorème d'existence d'un programme universel et le théorème SMN ne sont pas valides pour n'importe quelle fonction de codage. Rappelons ici celle que nous utilisons : chaque programme $P$ est codé par l'entier correspondant à la représentation binaire de la chaîne de caractère qui contient $P$.
Rogers [183] a prouvé que toute fonction de codage satisfaisant le théorème de programme universel et le théorème SMN était le résultat d'une permutation calculable de ce codage canonique. Il existe cependant d'autres codages des fonctions partielles calculables ne satisfaisant pas ces théorèmes. En particulier, Friedberg [64] a défini un codage calculable de toutes les fonctions partielles calculables sans répétition. Cela n'est bien entendu pas le cas pour notre codage, pour lequel une même fonction partielle a une infinité de codes différents. C'est ce que nous nous apprêtons à voir avec le lemme 5.1.

# 5. Lemme de remplissage

Le lemme de remplissage est utile de temps à autre et indique que pour tout programme informatique $e$, il existe une infinité de programmes équivalents, dont on peut de surcroît calculer le code à partir de $e$ : il suffit de rajouter des instructions qui ne servent à rien.

## Lemme 5.1 (Lemme de remplissage)

Il existe une fonction calculable totale $h: \mathbb{N}^2 \to \mathbb{N}$ telle que pour tous $e, n \in \mathbb{N}$, on a $h(e, n) \ge n$, et $\Phi_{h(e,n)} = \Phi_e$. $\star$

## PREUVE

Étant donné le code $e$ et un entier $n$, décodeer $e$ pour obtenir le programme $P_e$. Ajouter $n$ instructions inutiles à $P_e$, puis coder le nouveau programme en un entier $i$.

Par exemple, si le langage possède une instruction `skip` qui n'effectue rien, alors il suffit d'ajouter au programme une suite d'instructions `skip` comme suit :

```pascal
function MonProgramme(x) {
  // CODE
  skip;
  skip;
  ...
}
```

■

Notons bien que $\Phi_{h(e,n)}$ et $\Phi_e$ sont égales en tant que fonctions mathématiques, mais ont des codes informatiques différents.
# 6. Théorème du point fixe de Kleene

Le théorème du point fixe de Kleene, appelé parfois recursion theorem en anglais, est bien plus subtil que le théorème SMN. Stephen Cole Kleene est considéré avec Kurt Gödel, Alan Turing, Emil Post et Alonzo Church, son professeur, comme un des fondateurs de la calculabilité. Il formalise avec Post la notion de degré d'insolubilité, que l'on appellera plus tard degré Turing et qui sera définie précisément dans le chapitre 4. Parmi ses travaux les plus remarquables, figurent la définition et l'étude des ensembles hyperarithmétiques et des ordinaux calculables [114], que nous verrons dans la partie IV et pour lesquels nous aurons besoin de créer des programmes informatiques ayant accès à leur propre code.

La notion peut sembler douteuse : comment peut-on utiliser dans la définition d'un objet *A* l'objet *A* lui-même ? Les auto-références mènent souvent à des paradoxes. Nous allons cependant voir que dans le cas de programmes informatiques, l'accès à son propre code est tout à fait valide, et même bien utile dans certains cas. Nous verrons un exemple remarquable d'utilisation du théorème du point fixe dans la preuve du théorème 19-1.7. Voyons plus précisément de quoi il s'agit. Le théorème stipule que pour toute fonction qui modifie des programmes, il existe un programme dont le comportement n'est pas modifié par la fonction.

<figure><img src="image_24.png" /><figcaption>Stephen Cole Kleene, 1909-1994</figcaption></figure>

**Théorème 6.2**

Pour toute fonction totale calculable $f : \mathbb{N} \to \mathbb{N}$, il existe $e \in \mathbb{N}$ tel que pour tout $n$,

$$ \Phi_{f(e)}(n) = \Phi_e(n). $$

Avant de passer à la preuve, voyons un peu en quoi cette mystérieuse affirmation permet de créer des programmes ayant accès à leur propre code. Supposons qu'un programme *M* utilise une variable *var* ayant été initialisée à une certaine valeur au début de son exécution. On peut alors définir une fonction totale calculable *f* qui prend un entier *n* en paramètre, et renvoie le code du programme *M*, qui commence son exécution avec *var* initialisée à *n*. D'après le théorème du point fixe, il y a une valeur *e* telle que les programmes de code *e* et *f(e)* ont le même comportement. Donc, *e*
est un code de programme équivalent à celui du programme M s'exécutant avec la variable var initialisée à e : il y a une version de M qui peut accéder à son propre code. Voici, plus formellement, ce que nous venons d'énoncer.

### Corollaire 6.3

Pour toute fonction partielle calculable $g : \mathbb{N}^2 \to \mathbb{N}$, il existe $e \in \mathbb{N}$ tel que pour tout $n$, on a

$$ \Phi_e(n) = g(e, n) $$

PREUVE. Soit $i$ tel que $\Phi_i(x, n) = g(x, n)$ pour tous $x, n$. Par le théorème SMN (voir le théorème 4.1), pour tous $x, n$, on a $\Phi_{S_2^1(i,x)}(n) = \Phi_i(x, n)$. Soit $f$ la fonction définie par $f(x) = S_2^1(i, x)$. Par le théorème du point fixe (voir le théorème 6.2), il existe $e$ tel que, pour tout $n$, $\Phi_{f(e)}(n) = \Phi_e(n)$. En particulier, $\Phi_e(n) = \Phi_{f(e)}(n) = \Phi_i(e, n) = g(e, n)$. ■

La preuve du théorème 6.2, bien que concise, est un peu obscure; c'est pourquoi nous fournissons au préalable un morceau de code dont l'objectif est de donner l'intuition au programmeur de la manière dont on peut écrire un programme ayant accès à son propre code. L'exemple est ici donné dans le langage Javascript.

Dans ce qui suit, les deux points de suspension doivent chacun contenir le même code, peu importe lequel. En Javascript, les « backquotes » délimitent une chaîne de caractères sur plusieurs lignes. La fonction `replace` remplacera la première occurrence de `'#'` par le contenu de la variable `v`.

```javascript
function fct() {
    let v=`
function fct() {
    let v='#
    v = v.replace '#', v)
    ... //mon code
}`
    v = v.replace ('#', v)
    ... //mon code
}
```

L'exécution de ce programme se fera avec la variable `v` ayant pour contenu le programme lui-même, à ceci près que les « backquotes » se transforment alors en simple « quotes ». Il est bien entendu possible de faire en sorte que la variable `v` contienne *exactement* le programme, mais cela rendrait l'exemple beaucoup moins compréhensible. Ayant pour objectif de donner une intuition et non une preuve, nous avons conservé les choses ainsi. Pas-
sons justement à présent à la preuve formelle de notre théorème, dans le cadre des notations et principes que nous avons définis jusque-là.

PREUVE DU THÉORÈME 6.2. Soit $a$ le code d'une machine à un paramètre, qui sur l'entrée $n$ renvoie le code d'une machine à un paramètre $m$, qui effectue les opérations suivantes.

(1) Elle lance le calcul de $f(\Phi_n(n))$.

(2) Si l'on a $f(\Phi_n(n)) \downarrow$, alors elle renvoie le résultat du calcul de la machine de code $f(\Phi_n(n))$ sur l'entrée $m$ (et sinon ne s'arrête pas).

Formellement, $a$ est tel que, pour tous $n, m \in \mathbb{N}$,

$$ \Phi_{\Phi_a(n)}(m) = \Phi_{f(\Phi_n(n))}(m). $$

On fait ici un léger abus de notation : si $\Phi_n(n) \uparrow$, alors $m \mapsto \Phi_{f(\Phi_n(n))}(m)$ dénote la fonction nulle part définie. Notez que $\Phi_a$ est une fonction totale : pour tout $n$, dans le calcul de $\Phi_a(n)$, on ne cherche pas à faire les étapes (1) et (2), mais seulement à calculer le code d'une machine qui les fait. La démonstration qu'un tel code $a$ existe est donnée par le théorème SMN, voici comment. La fonction $(n, m) \mapsto \Phi_{f(\Phi_n(n))}(m)$ est calculable (éventuellement partielle), et il y a donc un code $b$ tel que

$$ \Phi_b(n, m) = \Phi_{f(\Phi_n(n))}(m). $$

D'après le théorème SMN, il y a une fonction totale calculable $s$ telle que $\Phi_{s(b,n)}(m) = \Phi_{f(\Phi_n(n))}(m)$. Comme $s$ est totale calculable, il y a un code $a$ tel que $\Phi_a(n) = s(b, n)$.

Le point fixe sera alors $\Phi_a(a)$. En effet, on a

$$ \forall m, \Phi_{\Phi_a(a)}(m) = \Phi_{f(\Phi_a(a))}(m). $$

Cela conclut la preuve.

■

## Théorème de point fixe et paradoxe

Comme expliqué plus haut, le théorème du point fixe de Kleene permet de concevoir des programmes *auto-référents*, c'est-à-dire des programmes qui peuvent lire leur code au cours de l'exécution, et adapter leur comportement en fonction. La capacité à faire de l'auto-référence est souvent source de paradoxes.

Le paradoxe du barbier, par exemple, raconte l'histoire d'un barbier philanthrope qui décida de raser tous les gens qui ne se rasaient pas eux-mêmes. Dût-il se raser lui-même ? Paradoxe... En mathématiques, le paradoxe de Russell suit le même schéma : soit $E$ l'ensemble de tous les ensembles qui n'appartiennent pas à eux-mêmes. Par exemple, $\mathbb{N}$ n'est pas un entier, donc $\mathbb{N} \notin \mathbb{N}$, donc $\mathbb{N} \in E$. La question problématique est alors « est-ce que $E \in E$ ? »
Pourquoi le théorème du point fixe de Kleene n'engendre-t-il pas de
paradoxe ? Si l'on essaye de suivre le même schéma que les deux para-
doxes précédents, on va définir une fonction Φ<sub>e</sub> qui connaît son code e,
et donc peut décider, pour tout entrée n, d'exécuter Φ<sub>e</sub>(n) et de ren-
voyer une valeur différente de celle renvoyée par Φ<sub>e</sub>(n). On aurait
donc Φ<sub>e</sub>(n) ≠ Φ<sub>e</sub>(n). La solution vient de la partialité des fonctions :
en effet, Φ<sub>e</sub> ne sera tout simplement pas définie en n et s'exécutera à
l'infini.

Le lecteur désireux d'explorer les possibilités du théorème du point fixe
pourra s'atteler à l'exercice suivant, dont l'objet est de démontrer le théo-
rème de Rice, qui sera abordé plus en détail dans la section 5-6.

**Exercice 6.4.** (★) Soit $A \subseteq \mathbb{N}$ tel que $A \neq \mathbb{N}, A \neq \emptyset$ et tel que $A$ est calculable.

1. Montrer qu'il existe une fonction calculable $f$ telle que l'on a $x \in A$ ssi $f(x) \notin A$.

2. En utilisant le théorème du point fixe, en déduire qu'il existe *i*, *j* tels que $\Phi_i = \Phi_j$, avec $i \in A$ et $j \notin A$.

3. En déduire qu'il n'existe pas de prédicats calculables $A$ tels que $e \in A$ ssi $e$ est le code d'un programme qui fait la multiplication par 2.

4. Généraliser la question précédente pour montrer le théorème de Rice : pour tout « comportement non trivial », il n'est pas possible de calculer l'ensemble des codes de programmes ayant ce comportement. Formellement : soit un prédicat $P \subseteq \mathbb{N}$ avec $P \neq \mathbb{N}$ et $P \neq \emptyset$ tel que, pour tous $e_1, e_2$ pour lesquels $\Phi_{e_1} = \Phi_{e_2}$, on a $e_1 \in P \leftrightarrow e_2 \in P$. Alors, $P$ n'est pas calculable. ◇

**7. Ensembles calculatoirement énumérables**

La calculabilité place le « calculable » comme puissance calculatoire de
référence. Il s'agit de la plus faible notion calculatoire que ce paradigme
permet d'identifier. Comme nous l'avons vu, un ensemble *E* est calculable
s'il existe une procédure qui, étant donné un élément, indique si cet élément
appartient à *E* ou non. La procédure doit toujours s'arrêter et donner une
réponse correcte.

Il existe cependant un certain nombre de problèmes mathématiques qui peuvent s'exprimer naturellement sous forme d'ensembles dont les éléments sont énumérables par une procédure calculable, mais dans le désordre. Ces ensembles sont appelés calculatoirement énumérables.
Par exemple, soit $E$ l'ensemble des théorèmes mathématiques. Il n'existe pas de procédure qui, étant donné une formule mathématique, renvoie vrai ou faux selon que cette formule soit prouvable ou non. Cependant, il est possible d'énumérer les théorèmes, en listant toutes les chaînes de caractères possibles, testant s'il s'agit d'une preuve valide, et si c'est le cas, en énumérant la conclusion de la preuve (nous en discuterons plus en détail dans le chapitre 9).

Nous allons maintenant définir formellement la notion d'ensemble calculatoirement énumérable sous une forme qui peut sembler éloignée de la définition informelle que nous venons de donner. Nous verrons à travers la proposition 7.2 que ces définitions coïncident.

**Définition 7.1.** Un ensemble $A \subseteq \mathbb{N}$ est calculatoirement énumérable (c. e.) s'il existe un code de programme $e$ tel que $n \in A \leftrightarrow \Phi_e(n) \downarrow$, pour tout $n \in \mathbb{N}$. $\diamond$

Notons que les ensembles calculatoirement énumérables étaient historiquement appelés *récursivement énumérables*. Il est encore fréquent de voir des articles utilisant l'ancienne terminologie, et en particulier l'abréviation r. e. au lieu de c. e.

On peut voir la machine de code $e$ comme un processus qui énumère $A$: pour chaque entier $n$, on cherche un entier $t$ tel que $\Phi_e(n)$ s'arrête en $t$ étapes de calcul. Si un tel $t$ est trouvé, on énumère alors $n$ dans notre ensemble. Sachant qu'il existe une infinité d'entiers, il convient de fixer un ordre d'exécution pour ne réaliser qu'un nombre fini de calculs à chaque étape. L'idée est de décomposer étape par étape comme suit.

1. Tester si $\Phi(0)[0] \downarrow$.

2. Tester si $\Phi(0)[1] \downarrow$ ou $\Phi(1)[1] \downarrow$.

3. Tester si $\Phi(0)[2] \downarrow$ ou $\Phi(1)[2] \downarrow$ ou $\Phi(2)[2] \downarrow$.

4. ...

La première fois que l'on trouve une étape $t$ telle que $\Phi(n)[t] \downarrow$ pour un certain entier $n$, on énumère ce dernier. Une telle énumération peut se voir comme une fonction calculable $f: \mathbb{N} \to \mathbb{N}$ où $f(n)$ est le $n$-ième élément énuméré dans $A$. Cette idée est reprise dans la preuve de la proposition suivante.

**Proposition 7.2.** Un ensemble infini $A$ est calculatoirement énumérablessi il existe une fonction totale calculable $f: \mathbb{N} \to \mathbb{N}$ injective telle que

$$f(\mathbb{N}) = A. \quad \star$$
PREUVE. Soit $A$ un ensemble calculatoirement énumérable infini, et soit $e$ tel que $\Phi_e(n) \downarrow$ ssi $n \in A$. On définit la fonction calculable $f : \mathbb{N} \to \mathbb{N}$ comme suit.

▷ Pour calculer $f(0)$, on cherche le plus petit $t$ tel que $\Phi_e(s)[t] \downarrow$ pour un certain $s \le t$, et l'on renvoie alors le plus petit tel entier $s \le t$.

▷ Pour calculer $f(n+1)$, on lance d'abord le calcul de $f(i)$ pour tout $i \le n$, puis on cherche le plus petit $t$ tel que $\Phi_e(s)[t] \downarrow$ pour un certain $s \le t$ tel que $s$ est différent de chaque $f(i)$ pour $i \le n$, et l'on renvoie alors le plus petit tel entier $s \le t$.

Le processus pour déterminer $f(n)$ est bien calculable, et comme notre ensemble calculatoirement énumérable est infini, la fonction $f$ s'arrêtera sur toutes ses valeurs. Il est alors clair que $f(\mathbb{N}) = A$.

Supposons à présent que $f(\mathbb{N}) = A$ pour une fonction totale calculable $f$. On définit la fonction $g$ qui sur $n$ cherche le plus petit $t$ tel que $f(t) = n$, et ensuite s'arrête (et sinon cherche indéfiniment sans jamais s'arrêter). On a bien $g(n) \downarrow$ ssi $\exists t f(t) = n$. ■

Il devrait être clair pour le lecteur qu'un ensemble calculable est calculatoirement énumérable.

**Exercice 7.3.** Montrer que tout ensemble calculable est calculatoirement énumérable. ◇

Nous allons voir que l'inverse n'est pas forcément vrai : il y a des ensembles calculatoirement énumérables qui ne sont pas calculables. La proposition suivante donne plus précisément la connexion entre ces deux concepts.

**Proposition 7.4.** Un ensemble $A$ est calculable ssi $A \in \mathbb{N} \setminus A$ sont tous les deux calculatoirement énumérables. ★

PREUVE. Soit $A$ un ensemble calculable. D'après l'exercice 7.3, il est calculatoirement énumérable. Par ailleurs, l'ensemble $\mathbb{N} \setminus A$ est lui aussi calculable, et par conséquent calculatoirement énumérable.

Supposons à présent que l'on ait deux codes $e_1, e_2$ tels que $\Phi_{e_1}(n) \downarrow$ ssi $n \in A$ et $\Phi_{e_2}(n) \downarrow$ ssi $n \in \mathbb{N} \setminus A$. On définit la fonction calculable $f(n)$ qui cherche le plus petit $t$ tel que $\Phi_{e_1}(n)[t] \downarrow$ ou tel que $\Phi_{e_2}(n)[t] \downarrow$, puis renvoie 1 dans le premier cas et 0 dans le deuxième. Il est clair que la fonction $f$ calcule l'ensemble $A$. ■

Si un ensemble calculatoirement énumérable n'est pas en général calculable, il peut être approximé par une suite croissante d'ensembles uniformément calculables, au sens suivant. On dit qu'une suite d'ensembles $A_0, A_1, \dots$ est *uniformément calculable* s'il existe une fonction $f : \mathbb{N} \times \mathbb{N} \to \{0, 1\}$ calculable et telle que, pour tous $x, n$, on a $f(x, n) = 1$ ssi $x \in A_n$.
**Définition 7.5.** Une approximation c. e. d'un ensemble $A$ est une suite uniformément calculable d'ensembles $A_0, A_1, \dots$ telle que $A_n \subseteq A_{n+1}$ pour tout $n$, et $\bigcup_n A_n = A$. ◇

**Proposition 7.6.** Un ensemble $A$ est calculatoirement énumérable si, et seulement si, il possède une approximation c. e. ★

**PREUVE.** Supposons que $A$ soit c. e. Par définition, il existe un code de programme $e$ tel que $x \in A \leftrightarrow \Phi_e(x) \downarrow$, pour tout $x \in \mathbb{N}$. Soit $A_0, A_1, \dots$ la suite uniformément calculable d'ensembles définie par $A_n = \{x : \Phi_e(x)[n] \downarrow\}$. Il est clair que $A_n \subseteq A_{n+1}$, car si la machine $\Phi_e$ s'arrête sur une entrée $x$ avant $n$ étapes, elle s'arrêtera avant $n+1$ étapes.

Supposons maintenant que l'ensemble $A$ possède une approximation c. e., à savoir $A_0, A_1, \dots$. Soit le programme $\Phi_e$ qui, pour une entrée $x$, calcule $A_0(x)$, puis $A_1(x)$, puis $A_2(x)$, et ainsi de suite, jusqu'à ce que $A_n(x)=1$ pour un $n$ et s'arrête à ce moment-là. Si $A_n(x)=0$ pour tout $n$, alors $\Phi_e(x) \uparrow$, sinon $\Phi_e(x) \downarrow$. Par construction, $\{x : \Phi_e(x) \downarrow\} = \bigcup_n A_n = A$. ■

**Notation**

Étant donné un ensemble c. e. $A$, on notera $A[0], A[1], \dots$ une approximation c. e. de $A$ fixée. En particulier, $A[s]$ est l'approximation de $A$ au temps $s$. Par convention, $A[s]$ est un ensemble fini avec $\max A[s] < s$ si $A[s] \neq \emptyset$. On utilisera parfois aussi la notation $A_s$ à la place de $A[s]$.

Comme nous l'avons dit, il existe des ensembles calculatoirement énumérables qui ne sont pas calculables. L'exemple canonique est connu sous le nom de « problème de l'arrêt ».

**Définition 7.7.** On appelle le problème de l'arrêt ou plus simplement l'arrêt, que l'on note $\emptyset'$, l'ensemble :

$$ \emptyset' = \{n \in \mathbb{N} : \Phi_n(n) \downarrow\}. \quad \diamond $$

Alan Turing démontre en 1936 que l'arrêt n'est pas calculable, en utilisant un argument diagonal, comme celui introduit par Cantor pour démontrer la non-dénombrabilité des réels. Avant d'en donner une preuve mathématique, nous en donnons l'intuition via un peu de code utilisant la syntaxe Java.

Supposons par l'absurde que nous ayons à notre disposition une fonction boolean $\text{Halt}(\text{String } p, \text{String } v)$ qui renvoie true si la méthode se trouvant dans la chaîne $p$ s'arrête quand elle est exécutée avec le programme $v$, et renvoie false sinon. Comme d'habitude, si $p$ contient une
chaîne de caractère ne correspondant pas à une fonction valide ou ne correspondant pas à une fonction prenant un paramètre de type String, alors Halt renvoie false. Considérons le programme suivant.

```pascal
function Diagonale(x) {
  if (Halt(x, x)) {
    while (true); //boucle infinie
  } else {
    return; //fin
  }
}
```

Que renvoie l'exécution du programme Diagonale avec comme paramètre une chaîne de caractère x correspondant au programme Diagonale lui-même ? On voit que l'on arrive à un paradoxe :

▷ si Halt(x,x) renvoie true, alors Diagonale ne s'arrête pas sur Diagonale comme paramètre;

▷ dans le cas inverse, Diagonale s'arrête sur Diagonale comme paramètre.

Ainsi, la méthode Halt ne tient pas ses promesses.

## Théorème 7.8

L'arrêt est un ensemble calculatoirement énumérable qui n'est pas calculable.

**PREUVE.** La fonction partielle $f: n \mapsto \Phi_n(n)$ est clairement calculable, et l'on a $f(n) \downarrow$ ssi $\Phi_n(n) \downarrow$. Aussi a-t-on, par définition, $\emptyset' = \{n : f(n) \downarrow\}$. Donc, $\emptyset'$ est calculatoirement énumérable.

Supposons maintenant par l'absurde que $\emptyset'$ soit un ensemble calculable. En particulier, d'après la proposition 7.4, l'ensemble $N \setminus \emptyset'$ est calculatoirement énumérable, et il existe un code $e$ tel que $n \in N \setminus \emptyset'$ ssi $\Phi_e(n) \downarrow$. Alors, pour tout $n$,

$$ \Phi_e(n) \downarrow \leftrightarrow n \in N \setminus \emptyset' \leftrightarrow \Phi_n(n) \uparrow. $$

En particulier, pour $n = e$,

$$ \Phi_e(e) \downarrow \leftrightarrow e \in N \setminus \emptyset' \leftrightarrow \Phi_e(e) \uparrow, $$

ce qui est une contradiction. L'arrêt n'est donc pas calculable, et en particulier le complémentaire de l'arrêt n'est pas calculatoirement énumérable. ■

Nous invitons le lecteur à considérer les exercices suivants, qui permettent de réfléchir un peu sur les ensembles calculatoirement énumérables.
**Exercice 7.9.** (⋆) Un ensemble infini est calculatoirement énumérable dans l'ordre s'il existe une fonction totale $f : \mathbb{N} \to \mathbb{N}$ telle que $f(\mathbb{N}) = A$ et telle que $f(n) < f(n + 1)$. Montrer que si un ensemble infini $A$ est calculatoirement énumérable dans l'ordre, alors $A$ est calculable. ◇

**Exercice 7.10.** (⋆) Montrer que tout ensemble calculatoirement énumérable infini contient un sous-ensemble calculable infini. ◇

**Exercice 7.11.** (⋆⋆) Deux ensembles $A$ et $B$ sont calculatoirement inséparables si $A \cap B = \emptyset$ et si aucun ensemble calculable $C$ ne permet de séparer $A$ et $B$; autrement dit, aucun ensemble calculable $C$ n'est tel que $A \subseteq C$ et $C \cap B = \emptyset$. Montrer qu'il existe deux ensembles $c. e. calculatoirement inséparables$. ◇

**Exercice 7.12.** (⋆⋆) Montrer qu'étant donné $A, B \subseteq \mathbb{N}$ deux ensembles calculables, l'ensemble $D_{A,B} = \{x - y : x \ge y \text{ et } x \in A \text{ et } y \in B\}$ n'est pas nécessairement calculable.

Indication.– Montrer que pour tout ensemble $c. e. C \subseteq \mathbb{N}$, il existe deux ensembles calculables $A, B \subseteq \mathbb{N}$ tels que $x \in C \text{ ssi } 2^x \in D_{A,B}$. ◇

Certaines personnes — une petite minorité, rassurez-vous — auront peut-être intégré avec une très grande facilité tout ce qui a été vu jusqu'ici, au point sans doute de s'ennuyer un peu. C'est à celles-là que s'adresse l'exercice suivant, qui devrait les occuper un petit moment...

**Exercice 7.13.** (⋆⋆⋆) (Friedberg [64]). Un ensemble $c. e. X$ est maximal si $\mathbb{N} \setminus X$ est infini et si tout ensemble $c. e. Y \supseteq X$ est tel que $Y \setminus X$ est fini ou tel que $\mathbb{N} \setminus Y$ est fini. Montrer qu'il existe un ensemble $c. e. \text{maximal}$.

Indication.– On note $W_e$ l'ensemble $c. e. \text{donné par } \{n \in \mathbb{N} : \Phi_e(n) \downarrow\}$. On pourra commencer par trouver un processus uniforme qui sur chaque $e \in \mathbb{N}$ associe un code $d$ tel que $\mathbb{N} \setminus W_d$ est infini, et tel que si $W_d \subseteq W_e$; alors, soit $W_e$ est fini, soit $\mathbb{N} \setminus W_e$ est fini. ◇
<figure><img src="image_25.png" /></figure>
Chapitre
# 4

Degrés Turing

Un ensemble non calculable peut être vu comme un problème insoluble : il n'existe pas d'algorithme permettant de décider si un entier appartient ou non à cet ensemble. Un des objectifs de la calculabilité est d'étudier et de comprendre l'univers des problèmes insolubles, via différentes comparaisons et classifications. On introduit pour cela différents outils. Le plus important d'entre eux est l'objet de ce chapitre et trouve sa genèse dans « Systems of logic based on ordinals » [226], le fameux article d'Alan Turing présentant ses travaux de thèse, et sera formalisé et étudié plus tard par Post [181] puis Post et Kleene [118] : étant donné un ensemble non calculable A, on imagine pouvoir l'utiliser comme « oracle » afin d'augmenter la puissance de calcul de nos machines. On dira alors que deux ensembles sont dans le même degré d'insolubilité ou dans le même degré *Turing*, si chacun peut se calculer avec un algorithme utilisant l'autre comme « oracle ».

1. Les chaînes finies

Avant d'entrer dans le vif du sujet, nous devons introduire un peu de vocabulaire et de notation sur les chaînes binaires. Formellement, une chaîne binaire est une fonction partielle de $N$ vers $\{0, 1\}$ dont le domaine de définition est un segment initial de $N$. De manière plus informelle, il s'agit d'une suite finie de $0$ et de $1$.

**Définition 1.1.** On note $2^{<N}$ l'ensemble des suites finies de $0$ et de $1$. Les variables $\sigma, \tau, \rho$ seront normalement utilisées pour dénoter des éléments de $2^{<N}$, que l'on appellera généralement des *chaînes*.
Ces suites seront manipulées via les symboles suivants :

▷ ϵ : la chaîne vide, de taille 0

▷ $i^n$ pour $i \in \{0, 1\}$ : une suite de $n$ répétitions du bit $i$

▷ $\sigma\tau$ ou $\sigma \frown \tau$ : la concaténation de $\sigma$ et $\tau$

▷ $\sigma \preceq \tau$ : la chaîne $\sigma$ est un préfixe de $\tau$, c'est-à-dire $\exists\rho$ tel que $\sigma\rho = \tau$

▷ $\sigma \prec \tau$ : la chaîne $\sigma$ est un préfixe strict de $\tau$, c'est-à-dire $\exists\rho \neq \epsilon$ tel que $\sigma\rho = \tau$

▷ $|\sigma|$ : la taille de $\sigma$

▷ $\sigma(n)$ pour $n < |\sigma|$ : la valeur du n-ième bit de $\sigma$, en commençant à 0

▷ On dira que deux chaînes $\sigma, \tau$ sont incompatibles si l'on n'a ni $\sigma \preceq \tau$ ni $\tau \preceq \sigma$ (on écrira aussi $\sigma \not\preceq \tau$ et $\tau \not\preceq \sigma$). Si à l'inverse $\sigma \preceq \tau$ ou $\tau \preceq \sigma$, les deux chaînes $\sigma$ et $\tau$ sont compatibles. ◇

On identifiera parfois un bit $i \in \{0, 1\}$ avec la chaîne de longueur 1 dont l'unique bit est $i$. Ainsi, on notera $\sigma i$ ou $\sigma \frown i$ la concaténation d'une chaîne $\sigma$ et d'un bit $i$. Suivant les définitions précédentes, $|\epsilon| = 0$, et pour toute chaîne $\sigma$ non vide, le premier et dernier bit sont respectivement $\sigma(0)$ et $\sigma(|\sigma| - 1)$. Les chaînes et les suites infinies peuvent se combiner.

**Définition 1.2.** On adoptera les notations suivantes pour $\sigma \in 2^{<N}$ et $X \in 2^N$ :

▷ $\sigma X$ : la concaténation de $\sigma$ et $X$

▷ $\sigma \prec X$ : la chaîne $\sigma$ est un préfixe de $X$, c'est-à-dire $\exists Y \in 2^N \sigma Y = X$

▷ $X \upharpoonright_n$ pour $n \ge 0$ : le préfixe de $X$ de taille $n$. ◇

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

## 2. Calcul avec oracle

Intuitivement, un calcul avec oracle, par exemple $A \subseteq N$, est simple à comprendre : il s'agit d'un calcul qui peut à tout moment utiliser une instruction qui « pose une question » à l'oracle, de la forme : « est-ce que $n$ appartient à $A$ ? » Cette instruction peut s'apparenter à un appel de fonction, qui renvoie toujours la bonne réponse.

Si l'oracle utilisé n'est pas calculable, on peut donc écrire des programmes informatiques qui calculent, à l'aide de cet oracle, des objets normalement non calculables, à commencer par l'oracle lui-même. Notre objectif est à présent d'étudier les ensembles d'entiers du point de vue de la puissance de calcul qu'ils fournissent quand ils sont utilisés comme oracles.
**Définition 2.1.** Une fonctionnelle Turing ou simplement une fonctionnelle est une fonction calculable par un algorithme ayant la possibilité d'utiliser, en plus de son jeu d'instruction habituel, une instruction permettant de savoir si un entier *n* appartient à l'oracle. ◇

Une fonctionnelle prend donc un ou plusieurs paramètres entiers, comme pour les fonctions calculables, et un ou plusieurs paramètres d'oracles, ici des ensembles d'entiers (on parle aussi parfois de paramètres << réels >> quand on les voit comme le développement binaire de nombres réels). On appellera aussi *paramètres du premier ordre* les paramètres entiers et *paramètres du second ordre* les paramètres qui sont des ensembles d'entiers.

**Notation**

On note $\Phi_e(A, n)$ ou $\Phi_e^A(n)$ le résultat du calcul de la fonctionnelle $\Phi_e$ avec l'oracle $A$ et sur l'entrée $n$. On écrira de la même manière $\Phi_e(A, n) \downarrow$, $\Phi_e(A, n) \uparrow$, $\Phi_e(A, n)[t] \downarrow$, $\Phi_e(A, n)[t] \uparrow$ pour signifier que la fonctionnelle $\Phi_e$ respectivement s'arrête, ne s'arrête pas, s'arrête en temps inférieur à $t$, ne s'arrête pas en temps inférieur à $t$, avec l'oracle $A$ et sur l'entrée $n$.

Afin d'avoir une vision uniforme, on suppose à présent que l'on ne travaille qu'avec des fonctionnelles. Il est facile de voir que les fonctions calculables sont exactement celles qui le sont par des fonctionnelles utilisant l'ensemble vide comme oracle (ou n'importe quel autre ensemble calculable).

**Définition 2.2.** Un ensemble $A$ est dit $X$-calculable ou calculable relativement à $X$ s'il est calculable par une fonctionnelle Turing utilisant $X$ comme oracle. Un ensemble $A$ est dit calculatoirement énumérable relativement à $X$ si c'est le domaine de définition d'une fonctionnelle Turing utilisant $X$ comme oracle. ◇

La notion d'oracle se généralise aux fonctions. Avec un oracle $f : \mathbb{N} \to \mathbb{N}$, un calcul consiste à ajouter la fonction $f$ aux primitives du langage de programmation. Ainsi, le programme pourra à tout moment interroger $f$ sur des entrées pour en connaître les résultats. On peut par conséquent parler d'ensemble $f$-calculable s'il est calculable par une fonctionnelle Turing utilisant $f$ comme oracle. De manière équivalente, un ensemble est $f$-calculable s'il est $G_f$-calculable, où $G_f \in 2^{\mathbb{N}}$ est un encodage du graphe de la fonction $f$ par un élément de $2^{\mathbb{N}}$, par exemple avec $\langle n, m \rangle \in G_f$ ssi $f(n) = m$.

**Notation**

On écrira aussi $X$-c. e. pour signifier calculatoirement énumérable relativement à $X$.
**Exemple 2.3.** Supposons par exemple que l’on dispose d’un oracle $X$ inclus dans $\mathbb{N}$ tel que la fonction $f$ qui à $n$ associe le $n$-ième élément de $X$ croisse suffisamment vite pour borner le temps d’arrêt des programmes informatiques. Formellement : $\Phi_e(e) \downarrow$ implique $\Phi_e(e)[f(e)] \downarrow$ pour tout $e \in \mathbb{N}$. Alors, il est aisé de créer une fonctionnelle Turing permettant de calculer $\emptyset'$ à partir de $X$ : pour savoir si $e \in \emptyset'$, il suffit de parcourir $X$ jusqu’à trouver son $e$-ième élément $f(e)$, puis de calculer $\Phi_e(e)$ durant $f(e)$ étapes de calcul. Si $\Phi_e(e)[f(e)] \downarrow$, alors $e \in \emptyset'$. Sinon, $e \notin \emptyset'$.

# 3. Relativisation des preuves

La plupart des arguments de calculabilité s'appliquent aux machines à oracle en remplaçant « machine » par « machine avec un oracle $X$ ». Cette opération purement syntaxique que l'on appelle relativisation (à un oracle) donne donc gratuitement un schéma de résultats similaires, paramétrés par un oracle $X$. Prenons l'exemple de l'indécidabilité du problème de l'arrêt, en remplaçant la notion de calcul par celle de calcul avec oracle $X$.

## Théorème 3.1

*Pour tout oracle $\mathbf{X}$, l'ensemble $Y = \{n : \Phi_n^{\mathbf{X}}(n) \downarrow\} n$ est pas $\mathbf{X}$-calculable.*

**PREUVE.** La fonction partielle $f: n \mapsto \Phi_n^{\mathbf{X}}(n)$ est clairement $\mathbf{X}$-calculable, et l'on a $f(n) \downarrow \text{ssi } \Phi_n^{\mathbf{X}}(n) \downarrow$. Aussi a-t-on, par définition, $Y = \{n \in \mathbb{N} : f(n) \downarrow\}$. Donc, $Y$ est $\mathbf{X}$-calculatoirement énumérable.

Supposons maintenant par l'absurde que l'ensemble $Y$ est $\mathbf{X}$-calculable. En particulier, d'après la proposition 3-7.4 relativisée à $\mathbf{X}$, l'ensemble $\mathbb{N} \setminus Y$ est $\mathbf{X}$-calculatoirement énumérable, et il existe un code $e$ tel que $n \in \mathbb{N} \setminus Y$ ssi $\Phi_e^{\mathbf{X}}(n) \downarrow$. On a alors pour tout $n$

$$ \Phi_e^{\mathbf{X}}(n) \downarrow \leftrightarrow n \in \mathbb{N} \setminus Y \leftrightarrow \Phi_n^{\mathbf{X}}(n) \uparrow. $$

En particulier, pour $n = e$, on a

$$ \Phi_e^{\mathbf{X}}(e) \downarrow \leftrightarrow e \in \mathbb{N} \setminus Y \leftrightarrow \Phi_e^{\mathbf{X}}(e) \uparrow, $$

ce qui est une contradiction. Donc, $Y$ n'est pas $\mathbf{X}$-calculable, et en particulier le complémentaire de $Y$ n'est pas $\mathbf{X}$-calculatoirement énumérable. ■

Il convient cependant d'être précautionneux lors de la relativisation d'un argument. En effet, certaines définitions masquent des appels à des machines, et leur définition doit alors être également relativisée. Par exemple, si l'on
définit le problème de l’arrêt comme l’ensemble $\{n : \Phi_n(n) \downarrow\}$, la relativisation de l’énoncé « Le problème de l’arrêt n’est pas calculable » n’est pas « Pour tout $X$, le problème de l’arrêt n’est pas $X$-calculable », mais « Pour tout $X$, le problème de l’arrêt relativisé à $X$ n’est pas $X$-calculable », où le « problème de l’arrêt relativisé à $X$ » est en fait défini comme l’ensemble $\{n : \Phi_n^X(n) \downarrow\}$.

De manière générale, la relativisation d'un théorème s'obtient en ajoutant un oracle $X$ à chaque machine, et en remplaçant calculable par $X$-calculable. C'est par exemple le cas pour une relativisation naïve du théorème SMN.

**Théorème 3.2 (Théorème SMN relativisé - version 1)**

Pour tout oracle $X$, et pour tous entiers $n$ et $m$ non nuls, il existe une fonction $X$-calculable totale $S_n^m : \mathbb{N}^{m+1} \to \mathbb{N}$ telle que pour tout $e$,

$$ \Phi_{S_n^m(e,x_1,\dots,x_m)}^X(y_1,\dots,y_n) = \Phi_e^X(x_1,\dots,x_m,y_1,\dots,y_n). $$

Une analyse de la preuve du théorème SMN révèle cependant que la fonction $S_n^m$ ne dépend pas de l'oracle $X$, car elle effectue des manipulations purement syntaxiques sur la machine. Il est donc possible de formuler une version relativisée plus forte du théorème SMN, où la fonction $S_n^m$ est calculable, bien que la version précédente soit également valide.

**Théorème 3.3 (Théorème SMN relativisé - version 2)**

Pour tout oracle $X$, pour tous $n, m \in \mathbb{N}^*$ il existe une fonction calculable totale $S_n^m : \mathbb{N}^{m+1} \to \mathbb{N}$ telle que pour tout $e$,

$$ \Phi_{S_n^m(e,x_1,\dots,x_m)}^X(y_1,\dots,y_n) = \Phi_e^X(x_1,\dots,x_m,y_1,\dots,y_n). $$

## Digression

La relativisation des arguments est un phénomène empirique qui d'une certaine manière reflète notre compréhension partielle de la notion de calcul. Toutefois, et notamment en théorie de la complexité, les preuves ne se relativisent pas nécessairement. L'exemple emblématique est la question de la séparation des classes de complexité P et NP. Chacune de ces classes peut se relativiser à un oracle. Baker, Gill, et Solovay [9] ont montré qu'il existait des oracles $X$ pour lesquels $P^X = NP^X$ et d'autres pour lesquels $P^X \neq NP^X$. Il est alors nécessaire pour résoudre la question P vs NP d'utiliser un argument qui ne se relativise pas. Il s'agit en calculabilité de quelque chose de tout à fait inhabituel, mais pas nécessairement en complexité où nous avons d'autres exemples de problèmes résolus qui
ne se relativisent pas. On sait par exemple que les classes IP et PSPACE coïncident [196], tout en étant capable de produire des oracles $X$ pour lesquels $IP^X \neq PSPACE^X$ [60].

# 4. Propriété de l’usage

Étant donné un calcul $\Phi_e(A, n)$ sur un oracle $A$, il est clair que si l’on suppose que $\Phi_e(A, n) \downarrow$, alors la fonctionnelle $\Phi_e$ n’a utilisé qu’une partie finie de l’oracle $A$ pour renvoyer le résultat : cela découle simplement du fait qu’un calcul s’effectue toujours en un nombre fini d’étapes. Cela nous amène à définir la notion de calcul avec des oracles finis.

## Notation

Étant donné une suite finie $\sigma \in 2^{<N}$, on note $\Phi_e(\sigma, n) \downarrow$ ou $\Phi_e^\sigma(n) \downarrow$ pour signifier que le calcul s’arrête sur l’entrée $n$ et avec $\sigma$ comme morceau d’oracle, la fonctionnelle n’ayant alors besoin pour son calcul que de poser à l’oracle des questions auxquelles $\sigma$ peut répondre, c’est-à-dire des questions d’appartenance de $i$ à l’oracle pour des entiers $i$ strictement inférieurs à $|\sigma|$.

Dans la notation précédente, si le calcul a besoin d’accéder à des valeurs de l’oracle qui dépassent la taille de $\sigma$, alors on note $\Phi_e(\sigma, n) \uparrow$ ou $\Phi_e^\sigma(n) \uparrow$. La partie finie de l’oracle $A$ interrogée jusqu’à ce que le calcul $\Phi_e(A, n)$ termine s’appelle l’usage du calcul.

**Proposition 4.1 (Propriété de l’usage).** Soient $\Phi_e$ une fonctionnelle Turing, $X$ un oracle et $n \in \mathbb{N}$ une entrée. Alors, $\Phi_e(X, n) \downarrow$ si, et seulement si, il existe un préfixe fini $\sigma \prec X$ tel que $\Phi_e(\sigma, n) \downarrow$. ★

Nous verrons dans la section 8-2 que la propriété de l’usage correspond au concept de continuité sur l’espace de Cantor. Malgré sa simplicité conceptuelle, la propriété de l’usage joue un rôle primordial en calculabilité. Nous en ferons par exemple une utilisation forte dans la section 8 sur la méthode des extensions finies.

**Définition 4.2.** Étant donné une fonctionnelle $\Phi$ et un oracle $X$, on note $\text{use}_\Phi^X : \mathbb{N} \to \mathbb{N}$ la fonction partielle $X$-calculable qui sur $n$ renvoie la taille minimale du préfixe de $X$ nécessaire à l’arrêt du calcul de $\Phi(X, n)$. ◇

## Remarque

D’après la propriété de l’usage, toute fonctionnelle Turing $\Gamma$ peut être représentée par l’ensemble $c. e. W$ des triplets $(\sigma, x, y)$ tels que
si $(\sigma, x, y) \in W$, alors $\Gamma^\sigma(x) \downarrow= y$. Une telle énumération satisfait la propriété de cohérence suivante : pour tous $(\sigma, x, y) \in W$ et $(\tau, x, y') \in W$ tels que $\sigma < \tau$, on a $y = y'$.

**Exercice 4.3.** Montrer que si $Y$ est $X$-calculable et $Z$ est $Y$-calculable, alors $Z$ est $X$-calculable. ◇

# 5. Degrés Turing

Les machines à oracle induisent une notion de calculabilité relative. Informellement, un ensemble $Y$ est $X$-calculable si $X$ est au moins aussi puissant que $Y$, au sens où tout ce qui est calculable par $Y$ l'est également par $X$. Cela donne lieu à la *réduction Turing*.

**Définition 5.1 (Réduction Turing).** Pour tous ensembles $X, Y \subseteq \mathbb{N}$, on écrit $X \leq_T Y$ — et l'on dit que $X$ est *Turing réductible* à $Y$ — si $X$ est $Y$-calculable. On écrit $X <_T Y$ si $X \leq_T Y$ mais $Y \not\leq_T X$. ◇

La réduction Turing forme un pré-ordre sur les ensembles d'entiers, c'est-à-dire que cette relation est réflexive et transitive. En effet, si $Y$ est $X$-calculable et $Z$ est $Y$-calculable, $Z$ est $X$-calculable. Ce n'est cependant pas un ordre partiel sur les ensembles, car la réduction Turing n'est pas anti-symétrique. Par exemple, les ensembles des nombres pairs et des nombres impairs sont trivialment mutuellement calculables puisqu'ils sont tous deux calculables, mais ils ne sont pas égaux en tant qu'ensembles d'entiers.

Il est cependant possible de transformer ce pré-ordre en un ordre partiel en identifiant tous les ensembles mutuellement calculables. Cela donne la notion de *degré Turing* qui représente une puissance calculatoire plus robuste que la notion d'ensemble pour la réduction Turing.

**Définition 5.2.** On écrit $X \equiv_T Y$ si $X \leq_T Y$ et $Y \leq_T X$. On dira alors que $X$ et $Y$ sont *Turing-équivalents*. On appelle *degrés Turing* les classes d'équivalences de la relation $\equiv_T$. Le degré Turing d'un ensemble $X$ est $\text{l'ensemble deg}_T(X) = \{Y : Y \equiv_T X\}$. ◇

Par construction, si $X \leq_T Y$, alors tout élément dans le degré Turing de $Y$ calcule n'importe quel élément dans le degré Turing de $X$. La réduction de Turing induit donc un ordre partiel sur les degrés Turing, que l'on notera tout simplement $\leq$.
**Notation**

On notera ($\mathcal{D}, \leqslant$) l'ensemble des degrés Turing $\mathcal{D}$ partiellement ordonné par $\leqslant$. On utilisera en général les lettres **a**, **b**, **c**, **d**, **e**,... pour désigner ses éléments. On écrira parfois $X \leqslant_T \mathbf{d}$ pour $\deg_T(X) \leqslant \mathbf{d}$.

**Exercice 5.3.** Montrer que si $X \equiv_T Y$ et $A \equiv_T B$, on a alors $X \leqslant_T A$ si, et seulement si, $Y \leqslant_T B$. ◇

Deux ensembles sont donc Turing-équivalents s'ils ont la même puissance calculatoire, et la relation $\leqslant$ permet de comparer non plus des ensembles, mais des degrés de puissance calculatoire. En particulier, les degrés Turing sont stables par variations finies, au sens où si $X \in \mathbf{d}$ et $Y =^* X$, alors $Y \in \mathbf{d}$. Ici, $Y =^* X$ signifie que $X$ et $Y$ ne diffèrent que sur un nombre fini de bits.

**Exercice 5.4.** Montrer que les degrés Turing sont stables par variation finie. ◇

Une grande partie de la calculabilité classique consiste à comprendre la structure ($\mathcal{D}, \leqslant$). L'ordre $\leqslant$ est-il total sur $\mathcal{D}$ ? Est-il bien fondé ? Si c'est un ordre partiel, quelle est la taille maximale d'un ensemble ne contenant que des éléments deux à deux incomparables ? Nous verrons que la structure des degrés Turing est d'une grande richesse, mais aussi d'une grande complexité. Commençons par quelques observations immédiates.

Tout d'abord, les degrés Turing possèdent un élément minimal, à savoir le degré des ensembles calculables. On le notera **0**. Nous avons ensuite la proposition suivante.

**Proposition 5.5.** Tout degré Turing est dénombrable. ★

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

**PREUVE.** Soit **d** un degré Turing et soit $X \in \mathbf{d}$. En particulier,

$$ \mathbf{d} = \deg_T(X) = \{Y : X \equiv_T Y\} \subseteq \{\{n : \Phi_e^X(n) \downarrow= 1\} : e \in \mathbb{N}\}, $$

donc **d** est fini ou dénombrable. Par ailleurs, **d** est stable par variations finies, donc est infini. Ainsi, **d** est dénombrable. ■

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

La collection des sous-ensembles de $\mathbb{N}$ étant indénombrable, et chacun ap-
partenant à un degré Turing, il s'ensuit de la proposition précédente que
les degrés Turing sont en quantité indénombrable. Supposons en effet le
contraire. Alors, d'après l'exercice 2-3.11, la réunion de tous les degrés Tu-
ring serait un ensemble dénombrable, en tant que réunion dénombrable
d'ensembles dénombrables. Comme cette réunion est égale à $2^\mathbb{N}$, on a là
une contradiction. Remarquons que l'exercice 2-3.11 utilise l'axiome du
choix (dont nous parlerons en détail dans la section 9-4). Celui-ci n'est
toutefois pas nécessaire : nous verrons plusieurs constructions effectives
de fonctions $f : 2^N \to 2^N$ (voir l'exercice 8-5.4 ou l'exercice 8-5.3) telles que $f(X)$ et $f(Y)$ sont dans des degrés Turing différents pour tous $X \neq Y$, ce qui fait de $f$ une injection de $2^N$ dans les degrés Turing et montre en particulier $|2^N| \le |D|^1$.

**Définition 5.6.** La jointure effective de deux ensembles $A$ et $B$ est l'ensemble $A \oplus B = \{2n : n \in A\} \cup \{2n + 1 : n \in B\}$ (notons que la réunion entre les deux ensembles est disjointe). ◇

La jointure effective de deux ensembles est une façon d'encoder l'information de chaque ensemble de manière à pouvoir la décodeur calculatoirement. Il existe bien entendu de nombreuses manières d'encoder deux ensembles en un seul, la jointure effective étant la plus directe et efficace, au sens suivant.

**Proposition 5.7.** Soient $A$ et $B$ deux ensembles. Alors, $\deg_T(A \oplus B)$ est la borne supérieure des degrés $\deg_T(A)$ et $\deg_T(B)$, c'est-à-dire que tout degré au-dessus de $\deg_T(A)$ et de $\deg_T(B)$ est aussi au-dessus de $\deg_T(A \oplus B)$. Ainsi, toute paire de degrés Turing $c$ et $d$ admet une borne supérieure que l'on notera $c \cup d$.

**PREUVE.** Il est clair que la jointure $A \oplus B$ permet de calculer $A$ et $B$. Ainsi, $\deg_T(A \oplus B)$ est un majorant de $\deg_T(A)$ et $\deg_T(B)$. Soit $\deg_T(C)$ un majorant de $\deg_T(A)$ et $\deg_T(B)$. En particulier, $C \ge T$ $A$ et $C \ge T$ $B$. Soient $i$ et $j$ des codes tels que $\Phi_i(C, n) = A(n)$ et $\Phi_j(C, n) = B(n)$ pour tout $n$. La fonction $f : N \to \{0, 1\}$ définie par

$$f(n) = \begin{cases} \Phi_i(C, n/2) & \text{si } n \text{ est pair} \\ \Phi_j(C, (n-1)/2) & \text{sinon} \end{cases}$$

est $C$-calculable, et l'on a $f(n) = 1$ ssi $n \in A \oplus B$ pour tout entier $n$. Donc, $C \ge T$ $A \oplus B$. ■

**Notation**

Nous avons fait usage dans la preuve de la proposition précédente du prédicat $\ll \Phi_i(C, n) \downarrow = A(n) \gg$ pour tout $n$. Il nous arrivera quelques fois d'utiliser la notation $\Phi_i(C) = A$, plus courte.

Attention, la borne supérieure $c \cup d$ de $c$ et $d$ n'a bien entendu rien à voir avec la réunion ensembliste des degrés $c$ et $d$. De manière générale, les lettres en caractère gras $a, b, c, d, \dots$ seront utilisées pour parler des degrés en tant qu'objets abstraits au sein d'un ordre partiel, le détail des ensembles d'entiers constituant chaque degré n'étant alors pas pertinent.

<footnote n="1">1. L'inégalité $|D| \le |2^N|$ semble évidente, mais elle utilise l'axiome du choix, afin de sélectionner uniformément un élément dans chaque degré Turing. Nous en reparlerons brièvement dans la section 12-2.3.</footnote>
Nous jonglerons désormais entre les ensembles d'entiers et les degrés Turing. Chaque degré Turing pouvant être représenté par un ensemble d'entiers (l'un de ses membres), une opération sur les degrés Turing se fera normalement via une opération sur l'un de ses représentants, de manière à ce que le résultat attendu soit indépendant du choix d'un tel représentant. La jointure effective constitue un premier exemple illustrant notre propos.

**Exercice 5.8.** Montrer que si l'on suppose que $X \leq_{T} Y$ et $A \leq_{T} B$, alors

$$X \oplus A \leq_{T} Y \oplus B. \quad \diamond$$

L'exercice précédent montre que la jointure effective induit une opération sur les degrés Turing. Nous allons étudier dans la section suivante une nouvelle opération sur les degrés jouant un rôle essentiel en calculabilité : le saut Turing.

# 6. Saut Turing

Le saut Turing est une opération fondamentale en calculabilité, et se définit comme la relativisation du problème de l'arrêt.

**Définition 6.1.** Étant donné un ensemble $X$, on définit

$$X' = \{n : \Phi_{n}^{X}(n)\downarrow\}.$$

Le saut Turing est l'opérateur $X \mapsto X'$. ◇

On peut par exemple à présent définir l'arrêt relativement à l'arrêt : l'ensemble des codes de programmes informatiques qui s'arrêtent sur leur propre entrée, mais en utilisant l'arrêt en tant qu'oracle. On le note $\emptyset''$. Il n'est pas très difficile de montrer que le saut Turing induit une opération sur degrés Turing, et nous en laissons la preuve en exercice.

**Exercice 6.2.** (*) Montrer que si $X \leq_{T} Y$, alors $X' \leq_{T} Y'$. ◇

Nous verrons un renforcement du résultat de l'exercice précédent avec l'exercice 5-5.7. On notera donc $d'$ le saut Turing d'un degré Turing $d$. En particulier, $0'$ est le degré Turing du problème de l'arrêt.

**Proposition 6.3.** On a $X <_{T} X'$ pour tout $X \in 2^{\mathbb{N}}$. Ainsi $a$-t-on $d < d'$ pour tout degré Turing $d$. ★

**PREUVE.** Montrons d'abord que $X'$ calcule $X$. Soit $f: \mathbb{N} \times \mathbb{N} \to \{0,1\}$ la fonction partielle $X$-calculable définie par

$$f(e, n) = \begin{cases} 1 & \text{si } e \in X \\ \uparrow & \text{sinon.} \end{cases}$$
Par le théorème SMN relativisé à $X$ (voir le théorème 3.3), il existe une fonction totale calculable $g : \mathbb{N} \to \mathbb{N}$ telle que pour tous entiers $e$ et $n$, on a $\Phi_{g(e)}^X(n) = f(e, n)$. Ainsi, pour tout $e$ :

▷ si $e \in X$, alors $\Phi_{g(e)}^X$ est la fonction constante 1, et donc $g(e) \in X'$;

▷ si $e \notin X$, alors $\Phi_{g(e)}^X$ est la fonction nulle part définie, et $g(e) \notin X'$.

En particulier, $X'$ peut calculer $X$ : pour savoir si $n \in X$, il suffit de regarder si $g(n) \in X'$.

La preuve que $X \not\supseteq_T X'$ est une relativisation du fait que $\emptyset'$ n'est pas calculable, ce qui a été démontré préalablement avec le théorème 3.1. ■

Il existe donc une hiérarchie strictement croissante de degrés Turing :

$$0 < 0' < 0'' < \dots$$

Dans la preuve précédente, notons que la fonctionnelle Turing utilisée pour calculer $X$ à partir de $X'$ est la même pour tout oracle $X$. C'est quelque chose qui sera utilisé de temps à autre, par exemple dans le chapitre 26. Nous donnons l'occasion, ci-après, au lecteur non convaincu d'y réfléchir.

**Exercice 6.4.** Montrer qu'il existe une fonctionnelle $\Phi_e$ telle que :

▷ $\Phi_e(X', n) = X(n)$ pour tout $X \in 2^\mathbb{N}$ et pour tout $n \in \mathbb{N}$.

▷ $\Phi_e(Y, n) \downarrow$ pour tout $Y \in 2^\mathbb{N}$ et pour tout $n \in \mathbb{N}$.

◇

Notons enfin que le saut Turing n'est pas un opérateur injectif, comme nous le verrons par la suite à travers les ensembles low et high. Nous utiliserons de temps à autre la notion suivante de Turing-complétude.

**Définition 6.5.** Un ensemble $A$ est dit *Turing-complet* ou (simplement) *complet* si $A \supseteq_T \emptyset'$. Un degré Turing complet est un degré $\mathbf{d} \ge 0'$. Un ensemble ou degré qui n'est pas complet est *incomplet*. ◇

# 7. Calculabilité à la limite

Nous allons maintenant étudier certaines propriétés des ensembles calculables par le problème de l'arrêt. Ces ensembles admettent notamment une caractérisation très naturelle en termes d'approximations.

**Définition 7.1.** Une fonction $f : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ est *stable* si pour tout $x \in \mathbb{N}$, $\lim_y f(x, y)$ existe. Un ensemble $A$ est *calculable à la limite* s'il existe une fonction stable calculable $f : \mathbb{N} \times \mathbb{N} \to \{0, 1\}$ telle que pour tout $x$

$$\lim_y f(x, y) = 1 \Leftrightarrow x \in A.$$

◇
**Lemme 7.2 (Lemme de limite de Shoenfield).** Un ensemble $A \subseteq \mathbb{N}$ est $\emptyset$-calculable si, et seulement si, il est calculable à la limite. ★

**PREUVE.** On pourra se reporter aux figures 7.4 et 7.3 pour s'aider dans la compréhension de la preuve.

⇒. Supposons que $A \leq_T \emptyset'$ via une fonctionnelle $\Phi_e$. Soit $\emptyset'_0 \subseteq \emptyset'_1 \subseteq \dots$ une approximation c. e. de $\emptyset'$, et soit $f: \mathbb{N} \times \mathbb{N} \to \{0,1\}$ la fonction qui pour une entrée $(x,s)$ regarde si $\Phi_e(\emptyset', x)[s] \downarrow$. Si tel est le cas, $f(x,s) = \Phi_e(\emptyset'_s, x)[s]$. Sinon, $f(x,s)$ se voit attribuer une valeur arbitraire.

Montrons que $f$ est stable et que sa limite est $A$. Soit $x \in \mathbb{N}$; par la propriété de l'usage, comme $\Phi_e(\emptyset', x) \downarrow$, ce calcul est effectué en utilisant les $n$ premiers bits de l'oracle pour un certain entier $n$. Soit alors $s$ tel que $\emptyset'_s \upharpoonright_n = \emptyset' \upharpoonright_n$ et tel que $\Phi_e(\emptyset', x) \downarrow$ s'arrête après $s$ étapes de calcul (il suffit de prendre $s$ suffisamment grand). Alors, pour tout $t \geqslant s$,

$$ \Phi_e(\emptyset'_t, x)[t] \downarrow = \Phi_e(\emptyset', x), $$

$$ \text{auquel cas } \lim_{t} f(x,t) = \Phi_e(\emptyset', x) = A(x). $$

⇒. Supposons maintenant que $A$ est calculable à la limite, par une fonction stable calculable $f: \mathbb{N} \times \mathbb{N} \to \{0,1\}$. Alors,

$$ A = \{x : \exists y \forall z \geqslant y f(x,z) = 1\} \quad \text{et} \quad \bar{A} = \{x : \exists y \forall z \geqslant y f(x,z) = 0\}. $$

Nous allons définir une procédure $\emptyset$-calculable pour déterminer si $x \in A$ ou $x \in \bar{A}$. Soient $u, v: \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ deux fonctions totales calculables telles que pour tous $x, y, n$,

$$ \Phi_{u(x,y)}(n) = \left\{ \begin{array}{ll} 1 & \text{si } \exists z \geqslant y f(x,z) \neq 1 \\ \uparrow & \text{sinon,} \end{array} \right. $$

$$ \Phi_{v(x,y)}(n) = \left\{ \begin{array}{ll} 1 & \text{si } \exists z \geqslant y f(x,z) \neq 0 \\ \uparrow & \text{sinon.} \end{array} \right. $$

En particulier,

$$ u(x,y) \notin \emptyset' \quad \text{ssi} \quad \forall z \geqslant y f(x,z) = 1 \quad \text{et} \quad v(x,y) \notin \emptyset' \quad \text{ssi} \quad \forall z \geqslant y f(x,z) = 0. $$

$$ \text{Ainsi, } A = \{x : \exists y u(x,y) \notin \emptyset'\} \quad \text{et} \quad \bar{A} = \{x : \exists y v(x,y) \notin \emptyset'\}. $$

Étant donné un entier $x$, pour savoir si $x \in A$ ou $x \in \bar{A}$, il suffit de chercher le plus petit $y$ tel que $u(x,y) \notin \emptyset'$ ou $v(x,y) \notin \emptyset'$. On finira nécessairement par trouver un tel entier $y$. Si $u(x,y) \notin \emptyset'$, alors $x \in A$. Si $v(x,y) \notin \emptyset'$, alors $x \notin A$. La procédure est $\emptyset$-calculable, et l'on a ainsi $A \leq_T \emptyset'$. ■
<table><thead><tr><th>Approximation du bit numéro <i>x</i></th><th>Codes de machines</th></tr></thead><tbody><tr><td>0</td><td>► <i>u</i>(<i>x</i>, 0) et <i>v</i>(<i>x</i>, 0)</td></tr><tr><td>1</td><td>► <i>u</i>(<i>x</i>, 1) et <i>v</i>(<i>x</i>, 1)</td></tr><tr><td>0</td><td>► <i>u</i>(<i>x</i>, 2) et <i>v</i>(<i>x</i>, 2)</td></tr><tr><td>0</td><td>► <i>u</i>(<i>x</i>, 3) et <i>v</i>(<i>x</i>, 3)</td></tr><tr><td>1</td><td>► <i>u</i>(<i>x</i>, 4) et <i>v</i>(<i>x</i>, 4)</td></tr><tr><td>0</td><td>► <i>u</i>(<i>x</i>, 5) et <i>v</i>(<i>x</i>, 5)</td></tr><tr><td>0</td><td>► <i>u</i>(<i>x</i>, 6) et <i>v</i>(<i>x</i>, 6)</td></tr><tr><td>...</td><td></td></tr></tbody></table>

FIGURE 7.3 – Illustration de la preuve de $\Leftarrow$ du lemme de Shoenfield : étant donné l'approximation d'un bit, on crée à l'étape $y$ le code $u(x,y)$ du programme qui s'arrête partout si une valeur différente de 1 est prise par le bit $x$ à une étape plus grande que $y$, et le code $v(x,y)$ du programme qui s'arrête partout si une valeur différente de 0 est prise par le bit $x$ à une étape plus grande que $y$.

**Exercice 7.5.** Montrer que si $Y$ est $X$-c. e. et $Z$ est $Y$-c. e., alors $Z$ n'est pas nécessairement $X$-c. e. ◇

Tout ensemble $\emptyset'$-calculable $A$ se voit donc associer une fonction stable $f$ dont la limite est $A$. On présente souvent cette fonction sous la forme d'une succession d'ensembles *uniformément calculables* $A_0, A_1, \dots$ définie par $A_y = \{x : f(x, y) = 1\}$ pour tout $y$.

## La calculabilité uniforme

Nous avons introduit le concept de suite $A_0, A_1, \dots$ *uniformément calculable* : chaque élément $A_n$ de la suite est calculable par la même fonction, paramétrée par un paramètre supplémentaire $n$ qui indique que l'on calcule le $n$-ième élément de la suite.

Insistons sur le fait qu'une suite d'ensembles calculables $(X_i)_{i \in \mathbb{N}}$ n'est pas nécessairement *uniformément calculable* : il n'existe pas forcément d'algorithme permettant de calculer $X_i$ en fonction de $i$. À titre d'exemple trivial, chaque $X_i$ peut simplement être une suite infinie de 0, à l'exception du bit en position $i$ qui est égal au $i$-ième bit de $\emptyset'$. Chaque $X_i$ est un ensemble fini et est donc de ce fait calculable. En revanche, un algorithme permettant de calculer *uniformément* $X_i$ en fonction de $i$ permettrait de calculer l'arrêt, et ne peut donc exister.
<figure><img src="image_29.png" /><figcaption>FIGURE 7.4 – Illustration de la preuve de ⇒ du lemme de Shoenfield. La première colonne représente des approximations successives de $\emptyset'$. La partie soulignée représente l'usage du calcul $\Phi_e(\emptyset', x)[t_n]$ lorsqu'il s'arrête. À measure que l'on énumère le i-ième élément dans l'arrêt à l'étape de calcul $t_i$, on lance le calcul de $\Phi_e$ avec l'approximation courante de l'arrêt comme oracle, et pour $t_i$ étapes de calcul. Par la propriété de l'usage, le processus converge nécessairement.</figcaption></figure>

**Définition 7.6.** Soit $A \leq_T \emptyset'$ un ensemble. Une approximation $\Delta_2^0$ de A est une suite uniformément calculable d'ensembles $A_0, A_1, \dots$ telle que pour tout $x$, $\lim_y A_y(x)$ existe et vaut $A(x)$. ♢

Les approximations $\Delta_2^0$ ne sont pas canoniques. Il est toujours possible par exemple d'« accélérer » une approximation $\Delta_2^0 A_0, A_1, \dots$ en considérant la suite $A_{g(0)}, A_{g(1)}, \dots$ pour une fonction calculable et strictement croissante $g : \mathbb{N} \to \mathbb{N}$.

**Remarque**

L'appellation « approximation $\Delta_2^0$ » sera justifiée dans le chapitre 5, où l'on donnera une nouvelle caractérisation des ensembles $\emptyset'$-calculables comme ceux définissables par un prédicat $\Delta_2^0$.

Les approximations $\Delta_2^0$ permettent de définir deux fonctions importantes, à savoir le modulus et la fonction de calcul. Ces fonctions expriment la com-
plexité calculatoire de l'ensemble A sous forme de rapidité de croissance : toute fonction croissant plus vite que le modulus de A ou que sa fonction de calcul permet de recalculer A.

**Définition 7.7.** Soit $A_0, A_1, A_2, \dots$ une approximation $\Delta_2^0$ d'un ensemble A.

1. Le modulus de l'approximation $\Delta_2^0$ est la fonction $\mu_A : \mathbb{N} \to \mathbb{N}$ qui à $x$ associe le plus petit entier $n$ tel que la suite $A_n \upharpoonright_x A_{n+1} \upharpoonright_x, \dots$ soit constante.

2. La fonction de calcul de l'approximation $\Delta_2^0$ est la fonction $c_A : \mathbb{N} \to \mathbb{N}$ qui à $x$ associe le plus petit entier $n \ge x$ tel que $A_n \upharpoonright_x A \upharpoonright_x$. ◇

Contrairement aux approximations c.e qui, lorsqu'elles font apparaître un élément dans A, ne le retirent plus jamais, une approximation $\Delta_2^0$ de A a le droit de « changer d'avis» un nombre arbitrairement grand (mais fini) de fois sur l'appartenance d'un élément $x$ à A. En particulier, la fonction de calcul croît en général plus lentement que le modulus, car un ensemble $A_n$ peut coïncider avec l'ensemble A sur un long segment initial sans pourtant avoir atteint son seuil de stabilité sur ce segment. La fonction de calcul, contrairement au modulus en général, est calculable par l'ensemble A.

Il est facile de vérifier que toute fonction dominant le modulus d'une approximation $\Delta_2^0$ d'un ensemble calcule cet ensemble.

**Exercice 7.8.** Soit $A_0, A_1, \dots$ une approximation $\Delta_2^0$ d'un ensemble A, et soit $\mu_A$ son modulus. Montrer que toute fonction dominant $\mu_A$ calcule A. Une fonction $f$ domine une fonction $g$ si $f(n) \ge g(n)$ pour tout $n \in \mathbb{N}$. ◇

Il n'est cependant pas clair que cela soit également le cas de la fonction de calcul. C'est pourtant ce que montre la proposition suivante.

**Proposition 7.9 (Martin et Miller [157]).** Soit $A_0, A_1, \dots$ une approximation $\Delta_2^0$ d'un ensemble A. Soit $c_A$ sa fonction de calcul. Toute fonction dominant $c_A$ calcule A. ★

**PREUVE.** Soit $f$ une fonction dominant $c_A$. Soit $M(x)$ le plus grand $y \le x$ tel que pour tout $x \le t \le f(x)$, $A_t \upharpoonright_y = A_{f(x)} \upharpoonright_y$. La fonction $M$ est totale $f$-calculable. De plus, $M$ tend vers $+\infty$, car l'approximation de $A$ étant $\Delta_2^0$, elle va se stabiliser sur des segments initiaux de plus en plus grands. Enfin, comme $x \le c_A(x) \le f(x)$, alors si $M(x) = y$, $A_x \upharpoonright_y = A_{c_A(x)} \upharpoonright_y = A \upharpoonright_y$. Ainsi, pour décider si $n \in A$, il suffit de trouver un entier $x$ tel que $M(x) > n$, puis tester si $n \in A_x$. Cette procédure est $f$-calculable. ■

Notons qu'il est important de demander que $c_A(x) \ge x$ dans la définition de fonction de calcul. La proposition précédente devient fausse lorsque l'on omet cette précision.
**Remarque**

Les notions de modulus et de fonction de calcul ne sont pas ca-
ractéristiques d'un ensemble $\emptyset'$-calculable, mais d'une approximation $\Delta_2^0$ d'un ensemble.

Un même ensemble $\emptyset'$-calculable possède une infinité d'approxima-
tions $\Delta_2^0$, chacune ayant son modulus et sa fonction de calcul.

8. Méthode des extensions finies

Nous allons maintenant présenter une méthode relativement simple et pour-
tant très puissante, permettant de créer des ensembles satisfaisant des pro-
priétés calculatoires « sur mesure ». Il s'agit de la *méthode des extensions
finies*.

En calculabilité, on appelle *propriété de faiblesse* une propriété close par le
bas dans les degrés Turing, c'est-à-dire que si X a une propriété de faiblesse
et si $Y \le_T X$, alors Y a aussi cette propriété de faiblesse. À l'inverse, une
propriété de force est une propriété close par le haut dans les degrés Turing,
c'est-à-dire que si X a une propriété de force et si $X \le_T Y$, alors Y a aussi
cette propriété de force.

La méthode des extensions finies est particulièrement adaptée lorsque l'on
se pose la question de l'existence d'ensembles satisfaisant simultanément
des propriétés de force et de faiblesse. Il faut alors créer un ensemble sur
mesure, ni trop fort, ni trop faible du point de vue calculatoire. Nous allons
illustrer cette méthode en prouvant deux propositions.

**Proposition 8.1 (Kleene et Post, 1954).** *Il existe deux ensembles A et B incomparables par la réduction de Turing.* ★

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

PREUVE. Nous allons construire simultanément deux ensembles A et B,
vus comme des suites binaires infinies — souvenons-nous de la correspon-
dance entre les deux.

L'ensemble A doit satisfaire une propriété de force (A n'est pas calculable par B) et une propriété de faiblesse (A ne calcule pas B). L'ensemble B doit de son côté satisfaire les propriétés duales de force et de faiblesse.

**Contrats.** Les propriétés calculatoires, qu’elles soient de force ou de faiblesse, sont en général des schémas de propriétés, au sens où elles se déclinent en une infinité de propriétés plus élémentaires et plus faciles à satisfaire de manière indépendante. Par exemple, la propriété « $A \not\le_T B$ » correspond à la collection de propriétés $\langle \Phi_e^A \neq B \rangle$ pour tout code de fonctionnelle $e$, où $\langle \Phi_e^A \neq B \rangle$ signifie que soit $\Phi_e^A$ est une fonction partielle, soit $\Phi_e^A(x) \downarrow \neq B(x)$ pour un $x \in \mathbb{N}$. On appelle ces propriétés
élémentaires des contrats (ou *requirements* en anglais). La première étape d'une construction par méthode des extensions finies consiste à identifier les contrats. Nous en avons donc de deux sortes ($\mathcal{R}_e$)$_{e \in \mathbb{N}}$ et ($\mathcal{S}_e$)$_{e \in \mathbb{N}}$ :

$$ \mathcal{R}_e : \quad \exists x \Phi_e^A(x) \uparrow \lor \exists x \Phi_e^A(x) \downarrow \neq B(x) $$

$$ \mathcal{S}_e : \quad \exists x \Phi_e^B(x) \uparrow \lor \exists x \Phi_e^B(x) \downarrow \neq A(x). $$

Si tous les contrats $\mathcal{R}_e$ sont satisfaits, alors $A \not\geq_T B$, tandis que si tous les contrats $\mathcal{S}_e$ le sont, $B \not\geq_T A$. Étant donné que l'on ne s'intéresse qu'aux fonctionnelles calculant des éléments de $2^\mathbb{N}$, on considérera — comme sout- vent dans ce genre de cas — que $\Phi_e(X, n) \uparrow$ si jamais $\Phi_e(X, n) \downarrow \notin \{0, 1\}$.

**Satisfaction d'un contrat.** Supposons que l'on ne veuille satisfaire qu'un seul contrat, disons $\mathcal{R}_e$. Deux cas se présentent.

▷ Cas 1. Il existe un ensemble $X$ tel que $\Phi_e^X(0) \downarrow = i$ pour un $i \in \{0, 1\}$ donné. On peut alors fixer $A = X$ et $B$ peut être n'importe quel ensemble tel que $B(0) \neq i$. On aura alors satisfait le contrat $\mathcal{R}_e$ en s'assurant que $\Phi_e^A(0) \downarrow \neq B(0)$.

▷ Cas 2. Quel que soit l'ensemble $X$, on a $\Phi_e^X(0) \uparrow$. Ce cas-ci est encore plus simple, $A$ et $B$ peuvent être n'importe quels ensembles.

L'argument précédent a entièrement spécifié les ensembles $A$ et $B$ pour satisfaire un contrat $\mathcal{R}_e$, sans laisser de liberté aux autres contrats pour être satisfaits. Nous allons donc tenter d'être plus économies pour laisser de la place à la satisfaction des autres contrats. Pour cela, nous allons faire en sorte de ne spécifier qu'un segment initial fini de $A$ et $B$ pour satisfaire un contrat donné.

**Construction.** Les ensembles $A$ et $B$ vont être construits par approxima- tions finies, sous forme de deux suites de chaînes binaires finies, représentant des préfixes de plus en plus longs de $A$ et $B$.

$$ \sigma_0 \preceq \sigma_1 \preceq \dots \quad \text{et} \quad \tau_0 \preceq \tau_1 \preceq \dots $$

On ne demande pas nécessairement à ce que $\sigma_n \prec \sigma_{n+1}$ : la suite de chaînes peut stagner pendant un certain temps. En revanche, pour tout $n$, on demande que pour $m > n$ suffisamment grand on ait $\sigma_n \prec \sigma_m$. De cette manière, les chaînes $\sigma_0 \preceq \sigma_1 \preceq \dots$ convergent petit à petit vers une unique suite infinie $A$ et les chaînes $\tau_0 \preceq \tau_1 \preceq \dots$ convergent petit à petit vers une unique suite infinie $B$. Formellement, on définit $A$ et $B$ via de nouvelles notations : étant donné une chaîne binaire $\sigma$, on notera $[\sigma]$ l'ensemble des suites binaires infinies ayant $\sigma$ comme préfixe. On aura donc $A \in [\sigma_n]$ et $B \in [\tau_n]$ pour tout $n \in \mathbb{N}$. En s'assurant qu'il existe des chaînes de longueur arbitrairement grande, on fait en sorte que $\bigcap_n[\sigma_n]$ et $\bigcap_n[\tau_n]$ contiennent chacun exactement un élément : $A$ et $B$ respectivement.
Les approximations finies de $A$ et $B$ vont être définies par étapes, de manière à satisfaire successivement chaque contrat. Comme à une étape donnée, seuls des préfixes finis de $A$ et $B$ sont connus, il va donc falloir satisfaire un contrat quel que soit ce qui viendra après ces préfixes dans la suite de la construction. Une paire de chaînes $\sigma_n$ et $\tau_n$ force un contrat $\mathcal{R}_e$ (ou un contrat $\mathcal{S}_e$) si la propriété du contrat est satisfaite pour tous $A \succeq \sigma_n$ et $B \succeq \tau_n$. On doit donc s'assurer que le contrat est satisfait pour tous les éléments de $[\sigma_n]$ et de $[\tau_n]$. Notons au passage que si $\sigma_n$ et $\tau_n$ forcent un contrat, alors pour tout $\sigma \succeq \sigma_n$ et $\tau \succeq \tau_n$ on a $[\sigma] \subseteq [\sigma_n]$ et $[\tau] \subseteq [\tau_n]$, et donc $\sigma$ et $\tau$ forcent encore le contrat.

Les différents contrats vont être entrelacés afin que chacun reçoive l'attention à une étape de la construction. Lors d'une étape paire $n = 2e$, on définira $\sigma_{n+1}$ et $\tau_{n+1}$ de manière à forcer $\mathcal{R}_e$, tandis que lors d'une étape impaire, $n = 2e+1$, on forcera $\mathcal{S}_e$. Les contrats seront donc satisfaits selon l'ordre

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

**Satisfaction d'un contrat.** Nous allons maintenant à nouveau satisfaire le contrat $\mathcal{R}_e$ en ne spécifiant cette fois-ci qu'un préfixe fini des oracles $A$ et $B$. Le cas des contrats $\mathcal{S}_e$ est symétrique. Supposons que des segments initiaux $\sigma_n$ et $\tau_n$ ont déjà été spécifiés pour $A$ et $B$ (on commence au départ la construction avec $\sigma_0 = \tau_0 = \epsilon$ où $\epsilon$ est le mot vide). Autrement dit, les suites binaires infinies finales $A$ et $B$ devront respecter $\sigma_n \preceq A$ et $\tau_n \preceq B$. Soit $x = |\tau_n|$. En particulier, $x$ est la première position sur laquelle $B$ n'est pas encore spécifié. Toutes les valeurs de $B$ aux positions précédant $x$ sont déjà fixées par $\tau_n$. Les deux cas suivants se présentent.

▷ Cas 1. Il existe un ensemble $X \succeq \sigma_n$, tel que $\Phi_e^X(x) \downarrow = i$ pour un $i$ dans $\{0,1\}$ donné. Dans ce cas, par la propriété de l'usage, ce calcul fait appel à un nombre fini de bits de l'oracle, et il existe donc un segment initial $\sigma_{n+1} \preceq X$ tel que $\Phi_e^{\sigma_{n+1}}(x) \downarrow = i$, ou autrement dit tel que $\Phi_e^Y(x) \downarrow = i$ pour tout ensemble $Y \succeq \sigma_{n+1}$. On peut choisir le segment initial $\sigma_{n+1}$ de manière à ce qu'il soit au moins aussi long que $\sigma_n$, ce qui assure $\sigma_{n+1} \succeq \sigma_n$. Sachant que l'ensemble $A$ aura $\sigma_{n+1}$ pour segment initial, on s'est assuré que $\Phi_e^A(x) \downarrow = i$. Soit $\tau_{n+1}$ la chaîne obtenue à partir de $\tau_n$ en lui ajoutant le bit $1-i$. Autrement dit, $|\tau_{n+1}| = |\tau_n| + 1$, $\tau_{n+1} \succeq \tau_n$ et $\tau_{n+1}(x) = 1-i$. On s'est alors assuré que pour tout $B \succeq \tau_{n+1}$, $B(x) = 1-i$. Ainsi, les chaînes $\sigma_{n+1}$ et $\tau_{n+1}$ étendent respectivement $\sigma_n$ et $\tau_n$, et forcent le contrat $\mathcal{R}_e$ en s'assurant que $\Phi_e^A(x) \downarrow \neq B(x)$ pour tous $A \succeq \sigma_n$ et $B \succeq \tau_n$.

▷ Cas 2. Pour tout ensemble $X \succeq \sigma_n$, on a $\Phi_e^X(x) \uparrow$. Dans ce cas, $\sigma_n$ et $\tau_n$ forcent déjà le contrat $\mathcal{R}_e$ en s'assurant $\Phi_e^A(x) \uparrow$ pour un certain $x$. Il suffit donc de prendre $\sigma_{n+1} = \sigma_n$ et $\tau_{n+1} = \tau_n$.
On s'assurera que les longueurs des éléments des suites $(\sigma_n)_{n \in \mathbb{N}}$ et $(\tau_n)_{n \in \mathbb{N}}$ soient de plus en plus grandes, en ajoutant un bit arbitraire au bout de chaque chaîne à la fin de chaque étape, avant de passer à l'étape suivante. Comme expliqué précédemment, le fait de forcer un contrat est clos par extension de chaînes, et cela n'altérera donc pas la validité de la construction. La preuve de la proposition 8.1 est terminée. ■

Une nouvelle notation a été introduite dans la preuve précédente; nous en officialisons ci-après l'utilisation.

**Notation**

Étant donné $\sigma \in 2^{<\mathbb{N}}$, on note $[\sigma]$ l'ensemble des $X \in 2^{<\mathbb{N}}$ tels que $\sigma < X$.

Nous allons donner une autre illustration de la méthode des extensions finies en prouvant une proposition plus forte, impliquant la proposition 8.1. On fixe cette fois-ci un ensemble $A$, arbitraire en dehors du fait qu'on le suppose non calculable. On construit alors un ensemble $B$ que $A$ ne calcule pas, et qui ne calcule pas $A$. Il s'agit d'une construction *a priori* plus difficile, car on ne contrôle plus qu'un seul des deux ensembles. Notons par ailleurs qu'il sera nécessaire pour cette preuve d'utiliser le fait que $A$ est non calculable : en effet, dans le cas inverse, tout ensemble $B$ que l'on construit permettrait de calculer $A$.

**Proposition 8.2.** Pour tout ensemble non calculable $A$, il existe un ensemble $B$ tel que $B \not\leq_T A$ et $A \not\leq_T B$.

**PREUVE.** Contrairement à la proposition 8.1, l'ensemble $A$ est déjà fixé. Nous allons construire uniquement l'ensemble $B$ par la méthode des approximations finies. L'ensemble $B$ doit encore satisfaire une propriété de force ($B \not\leq_T A$) et une propriété de faiblesse ($A \not\leq_T B$). Les contrats sont donc identiques à ceux de la proposition 8.1, à savoir

$$ \mathcal{R}_e : \quad \exists x \Phi_e^A(x) \uparrow \lor \exists x \Phi_e^A(x) \downarrow \neq B(x) $$

$$ \mathcal{S}_e : \quad \exists x \Phi_e^B(x) \uparrow \lor \exists x \Phi_e^B(x) \downarrow \neq A(x). $$

Cependant, les ensembles $A$ et $B$ ne jouant plus un rôle symétrique, les contrats $\mathcal{R}_e$ et $\mathcal{S}_e$ vont être satisfaits chacun à leur manière.

**Construction.** L'ensemble $B$ va être construit par approximations successives

$$ \tau_0 \preceq \tau_1 \preceq \tau_2 \preceq \dots $$

pour définir $B$ comme unique élément de l'ensemble $\bigcap_n[\tau_n]$. Une chaîne $\tau_n$ force un contrat $\mathcal{R}_e$ (ou un contrat $\mathcal{S}_e$) si la propriété est satisfaite pour tout $X \in [\tau_n]$. À chaque étape de la construction, un contrat va être forcé,
en les entrelaçant comme précédemment :

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

**Satisfaction d'un contrat** $\mathcal{R}_e$. À l'étape $n$, supposons que la chaîne $\tau_n$ est définie. Nous voulons trouver une extension $\tau_{n+1} \supseteq \tau_n$ forçant le contrat $\mathcal{R}_e$. La satisfaction de ce type de contrat est très similaire à celle de la proposition 8.1. Soit $x = |\tau_n|$. Deux cas se présentent.

▷ Cas 1. On a $\Phi_e^A(x) \downarrow = i$ pour un $i \in \{0, 1\}$. Il suffit alors de définir $\tau_{n+1}$ comme l'unique chaîne de longueur $|\tau_n| + 1$ étendant $\tau_n$ telle que

$$ \tau_{n+1}(x) = 1 - i. $$

Comme $B \in [\tau_{n+1}]$, $B(x) = 1 - i$, donc $\Phi_e^A(x) \downarrow \neq B(x)$.

▷ Cas 2. On a $\Phi_e^A(x) \uparrow$. Le contrat $\mathcal{R}_e$ est alors triviallement satisfait, car $\Phi_e^A$ est une fonction partielle. Il suffit donc de prendre $\tau_{n+1} = \tau_n$.

On notera que l'on n'a fait aucune supposition sur l'ensemble $A$ pour satisfaire les contrats $\mathcal{R}_e$. L'hypothèse selon laquelle $A$ n'est pas calculable sera exploitée pour satisfaire les contrats $\mathcal{S}_e$.

**Satisfaction d'un contrat** $\mathcal{S}_e$. La difficulté de la satisfaction d'un contrat tel que $\mathcal{S}_e$ provient du fait que l'on n'a pas de contrôle sur l'ensemble $A$ qui est entièrement spécifié. Plus précisément, lors de la satisfaction d'un contrat $\mathcal{R}_e$, on fixe une entrée $x$ qui n'est pas encore spécifiée pour $B$, de manière à choisir sa valeur dans le cas 1 pour la rendre différente de la valeur de $\Phi_e^A(x)$. Ce n'est pas possible dans le cas du contrat $\mathcal{S}_e$, toutes les valeurs de $A$ étant fixées. Il va donc falloir exploiter le fait que l'ensemble $A$ n'est pas calculable. Notons en revanche que la satisfaction des contrats $\mathcal{R}_e$ laissait une certaine liberté, notamment dans le choix de $x$. En effet, seul un nombre fini d'entrées est spécifié à une étape donnée pour $B$, et donc la quasi-totalité des entrées peut être choisie pour $x$. Nous allons exploiter cette liberté de choix pour satisfaire les contrats $\mathcal{S}_e$. Trois cas se présentent.

▷ Cas 1. Il existe une entrée $x$ et un ensemble $X \supseteq \tau_n$ tels que

$$ \Phi_e^X(x) \downarrow \neq A(x). $$

Par la propriété de l'usage, il existe alors une chaîne finie $\tau_{n+1} \supseteq \tau_n$ telle que $\Phi_e^X(x) \downarrow \neq A(x)$ pour tout $X \in [\tau_{n+1}]$. La chaîne $\tau_{n+1}$ force donc le contrat $\mathcal{S}_e$.

▷ Cas 2. Il existe une entrée $x$ telle que pour tous les ensembles $X \supseteq \tau_n$, on a $\Phi_e^X(x) \uparrow$. Dans ce cas, la chaîne $\tau_n$ force déjà le contrat $\mathcal{S}_e$ en s'assurant que $\Phi_e^B(x) \uparrow$.

▷ Cas 3. Aucun des deux cas précédents ne se présente. Nous allons montrer alors qu'il est possible de calculer l'ensemble $A$, et donc d'en déduire une contradiction.
Voici la procédure pour calculer la valeur de $A(x)$ : chercher une chaîne finie $\tau \succeq \tau_n$ telle que $\Phi_e^\tau(x) \downarrow$ et renvoyer le résultat de ce calcul. Nous prétendons les deux faits suivants :

(1) il existe une telle chaîne, et donc que la recherche se terminera;

(2) quelle que soit $\tau$ telle que $\Phi_e^\tau(x) \downarrow$, alors $\Phi_e^\tau(x) \downarrow = A(x)$.

Pour montrer (1), remarquons que la négation du cas 2 signifie que pour tout $x$ (et en particulier pour ce $x$ considéré), il existe un ensemble $X \succeq \tau_n$ tel que $\Phi_e^X(x) \downarrow$. Par la propriété de l'usage, il existe alors un segment initial $\tau \succeq \tau_n$ de $X$ tel que $\Phi_e^\tau(x) \downarrow$.

Montrons (2). Si $\Phi_e^\tau(x) \downarrow \neq A(x)$, alors le cas 1 serait vrai en prenant n'importe quel $X \succeq \tau$. Il s'ensuit que $\Phi_e^\tau(x) \downarrow$ implique $\Phi_e^\tau(x) = A(x)$. Nous avons donc décrit une procédure calculable pour déterminer la valeur de $A(x)$ quel que soit $x$, contredisant l'hypothèse selon laquelle $A$ n'est pas calculable.

Cela conclut la preuve de la proposition 8.2. ■

Avant de conclure cette section dédiée à la méthode des extensions finies, mentionnons que de manière générale, cette méthode n'est pas *effective*, au sens où aucune contrainte de calculabilité n'est imposée à la suite des chaînes finies en construction. Il est cependant possible de faire une analyse fine de l'argument pour déterminer la puissance calculatoire nécessaire pour trouver un $\tau_{n+1}$, étant donné $\tau_n$. On obtient alors des bornes supérieures sur la complexité de l'ensemble construit.

## 9. Degrés low

Comme nous l'avons vu, le saut Turing est invariant par degré Turing. Ainsi, pour tout ensemble calculable $X$, $X' \equiv_T \emptyset'$. Il est naturel de se demander si seuls les ensembles calculables ont un saut Turing équivalent à $\emptyset'$, et plus généralement si le saut Turing est une fonction injective sur les degrés Turing. La proposition suivante montre que ce n'est pas le cas.

**Proposition 9.1.** Il existe un ensemble non calculable $A$ tel que

$$A' \equiv_T \emptyset' . \quad \star$$

**PREUVE.** L'ensemble $A$ va être construit à l'aide d'une version effective de la méthode des extensions finies (voir la section 8), en s'assurant que l'intégralité de la construction est calculable en $\emptyset'$.

**Contrats.** L'ensemble $A$ doit satisfaire une propriété de force ($A$ non calculable) et une propriété de faiblesse ($A' \leq_T \emptyset'$).
La propriété de force se décline en une infinité de contrats ($\mathcal{R}_e$)$_{e \in \mathbb{N}}$ :

$$ \mathcal{R}_e : \exists x \Phi_e(x) \uparrow \lor \exists x \Phi_e(x) \downarrow \neq A(x). $$

La propriété de faiblesse est d'un type nouveau. Pour la satisfaire, nous al-
lons faire en sorte de « contrôler » le saut Turing de $A$ au fur et à mesure de
la construction, tout en s'assurant que toute la construction elle-même est
calculable en $\emptyset'$. En s'aidant de ce fait, on aura une fonction $\emptyset'$-calculable $f$
pour laquelle on devra satisfaire une infinité de contrats ($S_e$)$_{e \in \mathbb{N}}$ :

$$ S_e : \Phi_e^A(e) \downarrow \rightarrow f(e) = 1 \text{ et } \Phi_e^A(e) \uparrow \rightarrow f(e) = 0. $$

Informellement, le contrat $S_e$ est satisfait si, à un moment fini de la construc-
tion, nous savons si $\Phi_e^A(e) \downarrow$ ou $\Phi_e^A(e) \uparrow$, quelle que soit la suite de la
construction.

**Construction.** L'ensemble $A$ va être construit par approximations succes-
sives

$$ \sigma_0 \preceq \sigma_1 \preceq \sigma_2 \preceq \dots $$

pour définir $A$ comme unique élément de $\bigcap_n[\sigma_n]$. Une chaîne $\sigma_n$ force un contrat $\mathcal{R}_e$ ou $S_e$ si la propriété est satisfaite pour tout $B \in [\sigma_n]$. À chaque étape de la construction, un contrat va être forcé, en les entrelaçant comme précédemment :

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

Nous devons de plus nous assurer que la construction est calculable en $\emptyset'$. Ainsi, pour connaître la valeur de $A'(e)$, il suffira d'exécuter à l'aide de $\emptyset'$ la construction jusqu'à l'étape 2e satisfaisant $S_e$, et de renvoyer le résultat. Cette procédure $\emptyset'$-calculable assure que $A' \leq_T \emptyset'$. Nous allons donc montrer comment satisfaire chaque type de contrat indépendamment, tout en analysant la complexité calculatoire de chaque étape pour s'assurer que $\sigma_{n+1}$ peut être obtenu à partir de $\sigma_n$ à l'aide de l'oracle $\emptyset'$.

**Satisfaction d'un contrat** $\mathcal{R}_e$. Supposons que $\sigma_n$ est déjà défini. Nous voulons trouver $\sigma_{n+1} \succeq \sigma_n$ forçant le contrat $\mathcal{R}_e$. Soit $x = |\sigma_n|$; autrement dit, $x$ est la première valeur de $A$ qui n'est pas encore spécifiée. Deux cas se présentent.

▷ Cas 1. On a $\Phi_e(x) \uparrow$, auquel cas $\mathcal{R}_e$ est trivalement satisfait, et l'on peut définir $\sigma_{n+1} = \sigma_n$

▷ Cas 2. On a $\Phi_e(x) \downarrow$, auquel cas la chaîne $\sigma_{n+1}$ obtenue à partir de $\sigma_n$ en lui ajoutant le bit $1 - \Phi_e(x)$ force $\mathcal{R}_e$.

En fonction du cas, nous allons donc définir une extension $\sigma_{n+1}$ différente. Il faut s'assurer que cette extension peut être obtenue calculatoirement à l'aide de l'oracle $\emptyset'$. La distinction entre les deux cas n'est pas calculable en soi, car elle demande de décider si $\Phi_e(x)$ s'arrête ou non. Nous pouvons cependant utiliser $\emptyset'$ pour répondre à cette question comme suit : soit $\Phi_i$
la fonction partielle calculable définie pour tout $n$ par $\Phi_i(n) = \Phi_e(x)$. Le code $i$ peut être construit calculatoirement, car il s'agit d'une simple manipulation de machine. Il s'ensuit que l'on est dans le premier cas ssi $i \notin \emptyset'$. Dans le premier cas, $\sigma_{n+1} = \sigma_n$ est triviallement calculable, tandis que dans le second cas, il suffit d'exécuter $\Phi_e(x)$ pour récupérer la valeur renvoyée, et obtenir ainsi $\sigma_{n+1}$. Nous pouvons donc trouver une extension $\sigma_{n+1}$ forçant le contrat $\mathcal{R}_e$ à l'aide de l'oracle $\emptyset'$.

**Satisfaction d'un contrat S<sub>e</sub>.** Supposons que $\sigma_n$ est déjà défini. Nous voulons trouver $\sigma_{n+1} \succeq \sigma_n$ tel que le comportement de $\Phi_e^A(e)$ est déjà défini par $\sigma_{n+1}$, autrement dit $\Phi_e^X(e) \downarrow$ pour tout $X \in [\sigma_{n+1}]$ ou $\Phi_e^X(e) \uparrow$ pour tout $X \in [\sigma_{n+1}]$. Deux cas se présentent encore.

* Cas 1. Il existe une chaîne $\tau \succeq \sigma_n$ telle que $\Phi_e^\tau(e) \downarrow$. Dans ce cas, en prenant $\sigma_{n+1} = \tau$, nous assurons que $\Phi_e^A(e) \downarrow$, car $A \in [\sigma_{n+1}]$.

* Cas 2. Pour toute chaîne $\tau \succeq \sigma_n$, $\Phi_e^\tau(e) \uparrow$. Dans ce cas, par la propriété de l'usage, quel que soit l'oracle $A \in [\sigma_n]$, $\Phi_e^A(e) \uparrow$. En définissant $\sigma_{n+1} = \sigma_n$, nous forçons donc $\Phi_e^A(e) \uparrow$.

Ainsi, dans chacun des cas, nous avons forcé le comportement de $\Phi_e^A(e)$ avec un préfixe fini de l'oracle.

Ici encore, il s'agit de trouver $\sigma_{n+1}$ à partir de $\sigma_n$ calculatoirement à l'aide de l'oracle $\emptyset'$. Comme pour le contrat $\mathcal{R}_e$, nous définissons une fonction partielle calculable $\Phi_i$ qui, pour chacune de ses entrées, cherche une chaîne $\tau \succeq \sigma_n$ telle que $\Phi_e^\tau(e)[|\tau|] \downarrow$, et s'arrête s'il en trouve une. Ainsi, $i \in \emptyset'$ si, et seulement si, nous sommes dans le premier cas. Une fois le cas déterminé, la chaîne $\sigma_{n+1}$ peut être trouvée calculatoirement. Cela conclut la preuve de la proposition 9.1. ■

Parmi les premières notions de faiblesse introduites et étudiées en calculabilité par Cooper et Soare de manière indépendante, se trouve la hiérarchie des ensembles low<sub>n</sub>, dont nous donnons ici le premier niveau.

**Définition 9.2.** Un ensemble $A \subseteq \mathbb{N}$ est low si $A' \leq_T \emptyset'$.

◇

Informellement, un ensemble est low s'il est indistinguishable d'un ensemble calculable du point de vue du saut Turing. Nous avons vu que si $X \leq_T Y$, alors $X' \leq_T Y'$.

Ainsi, comme $\emptyset \leq_T A$ pour tout ensemble $A$, $\emptyset' \leq_T A'$. Il s'ensuit qu'un ensemble est low ssi $A' \equiv_T \emptyset'$. Nous verrons plus loin d'autres exemples d'ensembles low non calculables, notamment des ensembles calculatoirement énumérables (voir le chapitre 13).
# 10. Degrés high

Si l'on considère un ensemble $A \leq_T \emptyset'$, quelles sont les puissances extrêmes que peut prendre son saut Turing $A'$ ?

Rappelons que si $X \leq_T Y$, alors $X' \leq_T Y'$. En particulier, $A' \geq_T \emptyset'$. D'un autre côté, $A' \leq_T \emptyset''$ car $A \leq_T \emptyset'$. On a donc

$$ \emptyset' \leq_T A' \leq_T \emptyset'' \text{ si } A \leq_T \emptyset' $$

Notons que dans le cas où $A \not\leq_T \emptyset'$, le saut Turing de $A$ peut être arbitrairement complexe.

Les ensembles dont le saut Turing est égal à la borne minimale, à savoir $\emptyset'$, sont les ensembles low. Nous avons vu qu'il existait des ensembles low non calculables. Nous allons maintenant nous pencher sur les ensembles dont le saut Turing calcule la borne maximale $\emptyset''$.

**Définition 10.1.** Un ensemble $A \subseteq \mathbb{N}$ est high si $\emptyset'' \leq_T A'$.

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

**Remarque**

La notion d'ensemble high a été historiquement définie uniquement pour les ensembles $A \leq_T \emptyset'$. Elle a depuis été étendue à tous les ensembles, mais il est important de garder cette différence historique en tête lorsqu'on lit les articles fondateurs de la calculabilité.

Réfléchissons à présent aux ensembles high. À l'inverse des low, leur saut Turing a plus de puissance de calcul qu'attendu : il permet de calculer le double saut. Le problème de l'arrêt lui-même est évidemment un exemple trivial d'ensemble high. Tout comme pour les ensembles low, la notion d'ensemble high a son intérêt pour les exemples non triviaux : les ensembles high qui ne calculent pas $\emptyset'$. Il est en fait possible de montrer que pour tout ensemble $C$ non calculable il existe un ensemble high qui ne calcule pas $C$.

Dans la preuve suivante, nous utilisons pour la première fois des oracles qui sont non pas des ensembles d'entiers, mais des fonctions $f : \mathbb{N} \to \mathbb{N}$. Une telle fonction peut être représentée par la suite binaire infinie $X_f$ telle que $X_f(\langle n, m \rangle) = 1$ ssi $f(n) = m$. Il est clair que $X_f$ permet de calculer $f$, et que tout ensemble $Y$ permettant de calculer $f$ peut aussi calculer $X_f$ : l'ensemble $X_f$ est une représentation minimum de la fonction $f$ dans les degrés Turing. D'autres représentations équivalentes en termes de degré Turing sont possibles, par exemple avec $X_f = 1^{f(0)}01^{f(1)}01^{f(2)}0...$ (On commence par les $f(0)$ premiers bits à 1, suivis d'un 0, puis on continue avec les $f(1)$ bits suivants à 1, suivit d'un 0, etc.).
**Proposition 10.2.** Pour tout ensemble non calculable $C$, il existe un ensemble high $A$ tel que $A \not\supseteq_T C$.

**PREUVE.** Elle est assez similaire à celle de la proposition 8.2 avec la méthode des extensions finies.

**Contrats.** L'ensemble $A$ doit satisfaire une propriété de force ($A' \geq_T \emptyset''$) et une propriété de faiblesse ($C \not\leq_T A$). Les contrats pour la propriété de faiblesse sont standard, à savoir

$$S_e : \exists x \Phi_e^A(x) \uparrow \lor \exists x \Phi_e^A(x) \downarrow \neq C(x).$$

Le cas de la propriété de force est différent. Tout d'abord, il ne s'agit pas de contrôler ce que l'ensemble $A$ calcule, mais de contrôler ce que son saut Turing calcule. Ensuite, cette propriété de force ne s'exprime pas sous une forme négative (ne pas se faire calculer par un autre ensemble) mais sous une forme positive (calculer un objet compliqué). Les formulations négatives se prouvent souvent par diagonalisation, tandis que les formulations positives sont plus constructives. Nous n'allons donc pas exprimer la propriété de force sous forme de contrats, mais l'imposer structurellement dans la nature de l'objet que l'on construit.

Dans les utilisations précédentes de la méthode des extensions finies, nous avions construit un ensemble en créant une suite infinie de chaînes binaires formant des approximations finies de l'ensemble.

Cette fois-ci, nous allons construire une fonction stable $f: \mathbb{N} \times \mathbb{N} \to \{0,1\}$ dont la limite est $\emptyset''$. Comme expliqué dans le paragraphe précédant la preuve, rappelons que cela peut se ramener à l'utilisation d'un élément de $2^{\mathbb{N}}$ en considérant l'ensemble $X_f$ défini par $\langle n,m \rangle \in X_f$ ssi $f(n) = m$. Par la relativisation du lemme de limite de Shoenfield à $f$ (voir le lemme 7.2), un ensemble $B$ est $f$-calculable à la limite ssi $B \leq_T f'$. En particulier, pour $B = \emptyset''$, si $\emptyset''$ est $f$-calculable à la limite, alors $\emptyset'' \leq_T f'$, autrement dit $f$ est high. L'ensemble $A$ est donc n'importe quel ensemble dans le degré Turing de $f$.

**Construction.** La fonction $f$ va être construite à partir d'approximations finies successives de plus en plus précises. Ces approximations, au lieu d'être des chaînes binaires, vont être des couples $(g, m)$, où

▷ $g \subseteq \mathbb{N} \times \mathbb{N} \to \{0,1\}$ est une fonction partielle à deux paramètres dont le domaine est fini, représentant un morceau de la fonction $f$ que l'on est en train de construire.

▷ $m$ est un entier signifiant que désormais, lorsque l'on étendra le domaine de $g$ avec une nouvelle entrée $(x, y)$, si $x < m$ alors $g(x, y) = \emptyset''(x)$.