Not Enough Formulas!

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 formulas is itself enumerable. Which means that there are more irrational numbers than there are mathematical formulas. 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 mistake of 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 formulas can't include explicit irrational numbers unless they are assigned a symbol like π or e and these irrationals, the ones we give a symbol to, are exactly the ones that have formulas that define them. That is, the computable irrational numbers are the ones we often give names to. They are the ones that have specific properties that enable us to reason about them. For example, I can use the symbol √2 to stand as the name of an irrational number, but this is more than a name. For example, I can do exact arithmetic with the symbol:

√2(1+√2)²=2(1+2√2+√2√2)= 2(1+2√2+2)=2(3+2√2)=6+4√2.

We repeatedly use the fact that √2√2=2 and it is this property, and the ability to compute an approximation to √2, that makes the symbol useful. This is not the case for irrational numbers in general and we have no hope of making it so. That is, a typical irrational number requires an infinite sequence of symbols to define it. For a few we can replace this by a finite symbol, like √2, that labels its properties and this allows it to be used in computation and provides a way of approximating the infinite sequence to any finite number of places.

Also notice that if you allow irrational numbers within a program or a formula then the set of programs or formulas 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.

Transcendental and Algebraic Irrationals

This lack of programs to compute all the numbers 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 polynomial is something like:

axⁿ+bx^n-1+cx^n-2+ ..

For example:

2x⁴+1/2x³+8x²+9x+13

is a polynomial of degree 4.

A few minutes thinking should convince you that there are only an enumerable set of polynomials. You can encode a polynomial as a sequence:

(a,b,c.. )

where the a, b, c are the coefficients of the powers of x. The length of the sequence is finite but unbounded. As in the earlier argument each of these sets for fixed, n is countable and hence the union of all of these sets is countable and hence there are aleph-zero polynomials. If you don’t like this argument write a program that enumerates them but you have to use a zig-zag enumeration like the one used for the rationals.

As the set of polynomials is countable, and each polynomial has at most n distinct roots, the set of all roots is also countable and hence the set of irrationals that are roots of polynomials is enumerable. That is, there are aleph-zero irrationals that are the roots of polynomials. Such irrational numbers are called algebraic numbers, they are enumerable and as such they are a "small" subset of all of the irrationals, which is aleph-one and hence much bigger. That is, most irrationals are not algebraic numbers. We call this bulk of the irrational numbers transcendental numbers and they 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 - π 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, in this sense the computable numbers are the integers, the algebraic irrationals and the transcendentals that are "regular enough" to have ways of computing approximations.

The situation is very strange when you try to think about it in terms of computational 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, like π, are fairly easy to compute.