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

Pretty Good Privacy 2.6ui - Public-key encryption for the masses. (c) 1990-1993 Philip Zimmermann, Phil's Pretty Good Software. 27 May 94 Date: 1994/07/28 03:23 GMT You need a pass phrase to unlock your RSA secret key. Key for user ID "Dietrich J. Kappe <kap1@tao.cpe.uchicago.edu>" Enter pass phrase: