Non-computable numbers

New Book Reviews!

 Non-computable numbers
Written by Mike James
Saturday, 19 December 2015
Article Index
Non-computable numbers
The Irrationals
The Standard Theory

What are the limits to computation? The computer science theory of computation can be intimidating because of its use of logic but taking a programmer's approach makes it seem much simpler. So if you want to know what a non-computable number is - read on.

One of the big topics of computer science is computability and it can often seem mysterious and strange.

How can there be things that aren't computable?

The whole idea seems silly.

There is another way of looking at the question that is more the way that a programmer would think about it - so let's get started.

To be 100% clear this is a general discussion about ways of thinking about computability and not formal theorem and proof. Some of the ideas expressed here can be turned into exact proofs others are better expressed in different and more precise language before proving them.

The central issue is about how much "stuff" there is in anything. I'm not going to bore you with stories about the history of numbers - fascinating though it is (and you can explore some recommended book titles by following links in right-hand panel).

All you really need to know is that in the beginning were the whole numbers, which we can confuse with the integers (which include zero and the negative numbers). Then there were fractions and the these where to fill in all the spaces on the number line.

That is, if you draw a line between two points then each point will correspond to an integer or a fraction on some measuring system.

The fractional numbers are usually known as the rationals because they are a ratio of two integers.

A small part of the number line to every number there is a point but is the reverse true?
Is there a number for every point?

Notice that if you pick any two points on the line then you can always find another fractional point between them. In fact if you pick any two points you can find an infinity of fractions that lie between them. This is quite unlike the integers where there most certainly isn't an integer between every pair of integers - for example what is the integer between 1 and 2?

The fractions or rationals  form a dense set that seems to cover the entire number line - but do they?

The irrationals

Now, with the integers and the fractions there is a number to every point and a point to every number - NO!

This is wrong but it is far from obvious that it is wrong.

If you think it is obviously wrong then you have been exposed to too much math - not in itself a bad thing but it can sometimes make it harder to see the naive view point.

What happened was that some followers of Pythagoras discovered a shocking truth - that there were points on the line that didn't correspond to integers or fractions.

The square root of two is one such point.

You can find the point that corresponds to the square root of two simply by drawing a unit square  and drawing the diagonal - now you have a line segment that  is exactly the square root of two long and thus lines of that length exist and are easy enough to construct.

That is you can find a point on the line that is the square root of two quite easily.

So far so much basic math but, and this is the big but, it can be proved (fairly easily) that there can be no fraction i.e. a number of the form a/b that is the square root of two.

You don't need to know the proof to trust its results but the proof is very simple but skip this section if you want to.

Suppose that you can express the square root of 2 as a rational number in its lowest terms i.e. all factors cancelled out, as a/b. Then (a/b)2 is 2 by definition and hence a2=2b2.

This implies that a2 is even and hence a has to be even (as odd numbers squared are still odd).

Suppose a=2c for some integer c.
Then 4c2=2b2 or b2=2c2 and hence b2 is also even and hence b is even.

Thus b=2d for some integer d.

Now we can write a/b=2c/2d which means that a/b isn't in its lowest form as we can now remove a factor of 2 to get c/d.

As you can reduce any fraction to its lowest form by cancelling common factors there can be no a/b that squares to give 2.

You can show that a line square root of two long exists and so there has to be a point on the number line that is that far from zero. Is there a rational number corresponding to this point? The simple answer is no!

What this means is that if we only have the integers and the fractions or the rationals (because they are a ratio of two integers) then there are points on the line that do not correspond to a number - and this is unacceptable.

The solution is that we simply expanded what we regard as a number and the irrational numbers were added to the mix.

Now we have integers like one or two, fractions like 5/6 and irrationals like the square root of two.

From the point of view of computing this is where it all gets very messy.

Enumerations

To see this you only have to think a little about iteration or enumeration.

Put simply anything you can count out is enumerable.

Integers are enumerable - just write a for loop.

`for i=0 to 10 display inext i`

which enumerates the integers 0 to 10.

Even an infinite number of integers are enumerable its just the for loop would take a little while longer to complete!

`for i=0 to infinity display inext i`

Ok, the loop would never end but if you wait long enough you will see every integer displayed. In this sense, the integers, all of them, are enumerable.

Now the next question is are the rationals enumerable?

The answer at first look seems to be no because of the following little problem.

Suppose you start your for loop at zero.

The next integer is one but what is the next rational?

The answer is that there isn't one. You can get as close as you like to zero by making the fraction smaller and smaller 1/10. 1/100, 1/1000 and so on. There is no next fraction (technically the fractions are "dense") and this seems to make writing a for loop to list them impossible.

However this isn't quite the point.

We don't need to enumerate the fractions in any particular order we just need to make sure that as long as the loop keeps going every rational number will eventually be constructed. So what about:

`for i=1 to infinity  for j=1 to i    display j/i next jnext i`

You should be able to see that if you wait long enough every fraction will eventually be displayed. In fact we are generating each fraction an infinite number of times because of identical terms like 1/2, 2/4. 4/8 and so on..

We can agree that even an infinite set is enumerable as long as you are guaranteed to see every element if you wait long enough.

<ASIN:0521430690>

<ASIN:9810230818>

<ASIN:0285635948>

<ASIN:0691024472>

Last Updated ( Friday, 22 January 2016 )