Non-computable numbers
Article Index
Non-computable numbers
Enumeration
Not enough programs

Enumerations

To see this you only have to think a little about iteration or enumeration.

Put simply anything you can count out is enumerable. Integers are enumerable - just write a for loop. Even an infinite number of integers are enumerable its just the for loop would take a little while longer to complete.

Now the next question is are the rationals enumerable?

The answer at first look seems to be no because of the following little problem.

Suppose you start your for loop at zero. The next integer is one but what is the next rational? The answer is that there isn't one. You can get as close as you like to zero by making the fraction smaller and smaller 1/10. 1/100, 1/1000 and so on. There is no next fraction (technically the fractions are "dense") and this seems to make writing a for loop to list them impossible.

However this isn't quite the point.

We don't need to enumerate the fractions in any particular order we just need to make sure that as long as the loop keeps going every rational number will eventually be constructed. So what about:

for i=0 to infinity
  for j=1 to i
    display i/j
 next j
next i

You should be able to see that if you wait long enough every fraction will eventually be displayed. In fact we are generating each fraction an infinite number of times because of identical terms like 1/2, 2/4. 4/8 and so on..

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.

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

3.14159...

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. 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.  It is as if you can have one infinite for loop and see results - but a pair of nested infinite loops is something non-computable.

 

Banner

 

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...

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 :

 .122...
 .348...
 .567...

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:

 .122...
 .348...
 .567...

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.

Banner

<ASIN:0521430690>

<ASIN:9810230818>

<ASIN:0285635948>

<ASIN:0691024472>



 
 

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