10
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ If I understand your question correctly, Chaitin's constants are examples of such numbers: They are transcendental and not computable at all. $\endgroup$
    – Bruno
    Dec 29, 2014 at 9:12
  • $\begingroup$ @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. $\endgroup$
    – XL _At_Here_There
    Dec 29, 2014 at 11:25
  • $\begingroup$ My mistake, I didn't notice that you asked for a computable number... $\endgroup$
    – Bruno
    Dec 29, 2014 at 16:59

1 Answer 1

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – XL _At_Here_There
    Dec 29, 2014 at 11:57
  • $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Dec 29, 2014 at 13:06
  • $\begingroup$ 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 $\endgroup$
    – XL _At_Here_There
    Dec 30, 2014 at 0:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.