Nombre réel calculable

Tout réel x est limite de nombreuses suites de nombres rationnels[3]. Il existe en particulier des suites de couples d'entiers (p_n, q_n), avec q_n ≠ 0, telles que :

${\displaystyle \forall n\in \mathbb {N} \quad \left|x-{\frac {p_{n}}{q_{n}}}\right|\leq {\frac {1}{2^{n}}}.}$

Le nombre x est dit calculable si, parmi ces suites (p_n, q_n), il en existe qui sont calculables[4]. (Il ne suffit pas pour cela que x soit limite d'une suite calculable de rationnels, comme le montre l'exemple des suites de Specker : il faut de plus que pour au moins une telle suite, le module de convergence soit, lui aussi, calculable[5].)

Une définition équivalente est :

Cette définition est vraie si on autorise chaque "chiffre", pour une base quelconque, à être éventuellement négatif, et c'est vrai particulièrement pour la base 10[6]. En revanche, en système binaire, les bits n'ont pas à être négatifs, et c'est la base généralement utilisée pour définir la calculabilité ainsi[7]^,[8].

Un nombre réel peut être calculable même si ses chiffres ne sont pas déterminés directement. Une troisième définition, toujours démontrée équivalente, est :

Soit A un ensemble d'entiers naturels, le réel

${\displaystyle \sum _{k\in A}2^{-k}}$

est calculable si et seulement si l'ensemble A est récursif[10].

Plus concrètement, on sait par exemple que :

${\displaystyle \pi =4\sum _{k=0}^{\infty }{\frac {(-1)^{k}}{2k+1}}}$ (formule de Leibniz).

Il est donc possible de déterminer des rationnels approchant π avec une précision arbitraire (la théorie sur les séries alternées permet même de savoir pour quel entier m il faut calculer ${\displaystyle 4\sum _{k=0}^{m}{\frac {(-1)^{k}}{2k+1}}}$ pour avoir un nombre donné de décimales exactes).

Mieux, tout nombre donné par une suite explicite à partir de nombres dont on a déjà montré qu'ils sont calculables l'est également. Par exemple non seulement e est calculable car

${\displaystyle \mathrm {e} =\sum _{n=0}^{+\infty }{1 \over n!}}$

mais pour tout nombre calculable x (par exemple x = π), le nombre e^x l'est également car

${\displaystyle \mathrm {e} ^{x}=\sum _{n=0}^{+\infty }{x^{n} \over n!}.}$

Donc pour toute fonction calculable, l'image d'un nombre calculable est un nombre calculable ; par exemple le cosinus d'un rationnel donné est calculable (réciproquement, si un réel x n'est pas calculable alors e^x, par exemple, ne l'est pas non plus, sinon x = ln(e^x) le serait).

• L'ensemble des réels calculables est un sous-corps de ℝ.
• Il contient l'algèbre des périodes (donc tous les nombres algébriques réels et certains nombres transcendants comme π), mais aussi la constante d'Euler-Mascheroni γ (dont on ignore si elle est rationnelle).
• C'est un corps réel clos[11].
• C'est un ensemble dénombrable (un algorithme étant une suite finie de lettres d'un alphabet fini, l'ensemble des algorithmes, et donc a fortiori des nombres calculables, est dénombrable). La quasi-totalité des réels est donc non calculable (complémentaire d'un ensemble dénombrable). Ce sont en grande partie des nombres aléatoires. Bien qu'ils soient très nombreux, il est difficile d'en exhiber « explicitement ». On peut cependant citer la constante Oméga de Chaitin ou les nombres définis par le castor affairé.
• Puisque l'ensemble des réels calculables est dénombrable, on pourrait être tenté de dire que l'application du procédé diagonal de Cantor à cet ensemble fournirait un algorithme pour calculer un nouveau nombre, ce qui conduirait à une contradiction. La réponse de Turing[12] est que l'on ignore comment attribuer un numéro à chaque nombre calculable (plus précisément, on peut facilement démontrer, justement, qu'une telle attribution n'est pas calculable), or ceci doit être fait préalablement à la diagonalisation.
• L'égalité entre réels calculables n'est pas décidable[7].