Welcome to NRICH.

 
Computable numbers: Turing machines and pi
By Andrew Smith (P2517) on Saturday, August 26, 2000 - 10:58 pm:

I have been reading a book about Alan Turing which says that pi is a computable number. How would it be represented on the "tape" (in binary maybe)? Also it says that it can be done by using an infinite series, if this is so how would the Turing machine "store" the data as it goes along? For example if one of the terms was 1/3 then this gives an infinite decimal but the program isn't allowed to take an infinite amount of time to store the term.

Any answers would be appreciated, thanks.

By Sean Hartnoll (Sah40) on Saturday, August 26, 2000 - 11:10 pm:

A first thought is that it doesn't need to store the infinite series, in just needs to be able to reproduce the nth term in finite time, which would answer the question, "what is the nth term of pi, or 1/3?".

So just storing 1, /, 3, with a binary representation of these symbols and an algorithm for calculating the nth term of the result. this will always be finite time because we cannot ask for the 'infinite term' because it doesn't exist.
Pi could be represented to successive accuracy by any of the series, such as sum 1/n2 = pi2/6.

Sean

By Michael Doré (P904) on Sunday, August 27, 2000 - 12:52 am:

I'm not sure what a computable number is, but maybe it means one in which there is an algorithm (or computer program) with which you can calculate the nth decimal place.

If this is true then I think we can say (using a bit of set theory) that most real numbers are not computable.

Consider the set of all computer programs. These are all a finite string of characters (the string has no upper limit on length but the strings are finite), and the number of possible characters (in whatever language) is finite. Therefore there are a countably infinite number of computer programs obviously (in the same way that there are a countably infinite number of decimals which have a finite number of places, under any base). But there are uncountably many irrational numbers. Therefore most numbers cannot have an associated computer program which will calculate any decimal place, because there aren't enough possible computer programs to go round!

p though would be one of the numbers which there is a computer program for. As Sean says you could use the first few terms of a series to calculate the value of any decimal place.

Michael

By Dan Goodman (Dfmg2) on Sunday, August 27, 2000 - 02:14 am:

Yes, the definition of a computable number is one for which there is a program that computes the nth place of the number. So, 1/3 and p are both computable. Interesting fact of the day, the set of computable numbers is not complete, i.e. you can have a series of computable numbers that don't tend to a computable number. This seems improbable, but a construction can be found. Also, Michael is correct, the computable numbers are countable.

By Andrew Smith (P2517) on Sunday, August 27, 2000 - 05:09 pm:

If I wanted to work out the tenth decimal digit of pi2/6 then as Sean said above I could use the sum of 1/n2. How can you tell though when you have got the correct tenth digit, i.e. how many terms would you need to use? Also I think from what people have said it would be necessary to approximate each term, for example 1/32 couldn't be recorded exactly in decimal or binary. I thought that approximating each term to say 20 decimal places would be good enough because eventually all terms would be less than 10-20 so this would produce the tenth decimal place correctly but applying this to the harmonic series would give a finite answer where the answer should of course be infinite. The fact that we know pi2/6 is finite probably helps but I expect there are series which converge to a finite limit which would give an incorrect answer using my system from above. Is there a more reliable system for finding the nth digit? Thanks.

By Michael Doré (P904) on Sunday, August 27, 2000 - 06:41 pm:

This is one possibility. (It is a bit messy but the best I can think of at the moment.)

Let f(n) = 1/12 + 1/22 + ... + 1/n2

Now p2/6 > f(n) for all integral n.

Also:

p2/6 = 1/12 + 1/22 + ... + 1/(2n-1)2

+ 1/(2n)2 + 1/(2n+1)2 + 1/(2n+2)2 + ...

Now:

1/(2n)2 > 1/(2n+1)2
1/(2n+2)2 > 1/(2n+3)2
1/(2n+4)2 > 1/(2n+5)2
...

So:

