Not enough programs!

Now we come to the final knockout blow for computation.

How many programs are there?

Any program is simply a sequence of bits and any sequence of bits can be read as a binary number a binary integer to be exact. 

Thus given any program you have a binary number corresponding to it. Equally given any binary number you can regard it as a program - it might not do anything useful but that doesn't spoil the principle. 

Every program is an integer and every integer is a program. 

This correspondence is an example of a Godel numbering and it is often encountered in computer science. 

This mean that the set of programs is the same as the set of integers and we have immediately that the set of programs is enumerable.

All I have to do is write a for loop that counts from 1 to 2^N and I have all the programs that can be stored in N bits. 

Even if you let this process go to infinity the number of programs is enumerable. It is infinite but it is enumerable. 

This is a very strange idea. The Godel numbering implies that if you start generating such a numbering eventually you will reach a number that is Windows or Linux or Word or whatever program you care to name.

The important point is that the number of irrational numbers isn't enumerable which means in a sense that there are more irrational numbers than there are programs.

So what?

What a moment think about the task of computing each possible number. 

That is imagine each number has a program that computes it and displays it say.  You can do it for the integers and you can do it for the rationals but you can't do it for the irrationals.

There are more irrational numbers than there are programs so many, in fact most, irrational numbers don't have programs that compute them.

Numbers like the square root of 2, pi and e clearly do have programs that compute them so not all irrational numbers are non-computable - but the vast majority are non-computable.

I'll say that again -

most of the irrational numbers do not have programs that compute them.

What does this mean?

Well if you think about it a program is a shortish regular sort of construct and if it generates an irrational number then some how the information in that number must be about the same as the information in the program that generates it.

That is computable numbers are regular in some complex sense but a non-computable number is so irregular that you can't compress its structure into a program. 

This leads on to the study of algorithmic information theory which is another interesting area of computer science full of strange ideas and even strange conclusions.

Math too

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.

Transendental And Algebraic Irrationals

This lack of programs also spills over into classical math. Long before we started to worry about computability mathematicians had run into the problem. The first irrational numbers that were found were roots of simple polynomials - polynomials with rational coefficients. If you think about it for a moment you will see that a polynomial is a sort of program for working something out and finding the roots of a polynomial is also an algorithmic procedure. A few minutes thinking should convince you that there are only an enumerable set of polynomials and hence the set of irrationals that are roots of polynomials is en numerable. Such irrational numbers are called algebraic numbers and they are enumerable and as such they are a "small" subset of all of the irrationals.

That is most irrationals are not algebraic.

We call the bulk of the irrational numbers transcendental numbers and these are not the roots of any finite polynomial with rational coefficients.

So what are transcendental numbers?

Most of them don't have names but the few that do are well known to us Pi and e are perhaps the best known. The transcendental numbers that we can work with have programs that allow us to compute the digit sequence to any length we care to. In this sense the non-computable numbers are a subset of the transcendental numbers. That is the computable numbers are the integers, the algebraic irrationals and the transcendental that are regular enough in some sense as to have ways of computing them.

The situation is very strange when you try to think about it in terms of compuational complexity. The algebraic numbers are the roots of polynomials and in this sense they are easy computable numbers. The transcendentals are not the roots of polynomials and hence a harder class of things to compute. Indeed most of them are non-computable but some of them are. And some of them, like Pi, are fairly easy to compute.

<ASIN:0521430690>

<ASIN:9810230818>

<ASIN:0285635948>

<ASIN:0691024472>