<p>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)}$ (<a href="http://arxiv.org/pdf/1112.4295v1.pdf">Datta and Pratap</a>). 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.</p>

CC BY-SA 3.0
2014-12-29T11:57:35.717Z
Excellent, But I have to think about it carefully. And I have just found that the Datta and Pratap is a paper that is just published recently.
XL _At_Here_There
CC BY-SA 3.0
2014-12-29T13:06:34.340Z
Presumably it had been known that the binary expansion of algebraic numbers can be computed in polynomial time. Their paper is just the first one I could find, and it actually proves stronger results.
Yuval Filmus
CC BY-SA 3.0
2014-12-30T00:32:05.837Z
Yes, I have conjectured for a long time that the binary expansion of algebraic numbers can be computed in polynomial time,but have not found any proof of that, thank you again for your answer and the referenced paper
XL _At_Here_There
CC BY-SA 3.0
2014-12-29T11:46:20.047Z
2014-12-29T11:46:20.047Z
Yuval Filmus
<p>In the 1965 article "<a href="http://dx.doi.org/10.1090/S0002-9947-1965-0170805-7" rel="nofollow">On the computational complexity of algorithms</a>" 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.</p>

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

CC BY-SA 3.0
2014-12-29T09:12:48.267Z
If I understand your question correctly, [Chaitin's constants](https://en.wikipedia.org/wiki/Chaitin%27s_constant) are examples of such numbers: They are transcendental and not computable at all.
Bruno
CC BY-SA 3.0
2014-12-29T11:25:52.613Z
@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
CC BY-SA 3.0
2014-12-29T16:59:30.343Z
My mistake, I didn't notice that you asked for a computable number...
Bruno
<cc.complexity-theory><reference-request><examples>
Hartmanis-Stearns conjecture and the computable transcendental numbers
XL _At_Here_There
# Hartmanis-Stearns conjecture and the computable transcendental numbers

(Asked by: username_0 on 2014-12-29)

In the 1965 article "[On the computational complexity of algorithms](http://dx.doi.org/10.1090/S0002-9947-1965-0170805-7)" 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?

**Tags:** cc.complexity-theory, reference-request, examples
> **Comments:**
> **username_1**: If I understand your question correctly, [Chaitin's constants](https://en.wikipedia.org/wiki/Chaitin%27s_constant) are examples of such numbers: They are transcendental and not computable at all.  
> **username_0**: @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.  
> **username_1**: My mistake, I didn't notice that you asked for a computable number...  

---

## 1 answers

### Answer by username_2 on 2014-12-29. Score: 10 | Accepted answer

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](http://arxiv.org/pdf/1112.4295v1.pdf)). 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.

> **Comments:**
> **username_0**: Excellent, But I have to think about it carefully. And I have just found that the Datta and Pratap is a paper that is just published recently.  
> **username_2**: Presumably it had been known that the binary expansion of algebraic numbers can be computed in polynomial time. Their paper is just the first one I could find, and it actually proves stronger results.  
> **username_0**: Yes, I have conjectured for a long time that the binary expansion of algebraic numbers can be computed in polynomial time,but have not found any proof of that, thank you again for your answer and the referenced paper  

---

