Nombre réel calculable

vignette|π est calculable avec un précision arbitraire alors que presque tous les nombres réels sont non calculables. 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 la suite de ses chiffres (éventuellement infinie), ou plus généralement des 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. Elle a ensuite été développée dans différentes branches des mathématiques constructives, et plus particulièrement l'analyse constructive. L'ensemble des réels calculables est un corps dénombrable. Il contient, par exemple, tous les nombres algébriques réels, ou des constantes célèbres comme π ou γ. 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 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 suites de Specker. Tout réel x est limite de nombreuses suites de nombres rationnels. Il existe en particulier des suites de couples d'entiers (p, q), avec q ≠ 0, telles que : Le nombre x est dit calculable si, parmi ces suites (p, q), il en existe qui sont calculables. (Il ne suffit pas pour cela que x soit limite d'une suite calculable de rationnels, comme le montre l'exemple des suites de Specker : il faut de plus que pour au moins une telle suite, le module de convergence soit, lui aussi, calculable.) Une définition équivalente est : 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. En revanche, en système binaire, les bits n'ont pas à être négatifs, et c'est la base généralement utilisée pour définir la calculabilité ainsi.