Numbers which are "Provably Difficult to Compute"?

Question

We recall that a computable number $\alpha \in \mathbb{R}$ satisfies the following: there exists a computable function $f$ such that, given any positive rational error bound, $f$ outputs a rational number $q=f(\epsilon)$ satisfying $\vert \alpha -q \vert < \epsilon$.

Do there exist formulations of computability that provide definite bounds on the runtime of $f$? For example, one could ask for which real numbers $\alpha$ there exists a computable function $f$ that returns the first $n$ digits of $\alpha$ (or some equivalent accuracy, to solve the rounding problem) in $O(n)$ time.

My question is this: are there examples of computable numbers $\alpha$ for which it is known that no algorithm for computing $\alpha$ can return an $n$-digit approximation to $\alpha$ in $O(\phi(n))$ time, for fixed function $\phi$? Such numbers would be, intuitively, "provably difficult to compute."

Answer 1

The time hierarchy theorem shows how to construct subsets of $\mathbb N$ that are (almost) arbitrarily difficult to decide. If you take such a subset $A$ and define $\alpha$ to have its binary digits given by whether their positions are in $A$ or not, you have a number that is "provably difficult to compute".

Answer 2

You can indeed ask for bounds on the run time. In the area I am working in at the moment, this kind of requirement is used to define a convenient setting in which to state results. Two kinds of approximation are useful:

• getting $n$ digits in polynomial time in $n$; for example this paper
• getting $\log n$ digits in polynomial time in $n$; this requirement is equivalent to saying that $e^\alpha$ has a fully polynomial time approximation scheme or is "efficiently approximable"

To answer your last question: yes, the time hierarchy theorem will give you all the hard-to-compute functions you want.

Answer 3

Are you defining the number in terms of a given algorithm or its output? If the latter I suspect no such nontrivial number is known. See https://cstheory.stackexchange.com/questions/9840/what-are-some-problems-where-we-know-we-have-an-optimal-algorithm