Continum of numbers and Turing Machines

[Perry E. Metzger]

Andrew Purshottam says:
> Marvin Minsky's old automata theory text
> (something like "Finite and Infinite Machines") 
> has an intro to the computable reals (or constructable reals? 
> can't remember) which the interested might like to read.

I'll point out that the countability of the reals (or, rather,
uncountability) is a simple concept -- I've explained it in five
minutes to a twelve year old, so I see no reason why it can't be
quickly explained here. (I haven't paid much attention -- perhaps
someone else has done this already but I haven't noticed it.)

An infinite set is said to be countable if it can be mapped one to one
to the integers. (Actually, to the cardinals, or positive integers, in
most definitions, but it doesn't matter as I'll show in a moment). As
an example, I can map the even positive numbers to the positive
numbers very easily -- use the "divide by two" operator, and I can
map every even positive number to a positive integer, and vice versa.
All integers may be mapped to the positive integers in an equally
simple manner -- start by numbering 0 as 1, 1 as 2, -1 as 3, 2 as 4,
-2 as 5, 3 as 6, and in general all positive n go to 2n and all
negative n go to -2n+1.

It would seem that the rational numbers couldn't be counted, but in
fact they can -- you just have to be clever. Build a table like so
(I've only partially filled it in :-) and think of the row index as the
numerator and the column index as the denominator -- you will swiftly
see that you can number every fraction. (Actually, you overnumber them
in the sense that some numbers get more than one index this way --
fixing this is left as an exercise to the reader...)


       1   2   3   4   5   6   7   8 ....
1      1   3   6  10  15  21  28  36  
2      2   5   9  14  20  27  35
3      4   8  13  19  26  34
4      7  12  18  25  33
5     11  17  24  32
6     16  23  31
7     22  30
8     29
...

Now, you might think some clever trick could be used to map the reals
into the integers. Unfortunately, you cannot do it. I can prove that
quite easily, by contradiction.

For simplicity, lets just try to map the reals between zero and one to
the integers, and lets consider them expressed as binary numbers.

Imagine that I had built a mapping between this subset of the reals
and the positive integers. Any such mapping implies a list, that is,
that I could build a table like

1   .1010101101010010010010010101001.....
2   .0100001010100010100101001001010010...
3.  .11000101001010110100010100010101001....

etc.

I can now construct a number that is not in the table. Take the first
binary digit from the first number in the table, and complement it. That
is the first digit in my constructed number. Take the second digit
from the second number and complement it -- that is the second digit
of the constructed number. Add in the complement of the third digit of
the third, the fourth digit of the fourth, etc. The number I have just
constructed can't be the first number in the imaginary table because
the first digit didn't match. It can't be the second because the
second didn't match. It can't be the third because the third doesn't
match. Indeed, it can't be any of them. Thus, you can't map the reals
to the integers.

The reals are thus in some sense a "bigger" infinite set than the
integers. 


Perry