Page 1 of 5 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 noncomputable 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.
Contents
 What Is Computable?
 Finite State Machines
 What is a Turing Machine?
 Computational Complexity
 Noncomputable numbers
 The Transfinite
 Axiom Of Choice
 Lambda Calculus
 Grammar and Torture
 Reverse Polish Notation  RPN
 Introduction to Boolean Logic
 Confronting The Unprovable  GĂ¶del And All That
 The Programmer's Guide to Fractals
 The Programmer's Guide to Chaos*
 Prime Numbers And Primality Testing
 Cellular Automata  The How and Why
 Information Theory
 Coding Theory
 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 righthand 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 55?". 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>
