Voir la source de Nombre réel calculable

[[Fichier:10,000 digits of pi - poster.svg|vignette|[[Π (nombre)|π]] est calculable avec un précision arbitraire, mais presque tous les nombres réels sont non calculables.]]
En [[informatique]] et [[algorithmique]], un '''nombre réel calculable''' est un [[nombre réel|réel]] pour lequel il existe un [[Algorithmique|algorithme]] ou une [[machine de Turing]] permettant d'énumérer la suite de ses chiffres (éventuellement infinie), ou plus généralement des [[Théorie_des_automates#Alphabet|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<ref>{{harvsp|Turing|1937}}</ref>. Elle a ensuite été développée dans différentes branches des [[mathématiques constructives]], et plus particulièrement l'[[analyse constructive]]<ref>{{harvsp|Di Gianantonio|1996|p=1}}</ref>.

L'ensemble des réels [[calculabilité|calculables]] est un [[corps commutatif|corps]] [[ensemble dénombrable|dénombrable]]. Il contient, par exemple, tous les [[nombre algébrique|nombres algébriques]] réels, ou des constantes célèbres comme [[pi|{{math|π}}]] ou [[Constante d'Euler-Mascheroni|{{math|γ}}]].

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 [[suite aléatoire|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 [[Suite de Specker|suites de Specker]].

== Définitions principales ==
Tout réel ''{{math|x}}'' est [[Limite d'une suite|limite]] de nombreuses [[Suite (mathématiques)|suites]] de [[nombre rationnel|nombres rationnels]]<ref>Voir le [[Construction des nombres réels#Construction via les suites de Cauchy|§ « Construction via les suites de Cauchy » de l'article « Construction des nombres réels »]]</ref>. Il existe en particulier des suites de [[Couple (mathématiques)|couples]] d'[[entier relatif|entiers]] {{math|(''p{{ind|n}}'', ''q{{ind|n}}'')}}, avec ''{{math|q{{ind|n}}}} ''≠ 0, telles que :
<center><math>\forall n\in\N\quad\left|x-\frac{p_n}{q_n}\right|\le\frac1{2^n}.</math></center>
Le nombre ''{{math|x}}'' est dit calculable si, parmi ces suites {{math|(''p{{ind|n}}'', ''q{{ind|n}}'')}}, il en existe qui sont [[Fonction calculable|calculables]]<ref>

Pour des définitions équivalentes et des références, cf. par exemple {{harvsp|Mostowski|1979|p=96}}, {{harvsp|Rice|1954}} et {{harvsp|Pour-El|Richards|1989}}.</ref>. (Il ne suffit pas pour cela que ''{{math|x}} ''soit limite d'une suite calculable de rationnels, comme le montre l'exemple des [[Suite de Specker|suites de Specker]] : il faut de plus que pour au moins une telle suite, le [[module de convergence]] soit, lui aussi, calculable<ref>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 [[ELEMENTARY (complexité)|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. ''{{arxiv|0903.1384}}</ref>.)

Une définition équivalente est :

{{Bloc emphase|Un réel est calculable si la suite des chiffres dans une [[Base (arithmétique)|base]] quelconque est calculable<ref name=PDG4>{{harvsp|Di Gianantonio|1996|p=4|loc=def. d)}}</ref>.}}

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]]<ref name=PDG4/>. En revanche, en [[système binaire]], les [[bit]]s n'ont pas à être négatifs, et c'est la base généralement utilisée pour définir la calculabilité ainsi<ref name=Rice>{{harvsp|Rice|1954|p=784|loc=def. B}}</ref>{{,}}<ref>{{harvsp|Mostowski|1957}}</ref>.

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 :

{{Bloc emphase|Un réel ''x'' est calculable s'il existe un programme pour énumérer l'ensemble des [[nombre rationnel|rationnels]] supérieurs à x, et un autre pour énumérer l'ensemble des rationnels inférieurs à ''x''<ref>J.P. Delayahe ''Omega Numbers'' in ''Randomness and Complexity. From Leibniz to Chaitin'' World Scientific, 2007, p. 355</ref>.}}

== Construction de nombres calculables ==
Soit ''{{math|A}} ''un ensemble d'entiers naturels, le réel
<center><math>\sum_{k\in A}2^{-k}</math></center>
est calculable si et seulement si l'ensemble ''{{math|A}} ''est [[Ensemble récursif|récursif]]<ref>{{harvsp|Weihrauch|2000|p=5, Example 1.3.2}} ou {{harvsp|Weihrauch|1995|p=21 example 1 (4)}}</ref>.

Plus concrètement, on sait par exemple que :

<center><math>\pi =4 \sum_{k = 0}^{\infty}\frac{(-1)^k}{2k+1}</math> ([[Formule de Leibniz#Série alternée|formule de Leibniz]]).</center>

Il est donc possible de déterminer des rationnels approchant [[pi|{{math|π}}]] avec une précision arbitraire (la théorie sur les [[série alternée|séries alternées]] permet même de savoir pour quel entier ''{{math|m}} ''il faut calculer <math>4\sum_{k=0}^m\frac{(-1)^k}{2k+1}</math> 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 {{math|e}} est calculable car
<center><math>\mathrm e=\sum_{n=0}^{+\infty}{1\over n!}</math></center>
mais pour tout nombre calculable ''{{math|x}} ''(par exemple {{math|''x ''{{=}} π}}), le nombre {{math|e{{exp|''x''}}}} l'est également car
<center><math>\mathrm e^x=\sum_{n=0}^{+\infty}{x^n \over n!}.</math></center>

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 ''{{math|x}} ''n'est pas calculable alors {{math|e{{exp|''x''}}}}, par exemple, ne l'est pas non plus, sinon {{math|''x ''{{=}} ln(e{{exp|''x''}})}} 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 [[nombre algébrique|nombres algébriques]] réels et certains [[Nombre transcendant|nombres transcendants]] comme {{math|π}}), mais aussi la [[constante d'Euler-Mascheroni]] {{math|γ}} (dont on ignore si elle est rationnelle).
*C'est un [[corps réel clos]]<ref>{{harvsp|Mostowski|1979|p=96}}</ref>.
*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 [[suite aléatoire|aléatoires]]. Bien qu'ils soient [[Puissance du continu|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 [[argument de la diagonale de Cantor|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<ref>{{harvsp|Turing|1937}}, § 8</ref> 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 [[Ensemble récursif|décidable]]<ref name=Rice/>.

== 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 {{math|(''x{{ind|m}}'')}} est dite calculable<ref>Cf. {{harvsp|Mostowski|1979|p=96}} et quelques explications dans {{Planetmath|titre=Computable sequence}}.</ref> s'il existe une suite calculable (doublement indexée) de couples d'entiers {{math|(''p{{ind|m, n}}'', ''q{{ind|m, n}}'')}}, avec ''{{math|q{{ind|m, n}}}} ''≠ 0, telle que :
<center><math>\forall m,n\in\N\quad\left|x_m-\frac{p_{m,n}}{q_{m,n}}\right|\le\frac1{2^n}.</math></center>

Chacun des réels {{math|''x{{ind|m}}''}} est alors clairement calculable.

Si la suite (doublement indexée) des décimales des {{math|''x{{ind|m}}''}} est calculable, alors  {{math|(''x{{ind|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 (arithmétique)|base]] > 1<ref>{{harvsp|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 [[Ernst Specker|Specker]], de ces mêmes variantes dans la définition d'un réel « semi-calculable ».</ref>.
<!--

Si les {{math|''x{{ind|m}}''}} sont des rationnels, si leur suite est calculable au sens usuel alors elle l'est au sens ci-dessus, mais quid de la réciproque ?

-->

== Notes et références ==
=== Notes ===
{{références}}
=== Bibliographie ===
*{{article|lang=en|prénom=Pietro|nom=Di Gianantonio|url=http://users.dimi.uniud.it/~pietro.digianantonio/papers/copy_pdf/reali.pdf|titre=Real Number Computability and Domain Theory|revue=''[[Information and Computation]]''|année=1996|vol=127|numéro=1|p.=12-25}}
*{{Ouvrage|langue=en|prénom1=Andrzej|nom1=Mostowski|lien auteur1=Andrzej Mostowski|titre=Foundational Studies|sous-titre=Selected Works|volume=1|lieu=Amsterdam/New York|éditeur=[[Elsevier (éditeur)|Elsevier]]|année=1979|isbn=978-0-444-85102-4|lire en ligne=https://books.google.fr/books?id=60mICbpCca4C}}
*{{article|lang=en|prénom=A.|nom=Mostowski|titre=On computable sequences|lien périodique=Fundamenta Mathematicae|revue=Fund. Math.|volume=44|année=1957|p.=37-51|url=http://matwbn.icm.edu.pl/ksiazki/fm/fm44/fm4413.pdf}}
*{{Ouvrage|langue=en|prénom1=Marian B.|nom1=Pour-El|prénom2=J. Ian|nom2=Richards|titre=Computability in Analysis and Physics|éditeur=[[Springer Verlag|Springer]]|année=1989|lire en ligne=http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.pl/1235422916}}
*{{article|lang=en|lien auteur=Henry Gordon Rice|prénom=H. G.|nom=Rice|titre=Recursive real numbers|lien périodique=Proceedings of the American Mathematical Society|revue=Proc. Amer. Math. Soc.|volume=5|année=1954|p.=784-791|url=http://www.ams.org/journals/proc/1954-005-05/S0002-9939-1954-0063328-5/}}
* {{On Computable Numbers}}
*{{Ouvrage|langue=en|prénom1=Klaus|nom1=Weihrauch|titre=A Simple Introduction to Computable Analysis|éditeur=[[Hagen (Rhénanie-du-Nord-Westphalie)#Enseignement supérieur et recherche|FernUniversität Hagen]]|collection=Informatik Berichte|numéro dans collection=171|année=1995|mois=7|numéro d'édition=2|pages totales=79|lire en ligne=http://eccc.hpi-web.de/static/books/A_Simple_Introduction_to_Computable_Analysis_Fragments_of_a_Book/}}
*{{Ouvrage|langue=en|prénom1=Klaus|nom1=Weihrauch|titre=Computable Analysis|sous-titre=An Introduction|éditeur=Springer|collection=Texts in Theoretical Computer Science|année=2000|pages totales=285|isbn=978-3-540-66817-6|lire en ligne=https://books.google.fr/books?id=OPolVWVFDJYC&pg=PA5}}

{{Palette|Notion de nombre}}

{{portail|informatique théorique}}

{{DEFAULTSORT:Nombre reel calculable}}
[[Catégorie:Calculabilité]]
[[Catégorie:Type de nombres|Réel calculable]]