Is PI a turing computable number? [closed]

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?

Heritor

I'm not quite sure what you mean by "PI is a real number, which cannot be enumerated by a T.M.". Yes, the real numbers are not enumerable, but I don't see how this affects whether PI is computable. 4 is also a real number, but that doesn't mean it's not computable. – Ehtelehud

Um, what I meant was, I thought it would take an infinitely long Turing Machine to compute PI as PI itself is infinitely long. – Heritor

@Gaurav: by that argument, would it take an infinitely long Turing machine to compute 1/3, since 1/3 = 0.333333... is infinitely long? – Conqueror

@katrielalex I thought because 1/3 can be represented as a fraction/equation, it wouldn't take an infinitely long tape to represent. Whereas PI cannot be represented in an equation. – Heritor

@Gaurav: sure it can: sin π = 0. – Conqueror

@katrielalex Ah, yes. Definitely missed that. – Heritor

@Gaurav: you may also be interested in the concept of definable numbers: en.wikipedia.org/wiki/Definable_real_number. Once again, these are countable. – Conqueror

The original question should probably go to cstheory.stackexchange.com ? – Tumble

Answer 1

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.

Conqueror

I think you mean almost all real numbers are not computable, as the set of Turing machines is countable. – Embouchure

Thanks for clearing that up! Cheers! – Heritor

got a source for this "definition"? – Zone

@Nuzzolilo pick your favourite textbook, or if you trust Wikipedia... – Conqueror

@Nuzzolilo and anyone else in doubt: youtube.com/watch?v=OYCxQqHFWTE – Schwing

This definition of pi being computable describes a procedure by which pi is never computed. It just means that pi is a number for which we can obtain better successive approximations using an algorithm; but never the number itself. It's seems silly to use the word "computable" to denote this concept. "Approximable" would be better. – Zanezaneski

@Zanezaneski How would you imagine a method that "computes" pi, then? This definition allows us to get any number of digits we want and need. To really "compute" it, we would have to have an infinite amount of time. – Heavyhearted

@IllidanS4 I wouldn't imagine such a thing. In its place, I would imagine a process which computes increasingly refined approximations of pi. – Zanezaneski