11

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?

Gaurav Dadhania
  • 5,167
  • 8
  • 42
  • 61
  • 1
    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. – sepp2k Nov 09 '10 at 13:57
  • Um, what I meant was, I thought it would take an infinitely long Turing Machine to compute PI as PI itself is infinitely long. – Gaurav Dadhania Nov 09 '10 at 14:11
  • 1
    @Gaurav: by that argument, would it take an infinitely long Turing machine to compute `1/3`, since `1/3 = 0.333333... ` is infinitely long? – Katriel Nov 09 '10 at 14:18
  • @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. – Gaurav Dadhania Nov 09 '10 at 14:26
  • 1
    @Gaurav: sure it can: `sin π = 0`. – Katriel Nov 09 '10 at 14:27
  • @katrielalex Ah, yes. Definitely missed that. – Gaurav Dadhania Nov 09 '10 at 14:38
  • @Gaurav: you may also be interested in the concept of definable numbers: http://en.wikipedia.org/wiki/Definable_real_number. Once again, these are countable. – Katriel Nov 09 '10 at 14:49
  • The original question should probably go to http://cstheory.stackexchange.com/ ? – DuckMaestro Jun 19 '11 at 03:24

1 Answers1

16

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.

Katriel
  • 120,462
  • 19
  • 136
  • 170
  • 2
    I think you mean almost all real numbers are *not* computable, as the set of Turing machines is countable. – Fred Foo Nov 09 '10 at 13:57
  • Thanks for clearing that up! Cheers! – Gaurav Dadhania Nov 09 '10 at 14:11
  • got a source for this "definition"? – marknuzz Apr 03 '13 at 21:50
  • @Nuzzolilo pick your favourite textbook, or if you trust [Wikipedia](http://en.wikipedia.org/wiki/Computable_number)... – Katriel Apr 04 '13 at 08:28
  • @Nuzzolilo and anyone else in doubt: https://www.youtube.com/watch?v=OYCxQqHFWTE – Fizz Feb 22 '15 at 12:26
  • 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. – Kaz Jun 03 '15 at 18:31
  • 1
    @Kaz 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. – IS4 Oct 29 '15 at 18:52
  • @IllidanS4 I wouldn't imagine such a thing. In its place, I would imagine a process which computes increasingly refined approximations of pi. – Kaz Oct 30 '15 at 21:11