The nature of infinite things 

For 60 years I've believed the argument that there are an uncountable infinity of real numbers. The argument goes roughly like this:

Suppose that there are a countable number of reals in [0,1), i.e. at least 0 and less than 1. This means that there is a 1-1 correspondence between those reals and the natural numbers from 1 up. We create this list of reals showing the sequence of decimal digits for each. But we can now create a new real number in [0,1) by setting its nth digit to be 1 more modulo 10 (i.e. 9->0) than the nth digit of the nth entry. Now we've created a new real that differs from every real in the list, contradicting our assumption that the list is complete.

 I now believe that this argument is wrong because it assumes that one can carry out operations that can't actually be carried out. To see this let's consider a related argument: that there exist non-computable reals.

Our definition of a computable real in [0,1) is a procedure that takes a natural number n, and returns that number's nth digit after the decimal place. A procedure in any turing-complete language is just a sequence of characters from some finite alphabet. So we can represent each character by a sequence of bits and concatenate those bits to form a number that corresponds to our procedure. So all possible procedures in our language are a subset of the natural numbers in this representation. Now make a list of all the procedures that create computable reals in [0,1) -- it doesn't matter if some numbers occur multiple times. We can now create a new computable real by a procedure that, given a position n, asks the nth procedure for its nth digit, adds 1 to that modulo 10, and returns that for its nth digit. This is different from every element in our supposed list of computable reals contradicting the assumption that all reals are computable.

But what we actually proved is that there is no computable way to put the computable reals into a list, because if we can compute that list then we can, using our diagonal argument, create a new procedure that is a computable real that is not in the list.

And it seems that a lot of mathematics is like this. We assume that some non-computable thing exists, then we find that this implies that all sorts of other non-computable things must also exist.

 So, to be perfectly clear:

Non-computable things don't exist.

You don't agree: show me one.

However it is a lot easier to think about the real numbers rather than the computable real numbers, and the sets of natural numbers rather than the computable sets of natural numbers. So my 2nd point is:

It's ok, in a programming language, to define types which ostensibly include non-computable values, even though the type's constructors only cover computable values.