Page 1 of 3
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 filled 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.
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 usually fractional point between them. In fact if you pick any two points you can find an infinity of fractions that lie between them. The fractions form a dense set that "covers" the number line.
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 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.