Search code examples
numbersturing-machinescomputability

Is PI a turing computable number?


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?


Solution

  • 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.