If you are now thinking that programs to compute numbers aren't that important let's take one final rephrasing of the idea.

Consider a mathematical formula.

It is composed of an enumerable set of n symbols and as such the set of all formulae is itself enumerable. Which means that there are more irrational numbers than there are mathematical formulae.

In other words, if you want to be dramatic, most of the numbers in mathematics are out of the reach of mathematics.

There are some subtle points that I have to mention to avoid the problem of you inventing "solutions" to the problem.

Surely you can write an equation like x=a where a is an irrational number and so every irrational number has its equation in this trivial sense.

The problem here is that you cannot write this equation down without writing an infinite sequence of digits - i.e. the numeric specification for a.

Mathematical formulae can't include explicit irrational numbers unless they are assigned a symbol like pi or e and these irrationals, the ones we give a symbol to are exactly the ones that have formulae that define them.

That is the computable irrational numbers are the ones we often give names to.

The same argument holds for programs.

Also notice that if you allow general irrational numbers within a program or a formula then the set of programs or formulae is no longer enumerable. What this means is that if you extend what you mean by computing to include irrational numbers within programs then the irrationals become computable. So far this idea hasn't prove particularly useful because practical computation is based on enumerable sets.

The standard theory

Now that we have arrived at these major conclusions it might be worth giving some of the more standard math.

Mathematicians say that two sets are equal in size if you can pair up items in one set with the items in the other one-to-one with none left over - they have the same cardinality and this idea works for infinite sets as well as finite ones.

All finite enumerable sets have cardinality equal to the number of elements they contain {a,b,c} has cardinality 3.

All infinite enumerable sets can be put into one-to-one correspondence and so have the same cardinality which is traditionally called Aleph Zero or enumerable infinity.

Aleph zero the size of the first or countable infinity

The set of real numbers i.e. including the irrationals isn't enumerable and is a "bigger" set than an enumerable set - it has cardinality Aleph One and is the infinity of the continuum i.e. the full number line.

There are a whole set of increasingly large infinities with cardinality Aleph Two, Three and so on..

And, yes, the set of infinities is thought to be an enumerable infinity - but I don't think anyone has proved the enumerable part as yet.

If you want to know more look up transfinite numbers.

This is more or less the end of the story but it really is just the beginning.

Recursion is often said to separate real programmers from the pack. What is it that makes it so powerful? What is it that makes it so difficult? What is the "shape" of recursion as a flow of control?

Finite state machines may sound like a very dry and boring topic but they reveal a lot about the power of different types of computing machine. Every Turing machine includes a finite state machi [ ... ]