Computationally complex irrational numbers

Question

Are there irrational numbers for which we know that computing its nth digit would take (at least) linear/polynomial/exponential/superexponential time (wrt to length of n and with "big enough" n)?

Answer 1

Sure there is. Just define an irrational number $x=0.r_1r_2r_3\ldots$ where $r_i$ is an integer computed in linear/polynomial/exponential/superexponential time (i.e. asymptotic to $O(i),O(i^n) $ etc).

For example, you can set $r_i$ is the number of subsets of $\{1,2,\ldots,i\}$ whose members sum to a prime number. (I have no idea what the time complexity of this is but I guess with a naive algorithm it would be $O(2^i)$). Then computing $n$ digits of $x$ is done in exponential time. Note that even if $r_i>9$ then just stick $r_i$ onto the end of the decimal expansion of $x$.

In order to make computing $n$ digits of $x$ exactly exponential time, you can change the previous definition to $r_i$ is the number of subsets of $\{1,2,\ldots,i\}$ whose members sum to a prime number, mod $10$. Then I'm pretty sure that as long as you're using the naive algorithm, the calculation is in exponential time.

Similar methods can be used to find irrational numbers that are calculated in any other time complexity.

Answer 2

I don't have a complete answer. But we should note first that there are irrational numbers for which computing the $n$th digit is impossible! See Wikipedia's Computable Numbers page. We can prove this simply by counting. There are only a countable number of Turing Machines, thus a countable number of algorithms for computing irrational numbers. But there are an uncountable number of irrational numbers. So we cannot compute them all.

An example of an uncomputable number is Chaitin's constant.

But I don't have many good examples of irrational numbers along with time to compute them. There is a formula for the $n$th digit of pi but I'm not sure of the exact running time (edit: see Micah's comment below)~. That page also has similar formulae for e.g. $\ln(2)$.