1
$\begingroup$

The fact that square root of 2, pi etc are computable numbers only means they can be approximated to arbitrary nth decimal, so these TM that approximate them do not count since they halt after printing out the nth digits. I would appreciate a definitive answer and reasoning. If the answer is NO, which I suspect, is the following statement equivalent? Any TM with blank tape input can only print rational numbers, assuming its alphabets are coded in integers.

$\endgroup$
  • $\begingroup$ I don't see any difference between printing every digit of $1/3$ and printing every digit of $\sqrt{2}$. $\endgroup$ – Willard Zhan Jan 22 '17 at 14:42
  • $\begingroup$ If you're talking about printing a number in a given base (e.g. base 10), you cannot print irrational numbers, because their representation is infinite. Similarly most of rational numbers in any given base are infinite. You cannot simply print out 1/3 in base 10 with using only digits and decimal point. Basically it all boils down what you permit when you say "print". Is recursion as in $0.\overline{3}$ ok? Is $\sqrt{2}$ ok? $\endgroup$ – Ordoshsen Apr 22 '18 at 5:53
1
$\begingroup$

I choose to represent numbers in base $\pi$. My machine prints $10$ and terminates, that's exactly $\pi$.

A Turing machine performs meaningless operations on meaningless objects, you provide the semantics, you find meaning in the computation. The answer to your question is a direct consequence of how you decide to represent numbers with the finite alphabet of the machine. It is certainly true that not all real numbers can be exactly computed under an unified semantics by Turing machines: there are uncountably many real numbers but countably many Turing machines.

But you might be able to represent some of them. For instance, with enough symbols to write integers, fractions, square roots and the imaginary unit, you can represent exactly the segments constructible with straightedge and compass, each of them in a finite amount of space.

$\endgroup$

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.