Nombre réel calculable - Définition

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

- Introduction - Construction de nombres calculables - Bibliographie - Nombre complexe calculable

Introduction

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.

L'ensemble 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, l'ensemble des algorithmes, et donc a fortiori des nombres calculables, est dénombrable). Cet ensemble contient, par exemple, tous les nombres algébriques, ou des constantes célèbres comme π ou γ. La plupart des réels sont donc non calculables (complémentaire d'un ensemble dénombrable), bien qu'il soit généralement difficile 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 calculable 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_{k = 0}^{\infty}\frac{(-1)^{k}}{2k+1}$

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 $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 $e = \sum_{n = 0}^{+\infty} {1 \over n!}$ mais $e π$ l'est également 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 autant puisque Ω ne l'est pas (d'ailleurs $e Ω$ n'est pas calculable sinon $Ω = l o g (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 fournirait bien un algorithme pour calculer un nouveau nombre, ce qui conduirait à une contradiction.

La réponse de Turing est que l'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.