Nombre réel calculable

En informatique et algorithmique, un nombre réel calculable est un réel pour lequel il existe un algorithme ou une machine de Turing permettant d'énumérer la suite de ses chiffres (éventuellement infinie), ou plus généralement des symboles de son écriture sous forme de chaîne de caractères. De manière plus générale, et équivalente, un nombre réel est calculable si on peut en calculer une approximation aussi précise que l'on veut, avec une précision connue.

Cette notion a été mise en place par Alan Turing en 1936^[1]. Elle a ensuite été développée dans différentes branches des mathématiques constructives, et plus particulièrement l'analyse constructive^[2].

L'ensemble des réels calculables est un corps dénombrable. Il contient, par exemple, tous les nombres algébriques réels, ou des constantes célèbres comme π ou γ.

Les réels non calculables sont donc bien plus nombreux, bien qu'il soit généralement difficile de les définir, et sont en grande partie des nombres aléatoires. On parvient toutefois à en caractériser certains, comme la constante Oméga de Chaitin ou des nombres définis à partir du castor affairé ou des suites de Specker.

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].

Par extension, on appelle nombre complexe calculable un nombre complexe dont la partie réelle et la partie imaginaire sont calculables.

Une suite de réels (x_m) est dite calculable^[13] s'il existe une suite calculable (doublement indexée) de couples d'entiers (p_{m, n}, q_{m, n}), avec q_{m, n} ≠ 0, telle que :

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

Chacun des réels x_m est alors clairement calculable.

Si la suite (doublement indexée) des décimales des x_m est calculable, alors (x_m) est une suite calculable de réels, mais la réciproque est fausse, et de même en remplaçant 10 par n'importe quelle base > 1^[14].

• (en) Pietro Di Gianantonio, « Real Number Computability and Domain Theory », Information and Computation, vol. 127, n^o 1,‎ 1996, p. 12-25 (lire en ligne)
• (en) Andrzej Mostowski, Foundational Studies : Selected Works, vol. 1, Amsterdam/New York, Elsevier, 1979 (ISBN 978-0-444-85102-4, lire en ligne)
• (en) A. Mostowski, « On computable sequences », Fund. Math., vol. 44,‎ 1957, p. 37-51 (lire en ligne)
• (en) Marian B. Pour-El et J. Ian Richards, Computability in Analysis and Physics, Springer, 1989 (lire en ligne)
• (en) H. G. Rice, « Recursive real numbers », Proc. Amer. Math. Soc., vol. 5,‎ 1954, p. 784-791 (lire en ligne)
• (en) Alan Turing, On Computable Numbers, with an Application to the Entscheidungsproblem : Proceedings of the London Mathematical Society, London Mathematical Society, 1937 (DOI 10.1112/PLMS/S2-42.1.230, lire en ligne) et « [idem] : A Correction », Proc. London Math. Soc., 2^e série, vol. 43,‎ 1938, p. 544-546 (DOI 10.1112/plms/s2-43.6.544, lire en ligne)
• (en) Klaus Weihrauch, A Simple Introduction to Computable Analysis, FernUniversität Hagen, coll. « Informatik Berichte » (n^o 171), juillet 1995, 2^e éd., 79 p. (lire en ligne)
• (en) Klaus Weihrauch, Computable Analysis : An Introduction, Springer, coll. « Texts in Theoretical Computer Science », 2000, 285 p. (ISBN 978-3-540-66817-6, lire en ligne)

v · m Notion de nombre
Ensembles usuels	Entier naturel (${\displaystyle \scriptstyle \mathbb {N} }$) Entier relatif (${\displaystyle \scriptstyle \mathbb {Z} }$) Nombre décimal (${\displaystyle \scriptstyle \mathbb {D} }$) Nombre rationnel (${\displaystyle \scriptstyle \mathbb {Q} }$) Nombre réel (${\displaystyle \scriptstyle \mathbb {R} }$) Nombre complexe (${\displaystyle \scriptstyle \mathbb {C} }$)
Extensions	Quaternion (${\displaystyle \scriptstyle \mathbb {H} }$) Octonion (${\displaystyle \scriptstyle \mathbb {O} }$) Sédénion (${\displaystyle \scriptstyle \mathbb {S} }$) Nombre complexe déployé Tessarine Nombre bicomplexe (${\displaystyle \scriptstyle \mathbb {C} _{2}}$) Nombre multicomplexe (${\displaystyle \scriptstyle \mathbb {C} _{n}}$ ${\displaystyle \scriptstyle {\mathcal {M}}\mathbb {C} _{n}}$) Biquaternion Coquaternion Quaternion hyperbolique Octonion déployé Nombre hypercomplexe Nombre p-adique (${\displaystyle \scriptstyle \mathbb {Q} _{p}}$) Nombre hyperréel Nombre superréel Nombre dual Droite réelle achevée Nombre cardinal Nombre ordinal Nombre surréel Nombre pseudo-réel
Propriétés particulières	Parité Nombre premier Nombre composé Nombre figuré Nombre parfait Nombre positif Nombre négatif Fraction dyadique Nombre irrationnel Nombre algébrique Nombre transcendant Nombre imaginaire pur Nombre de Liouville Période Nombre normal Nombre univers Nombre constructible Nombre réel calculable Nombre transfini Infiniment petit
Exemples	Pi (π) Racine carrée de deux (${\displaystyle \scriptstyle {\sqrt {2}}}$) Nombre d’or (φ) Zéro (0) Unité imaginaire (i) Constante de Neper (e) Aleph-zéro (ℵ0) Table de constantes mathématiques
Articles liés	Chiffre Numération Fraction Opération Calcul Algèbre Arithmétique Suite d'entiers Infini (∞) Chiffre significatif

• Portail de l'informatique théorique