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 est 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.

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:

$\backslash pi\; =4*\; \backslash sum\_\{k\; =\; 0\}^\{\backslash infty\}\backslash frac\{(-1)^\{k\}\}\{2*k+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 $\backslash pi\; =4*\; \backslash sum\_\{k\; =\; 0\}^\{m\}\backslash frac\{(-1)^\{k\}\}\{2*k+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\; =\; \backslash sum\_\{n\; =\; 0\}^\{+\backslash infty\}\; \{1\; \backslash over\; n!\}$ mais $e^\backslash pi$ l'est également car $e^\backslash pi\; =\; \backslash sum\_\{n\; =\; 0\}^\{+\backslash infty\}\; \{\backslash pi^n\; \backslash 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^\backslash omega\; =\; \backslash sum\_\{n\; =\; 0\}^\{+\backslash infty\}\; \{\backslash omega^n\; \backslash over\; n!\}$, $e^\backslash omega$ n'en est pas calculable pour autant puisque Ω ne l'est pas (d'ailleurs $e^\backslash omega$ n'est pas calculable sinon $\backslash omega=e^\backslash omega$ le serait).

Comme les réels calculables forment un corps et qu'ils incluent les nombres rationnels ainsi que π, $\backslash mathbb\; Q(\backslash pi)$ est un exemple de sous-corps du corps des nombres calculables (l'ensemble des valeurs prises par les fractions rationnelles à coefficients rationnels en π).

Nombre complexe calculable

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

Référence

• Alan Turing et Jean-Yves Girard , La machine de Turing, Editions du Seuil Paris, 1995

Liens

http://deptinfo.unice.fr/~fedou/ENSEIGNEMENT/OFI/GODEL/index.html

calculabilité | nombre

Berechenbare Zahl | Computable number | מספר חשיב | Beräkningsbart tal