Is PI a turing computable number? [closed]

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

开发者_运维百科

Closed 11 years ago.

Improve this question

AFAIK, turing computable numbers are numbers whose i-th index can be returned by a Turing Machine. So a non-computable number would be something like a number whose decimal points are decided if some other program halts on some other input, etc. But then again, PI is a real number, which cannot be enumerated by a T.M. and thus, cannot be computed? So which school of thought is correct?

---

Yes, π is computable. There are a few equivalent definitions of computable, but the most useful one here is the one you have given above: a real number r is computable if there exists an algorithm to find its nth digit. Here is such an algorithm.

Your last argument is not sound; you have confused the definition "can find the nth digit" with "can enumerate all the digits". The latter is not a useful definition: it rules out all the irrationals and many rationals as well!

An interesting fact is that the computable numbers are in fact countable, since we may Godel-number the Turing machines which produce them. Hence almost no reals are computable.