Computational complexity of real numbers

Question

Recently, I've been studying computable analysis. One of the basic notions is a computable real number, which I will define as any $r \in \mathbb{R}$ which has a computable Cauchy name - a computable, rational sequence $(q_n)_{n \in \mathbb{N}}$ satisfying $\lvert q_n - r \rvert \leq 2^{-n}$ for each $n$.

There is a well-developed theory of computational complexity for computable functions $f: \mathbb{N} \to \mathbb{N}$. It seems natural to try extend this to computable real numbers. For example, say a computable real $r \in \mathbb{R}$ has time complexity $O(g)$, for some function $g: \mathbb{N} \to \mathbb{N}$, if there exists a Cauchy name $(q_n)$ of $r$ which is computable in time $O(g)$ (here, consider $(q_n)$ as a function $\mathbb{N} \to \mathbb{N}$ under some coding of the rationals).

It seems clear then that any rational number $q$ is $O(1)$-computable - just choose the sequence which is constantly equal to $q$. I believe there should be irrationals which are constant-time-computable, but can't think of a quick example. And I'm not sure how one could prove that a real number is $\Omega(g)$ for some $g$. This has clear connections to rate of convergence of a sequence in numerical analysis, but we also have to consider how long it takes to compute terms of the sequence.

Can anyone point me to any work which has been done on such an idea? It seems like something which someone else must have considered. Note I'm not interested in complexity on real-valued functions, but on real numbers themselves.

---

Edit: to fix the ideas, let us say a real number $r$ is $O(h)$-computable if there exist $O(h)$-computable functions $f, g: \mathbb{N} \to \mathbb{N}$ such that for all $n$, $\left\lvert \frac{f(n)}{g(n)} - r\, \right\rvert \leq 2^{-n}$.

Answer 1

The question depends a bit on the description of the given irrational number $r \in \mathbb{R}\setminus \mathbb{Q}$. Typically $r$ takes its value as the output of a function $g:\mathbb{R} \to \mathbb{R}$, so $g(x^*) = r$, with the property that $x^*$ (typically a known integer or rational) and $g$ can be computed fast (an almost-example would be $\pi = 4 \text{atan}(1)$, after which a Padé approximation/continued fraction expansion of $\text{atan}$ can be applied to compute $\pi$, but other faster representations of $\pi$ are known).

So other than talking about specific constants of interest with efficient representations, the question will likely involve efficient approximations to functions that produce approximations to sets of irrational numbers of interest, taking efficiently representable numbers as inputs - continued fraction expansions are generally useful here - and then a computational complexity argument can be carried out. These and related matters (including my example for $\pi = 4 \text{atan}(1)$ above) are discussed in

M. Braverman, On the complexity of real functions, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), 2005.

Answer 2

I'm not familiar with computable analysis. But it seems to me that irrational numbers are not $O(1)$-computable: Let $r$ be an irrational number, and $(q_n)$ a Cauchy name for $r$. Suppose there exists a constant-time algorithm to compute $q : \mathbb{N} \rightarrow \mathbb{N}$. There is some constant $c$ such that the algorithm takes at most $c$ steps. In particular, the output of the algorithm can have at most $c$ bits, a contradiction to the fact that the number of decimal digits of $q_n$ tends to infinity. (Alternatively, if $q_n$ is represented as a fraction, the size of the denominator tends to infinity.)