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.
DĂ©finitions principales
Tout rĂ©el x est limite de nombreuses suites de nombres rationnels[3]. Il existe en particulier des suites de couples d'entiers (pn, qn), avec qn â 0, telles que :
Le nombre x est dit calculable si, parmi ces suites (pn, qn), 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 :
Construction de nombres calculables
Soit A un ensemble d'entiers naturels, le réel
est calculable si et seulement si l'ensemble A est récursif[10].
Plus concrĂštement, on sait par exemple que :
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 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
mais pour tout nombre calculable x (par exemple x = Ï), le nombre ex l'est Ă©galement car
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 ex, par exemple, ne l'est pas non plus, sinon x = ln(ex) le serait).
Statut de l'ensemble des réels calculables
- 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].
Prolongements
Nombre complexe calculable
Par extension, on appelle nombre complexe calculable un nombre complexe dont la partie réelle et la partie imaginaire sont calculables.
Suite calculable de réels
Une suite de rĂ©els (xm) est dite calculable[13] s'il existe une suite calculable (doublement indexĂ©e) de couples d'entiers (pm, n, qm, n), avec qm, n â 0, telle que :
Chacun des réels xm est alors clairement calculable.
Si la suite (doublement indexĂ©e) des dĂ©cimales des xm est calculable, alors (xm) 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].
Notes et références
Notes
- Turing 1937
- Di Gianantonio 1996, p. 1
- Voir le § « Construction via les suites de Cauchy » de l'article « Construction des nombres réels »
- Pour des définitions équivalentes et des références, cf. par exemple Mostowski 1979, p. 96, Rice 1954 et Pour-El et Richards 1989.
- Il existe toute une hiérarchie de classes de réels définies de façon analogue. Par exemple en remplaçant les fonctions calculables par les fonctions récursives primaires (dans le numérateur, le dénominateur, et le module de convergence de la suite de rationnels), on définit la notion (plus restrictive) de nombre réel élémentaire : cf. bibliographie de (en) Katrin Tent et Martin Ziegler, Low functions of reals. « 0903.1384 », texte en accÚs libre, sur arXiv.
- Di Gianantonio 1996, def. d), p. 4
- Rice 1954, def. B, p. 784
- Mostowski 1957
- J.P. Delayahe Omega Numbers in Randomness and Complexity. From Leibniz to Chaitin World Scientific, 2007, p. 355
- Weihrauch 2000, p. 5, Example 1.3.2 ou Weihrauch 1995, p. 21 example 1 (4)
- Mostowski 1979, p. 96
- Turing 1937, § 8
- Cf. Mostowski 1979, p. 96 et quelques explications dans (en) « Computable sequence », sur PlanetMath.
- Mostowski 1957 Ă©tablit des inclusions strictes entre diverses variantes, qui correspondent pourtant Ă des dĂ©finitions Ă©quivalentes d'un rĂ©el calculable, et fait remarquer l'analogie inexpliquĂ©e avec la non-Ă©quivalence, dĂ©jĂ remarquĂ©e par Specker, de ces mĂȘmes variantes dans la dĂ©finition d'un rĂ©el « semi-calculable ».
Bibliographie
- (en) Pietro Di Gianantonio, « Real Number Computability and Domain Theory », Information and Computation, vol. 127, no 1,â , p. 12-25 (lire en ligne)
- (en) Andrzej Mostowski, Foundational Studies : Selected Works, vol. 1, Amsterdam/New York, Elsevier, (ISBN 978-0-444-85102-4, lire en ligne)
- (en) A. Mostowski, « On computable sequences », Fund. Math., vol. 44,â , p. 37-51 (lire en ligne)
- (en) Marian B. Pour-El et J. Ian Richards, Computability in Analysis and Physics, Springer, (lire en ligne)
- (en) H. G. Rice, « Recursive real numbers », Proc. Amer. Math. Soc., vol. 5,â , 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, (DOI 10.1112/PLMS/S2-42.1.230, lire en ligne) et « [idem] : A Correction », Proc. London Math. Soc., 2e sĂ©rie, vol. 43,â , 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 » (no 171), , 2e éd., 79 p. (lire en ligne)
- (en) Klaus Weihrauch, Computable Analysis : An Introduction, Springer, coll. « Texts in Theoretical Computer Science », , 285 p. (ISBN 978-3-540-66817-6, lire en ligne)