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 l'ensemble des chiffres de son développement décimal.



Catégories :

Calculabilité - Type de nombre

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 l'ensemble des chiffres de son développement décimal. Cette notion a été mise en place et développée par Turing.

La totalité des réels calculables est un corps (les lois d'un corps étant calculables) dénombrable (un algorithme étant une suite finie de lettres d'un alphabet fini, la totalité des algorithmes, et par conséquent a fortiori des nombres calculables, est dénombrable). Cet ensemble contient, par exemple, l'ensemble des nombres algébriques, ou des constantes célèbres comme π ou γ. La majorité des réels sont par conséquent non calculables (complémentaire d'un ensemble dénombrable), quoiqu'il soit le plus souvent complexe de les définir (puisqu'on ne peut les calculer... ). Quelques exemples remarquables existent cependant, comme la constante Oméga de Chaitin ou les nombres définis par le castor affairé.

Construction de nombres calculables

Tout nombre réel est la limite d'une suite de nombres rationnels ; ainsi s'il est envisageable 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_{k = 0}ˆ{\infty}\frac{(-1)ˆ{k}}{2k+1}

Il est par conséquent envisageable 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 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 aussi. Par exemple non seulement e est calculable car e = \sum_{n = 0}ˆ{+\infty} {1 \over n!} mais eπ l'est aussi car eˆ\pi = \sum_{n = 0}ˆ{+\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.

En revanche, si on sait que eˆ\Omega = \sum_{n = 0}ˆ{+\infty} {\Omegaˆn \over n!}, eΩ n'en est pas calculable pour tout autant puisque Ω ne l'est pas (d'ailleurs eΩ n'est pas calculable sinon Ω = log (eΩ) le serait).

On pourrait être tenté de dire que, s'il y a un ensemble des nombres calculables, et s'il est dénombrable, l'application du procédé diagonal de Cantor à cet ensemble apporterait bien un algorithme pour calculer un nouveau nombre, ce qui conduirait à une contradiction.

La réponse de Turing est qu'on ignore comment attribuer un numéro à chaque nombre calculable, or ceci doit être fait préalablement à la diagonalisation - voir le chapitre 8 de l'ouvrage de 1936 cité ci-dessous.

Nombre complexe calculable

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

Bibliographie

Liens externes

http ://www. thocp. net/biographies/papers/turing_oncomputablenumbers_1936. pdf

Recherche sur Amazon (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Nombre_r%C3%A9el_calculable.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 10/03/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu