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.

A Programmers Guide To Theory
First Draft

There is a more recent version of this:

Now available as a paperback and ebook from Amazon.

A Programmers Guide To Theory - NP & Co-NP

Contents

1. What Is Computable?
2. Finite State Machines
3. What is a Turing Machine? 
4. Computational Complexity
5. Non-computable numbers
6. The Transfinite
7. Axiom Of Choice
8. Lambda Calculus
9. Grammar and Torture
10. Reverse Polish Notation - RPN
11. Introduction to Boolean Logic
12. Confronting The Unprovable - Gödel And All That
13. The Programmer's Guide to Fractals
14. The Programmer's Guide to Chaos*
15. Prime Numbers And Primality Testing
16. Cellular Automata - The How and Why
17. Information Theory
18. Coding Theory
19. Kolmogorov Complexity

*To be revised

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.

On the way we need to look at numbers that are computable and generally poke about in the basement of mathematics to discover what sorts of number lurk.

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).

But first the simple numbers that we all know.

Integers & Rationals

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). The whole numbers or counting numbers are just the one's we need to count things and in most cases these don't include zero which was quite a late invention. After all who counts zero things?!

The integers are what you get when you add zero and negative numbers. You need the negatives to solve problems like "What do I add to 5 to get 3?" and zero appears as a result of "What is 5-5?". You can motivate all of the different types of number by the need to solve equations of particular types. So the integers are the solution to equations like:

x+a=b

Notice that there are an infinity of counting numbers and an infinity of integers.

Then there are the 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.  That is the rationals are solutions of equations like

x*a=b

A small part of the number line to every rational 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?

Also notice that this seems to be a very different sort of infinity to the countable infinity of the integers. It is indeed the "small" infinity in that there are an infinite number of rational points in any small section of the line. Compare this to the "big" infinity of the integers which extends forever. You can hold an infinite number of rationals in your hand but not so much an infinity of integers.

Despite these differences the two types of infinity are infact the same - they are of the same size.

The rational numbers are countable as will be explained a little later.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. Another way of looking at this is that the point that is the square root of two exists but does a rational number that labels it?

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.

<ASIN:0521430690>

<ASIN:9810230818>

<ASIN:0285635948>

<ASIN:0691024472>