Computable irrational numbers with representations of surprising complexity

Cauchy sequences, Dedekind cuts, base-10 expansions and continued fractions are examples of well-known representations of irrational numbers. But there exist others, not so popular, which can be defined using various kinds of sum approximations and best approximations. In this paper we investigate the complexity of a number of such representations. For any fast-growing computable function f, we define an irrational number alpha(f) by using a series of reciprocals of powers of all primes. We prove that certain representations of alpha(f) are of low computational complexity (which does not depend on f), whereas others, apparently similar representations, can be of arbitrarily high computational complexity (which depends on f). The existence of computable numbers like alpha(f) allows us to prove new and non-trivial theorems on the computational complexity of representations without resorting to the standard computability-theoretic machinery involving enumerations and diagonalizations. In the paper we also show how to construct irrational numbers gamma whose representations by a Cauchy sequences are of low computational complexity, but whose base-b expansion may be of arbitrarily high computational complexity for all bases b. Moreover, for any epsilon(2)-irrational number alpha, there will be an epsilon(2)-irrational number beta, such that alpha + beta has the complexity of gamma. As a consequence, two numbers which have, let us say, base-10 expansions of low computational complexity, may add up to a number whose base-10 expansion is of arbitrarily high computational complexity. The same goes for representations by base-2 expansions, base-17 expansions, Dedekind cuts, continued fractions, and so on. (C) 2020 Elsevier B.V. All rights reserved.