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?

$\endgroup$
  • $\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 '14 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_China Dec 29 '14 at 11:25
  • $\begingroup$ My mistake, I didn't notice that you asked for a computable number... $\endgroup$ – Bruno Dec 29 '14 at 16:59
9
$\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.

$\endgroup$
  • $\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_China Dec 29 '14 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 '14 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_China Dec 30 '14 at 0:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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