p2/6 < 1/12 + 1/22 + ... + 1/(2n-1)2

+2[1/(2n)2 + 1/(2n+2)2 + 1/(2n+4)2 + ...]

So p2/6 < f(2n-1) + 1/2[p2/6 - f(n-1)]

So:

2 p2/6 < 2f(2n-1) + p2/6 - f(n-1)

And:

p2/6 < 2f(2n-1) - f(n-1)

Therefore p2/6 lies between f(2n-1) and 2f(2n-1)-f(n-1). So when these agree to 20 d.p. we know the 20th decimal place. They definitely will eventually agree to 20 d.p. because they both tend to p2/6. And you can find the value f(2n-1) and 2f(2n-1)-f(n-1) exactly as the ratio of two integers so it is easy to check they agree to 20 d.p.

Yours,

Michael

By Sean Hartnoll (Sah40) on Sunday, August 27, 2000 - 10:07 pm:

Some interesting points here...

Dan's point that the computable numbers are not complete (did you mean closed or complete in the sense of Cauchy sequences?) follows immediately, I guess, once we have established that there are countably many computable numbers and that all rationals are computable and that the completion of the rational numbers are the reals, which are uncountable.

However, this is very counterintuitive because every real number is the limit of a sequence of rationals. So Pi is the limit of 3, 3.1, 3.14, 3.141 ...

And this seems to allow us to calculate the nth digital place of an arbitrary real number with a finite code. So doesn't this mean all reals are computable?? Or perhaps some for some numbers the sequence required is not computable??

Does anyone know how to going about constructing an uncomputable number, as I think that might answer the above questions?

Sean

By Michael Doré (P904) on Sunday, August 27, 2000 - 10:14 pm:

It is true that a computer program can calculate any rational number to any no. of d.p.s, and that all irrational numbers are the limit of a sequence of rationals. However if a computer program was to construct an irrational number by reference to a rational sequence then it would have to store the ENTIRE rational sequence. (i.e. it would have to store 3.1, 3.14, 3.141, 3.1415 etc). And it can't store an infinite amount of rational numbers because the length of the program is finite. Unless of course the rationals in the sequence follow some sort of pattern but if you do this then you are limited to only a countable amount of irrational numbers as the limit.

By Tom Hardcastle (P2477) on Sunday, August 27, 2000 - 11:39 pm:

Sean, surely the point about uncomputable numbers is that there isn't a way of constructing them; if there was, then they would be computable. The universal Turing machine is theoretically capable of reproducing the processes of any machine; if the universal Turing machine can't do it, neither can we. Which was why Turing suggested his machine, to answer Hilbert's question about mechanical processes.

Tom

By Sean Hartnoll (Sah40) on Monday, August 28, 2000 - 12:19 am:

Fair point, but it would be interesting to see a direct proof (i.e. one that does not go via the countability) that there are real numbers that cannot be written as some sort of pattern.

Sean

By Dan Goodman (Dfmg2) on Monday, August 28, 2000 - 01:09 am:

I think the reason that there are uncomputable numbers which are the limit of computable numbers is because of two reasons, the first by Tom above. The second possibility is a sequence of computable xn tending to x, i.e. for all e>0, there is an N>0 such that n>=N implies |xn-x|<e (definition of xn tending to x), but you don't know what the integer N is!

Here is a construction for an uncomputable real number which is the limit of computable reals. Let xn=0.b0b1b2b3... with each bi in {0,1} and bi=1 if the ith turing machine stops in less than or equal to n steps, or bi=0 if not. Clearly xn is computable, you just run the appropriate turing machine for a certain number of steps and see whether it has stopped or not. Moreover, xn tends to a limit, as xn is increasing (because if i>j then bi>bj) and is less than 1. However, if x was computable, we would have a turing machine which could solve the halting problem (to test whether the nth turing machine stopped, just compute the nth digit of x), which isn't possible. Computability is very counterintuitive I think.