Nombre réel calculable

Infos
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 tous les chiffres de son développement décimal. Cette notion a été mise en place et développée par Turing. On démontre que l'ensemble des réels calculables est un corps dénombrable contenant l'ensemble de tous les nombres algébriques. On démontre aussi que π est calculable. Il existe des réels définis non ca
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 tous les chiffres de son développement décimal. Cette notion a été mise en place et développée par Turing. On démontre que l'ensemble des réels calculables est un corps dénombrable contenant l'ensemble de tous les nombres algébriques. On démontre aussi que π est calculable. Il existe des réels définis non calculables, un des plus célèbres étant la constante Oméga de Chaitin, mais il y aussi les nombres définis par le castor affairé (voir l'article en anglais busy beaver). Par contre, tout nombre calculable est un nombre définissable.

Construction de nombres calculables

Tout nombre réel est la limite d'une suite de nombres rationnels; ainsi s'il est possible d'expliciter un terme général pour une telle suite, le nombre qui en est la limite est calculable. On sait par exemple que: \pi =4 \sum_^\infty\frac 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 \pi =4 \sum_^\frac 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 e = \sum_^+\infty 1 \over n! mais e^\pi l'est également car e^\pi = \sum_^+\infty \pi^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). Mais en revanche, si on sait que e^\Omega = \sum_^+\infty \Omega^n \over n!, e^\Omega n'en est pas calculable pour autant puisque Ω ne l'est pas (d'ailleurs e^\Omega n'est pas calculable sinon \Omega=log(e^\Omega) le serait). Comme les réels calculables forment un corps et qu'ils incluent les nombres rationnels et algébriques ainsi que π, \mathbb Q(\pi) ou même \mathbb A(\pi) sont des exemples de sous-corps du corps des nombres calculables (l'ensemble des valeurs prises par les fractions rationnelles à coefficients rationnels, respectivement algébriques, en π). Oméga n'est ni un nombre rationnel ni un nombre algébrique ni un nombre calculable. Il est en revanche définissable, imprédictible et incompressible.

Nombre complexe calculable

Par extension, on appelle nombre complexe calculable un nombre complexe dont les parties réelle et imaginaire sont simultanément calculables.

Bibliographie

-Alan Turing et Jean-Yves Girard, La machine de Turing, Editions du Seuil Paris, 1995
-On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, series 2, 1936, vol 42, pp.230-265
-Klaus Weihrauch, Computable analysis: an introduction, Springer, Texts in theoretical computer science, ISBN 3540668179

Liens

http://deptinfo.unice.fr/~fedou/ENSEIGNEMENT/OFI/GODEL/index.html catégorie : calculabilité Réel calculable de:Berechenbare Zahl en:Computable number he:מספר חשיב sv:Beräkningsbart tal
Sujets connexes
Alan Turing   Algorithmique   Castor affairé   Chiffre   Corps (mathématiques)   Développement décimal   Ensemble dénombrable   Fonction calculable   Informatique   Jean-Yves Girard   Machine de Turing   Nombre algébrique   Nombre définissable   Nombre rationnel   Nombre réel   Oméga de Chaitin   Pi   Série alternée  
#
Accident de Beaune   Amélie Mauresmo   Anisocytose   C3H6O   CA Paris   Carole Richert   Catherinettes   Chaleur massique   Championnat de Tunisie de football D2   Classement mondial des entreprises leader par secteur   Col du Bonhomme (Vosges)   De viris illustribus (Lhomond)   Dolcett   EGP  
^