# Hartmanis-Stearns conjecture and the computable transcendental numbers

In the 1965 article "On the computational complexity of algorithms" by Hartmanis and Stearns, the authors conjecture that if a real-time Turing Machine computes the real number $r$ in, for example, base 10, then $r$ is either a rational number or a transcendental number.

Is there a computable transcendental number that is not computable by a real-time Turing machine in, for example, base 10?

• If I understand your question correctly, Chaitin's constants are examples of such numbers: They are transcendental and not computable at all. – Bruno Dec 29 '14 at 9:12
• @Bruno，but Chaitin's constants is not computable, or semicomputable, so it is not the numbers that is computable transcendental number and is not computable by a real-time Turing machine. – XL _At_Here_There Dec 29 '14 at 11:25
• My mistake, I didn't notice that you asked for a computable number... – Bruno Dec 29 '14 at 16:59

Let $L$ be an EXPTIME-complete language, and let $r \in (0,1)$ be the corresponding real. Clearly $r$ is computable. The number $r$ cannot be algebraic since the $n$th bit of an algebraic number can be computed in time $n^{O(1)}$ (Datta and Pratap). Since the $n$th bit of any number computable by a real-time Turing machine can be computed in time $O(n)$, $r$ cannot be computed by a real-time Turing machine.