Non-computable numbers
Non-computable numbers
Written by Mike James   
Saturday, 19 December 2015
Article Index
Non-computable numbers
The Irrationals
The Standard Theory

Enumerating the irrationals

Fractions and hence the rationals are enumerable.

The next question is - are the irrationals enumerable?

At first sight it seems not by the same argument that there is no "next" irrational number but as we have seen this argument failed with the rationals because they are enumerable.

However first we have another problem to solve - how do we write down the irrationals? 

It is clear that you can write them down as anything like a/b so how do you do it?

After lots of attempts at trying to find a way of representing irrational numbers the simplest way of doing the job is to say that an irrational number is represented exactly by an infinite sequence of digits - for example


where the ... means "goes on for ever".

You can see that a single irrational number is composed of an  enumerable sequence of digits. For example

for i=0 to infinity
 display the ith number
   of the square root of two
next i

Now what about the entire set of irrational numbers?

This is quite a different problem because now you have a nested set of for loops that both go on to infinity

for i=0 to infinity
 for j=0 to infinity
  display jth digit of the
  ith irrational
 next j
next i

The problem here is that you never get to the end of the inner loop so the outer loop never steps on by one. 

In other words, no matter what the logic of the program looks like, it is, in fact, equivalent to:

 for j=0 to infinity
  display jth digit of the 
  ith irrational
 next j

The original nested loops only appear to be an enumeration because they look like the finite case. In fact the program only ever enumerates the first irrational number you gave it.

Its quite a different sort of abstraction to the enumeration of the rationals and while it isn't a proof that you can't do it - it does suggest what the problem might be.

As the inner loop never finishes the second loop never moves on to another value of i and there are huge areas of the program that are logically reachable but are never reached because of the infinite inner loop. 

It is as if you can have one infinite for loop and see results, all the results if you wait long enough - but a pair of nested infinite loops is something non-computable because there are results you will never see no matter how long you wait.




The point is that you can't enumerate a sequence of infinite sequences. You never finish enumerating the first one so you never get to the second...

As already stated this isn't a proof but you can construct a proof out of it to show that there is no effective enumeration of the irrationals.

But this isn't about proof, it's about seeing why an infinite sequence of infinite sequences is different from just an infinite sequence.

Cantor's diagonal argument

If you do want a proof then the standard one is called "Cantor's diagonal argument" and its an argument by contradiction as are most of the arguments in this area of computer science.

Suppose you do have a complete enumeration of the irrationals and you decided to print out a table of the first few digits of the first few numbers.

For example a 3x3 section of the table might be :


Now construct a new irrational number by taking the first digit to be different from the first digit of the first irrational number 3 say, the second digit to be different from the second digit of the second irrational number 6 say and finally its third digit to be different to the third digit of the third number 4 say.

That is construct a new number by taking each digit in the diagonal and creating a number that uses a different digit in that location:


and our number is different from .147 e.g. .364

Now we have a new irrational number .364 and you are guaranteed that it is not in the table so far because it differs from the nth enumerated irrational in the nth digit.

So what you may say this is just an irrational number that we haven't generated yet. Let's make the table bigger by enumerating some more irrational numbers till we find the constructed value. Unfortunately at this point I can use the same trick to construct another number that isn't in the table.

No matter how big you make the table I can always find a number that isn't in it and so your compete enumeration of the irrationals cannot be done.

So looking at what can and cannot be enumerated has revealed some interesting things about the way we can work with infinity but what has this to do with non-computable numbers?

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. 

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.






Last Updated ( Friday, 22 January 2016 )

RSS feed of all content
I Programmer - full contents
Copyright © 2018 All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.