> "Tim Little" <firstname.lastname@example.org> wrote in message > news:email@example.com... >> On 2010-06-18, Peter Webb <webbfamily@DIESPAMDIEoptusnet.com.au> wrote: >>> If you can construct a list of all computable numbers (which you >>> can't), then Cantor's diagonal proof will construct a number not on >>> the list. And that number is definitely computable, because there is >>> a simple algorithm for producing it. Take the nth digit of the nth >>> item on the list >> >> That requires having the list be computable or provided as input, >> neither of which is assumed or proven. >> > > Cantor's proof that there can be no list of all Reals also requires the > list to be provided first. > > The form of the proof is identical - you give me a purported list of > all Reals with some property, and I prove the existence of at least one > Real which has that property which is not on the list, thus proving the > list did not contain all numbers with that property. Cantor used the > property "is Real", I used the property "is computable". > >> Rest snipped as it is based on your false premise. >> >> >> - Tim > > If you believe that you can list all computable numbers, you are > welcome to try and do so. Its a pointless exercise, as I can always > form a computable Real not on the list, but try anyway.
Pick a Gödel numbering scheme for the Turing machines. Then, given this scheme, the list of computable reals is very simple: the n'th element of the list is the real produced by the real-computing Turing machine with the n'th lowest Gödel number (so the 0th element of the list is the real produced by the lowest-numbered machine, the 1st element of the list is the real produced by the next-lowest-numbered machine, and so on). Determining whether a Turing machine computes a real is not a computable problem, but that does not prevent such a list from existing.
The antidiagonal of this list differs from every computable number, and there is a simple and effective algorithm for computing it *given the list*, but to show a contradiction you'd still have to prove that this number is computable in exactly sense  below. This is (likely) impossible, as this list itself is uncomputable, and the list can neither be embedded in a Turing machine's transition function directly nor stored on the tape.
More formal definitions of "computable number" would make the necessary step in proving your argument even harder.
 A real is computable if and only if there is a Turing machine that computes it.
 A Turing machine computes a real r if and only if, starting with an encoding of some natural number m on its tape, it halts with an encoding of the m'th digit of r on the tape.
 Keeping in mind that a Turing machine has finitely many states Q and finitely many symbols L, the image of the transition function contains at most |Q| * |L| elements -- far too few to encode an infinite list of reals.
 At every step, a Turing machine has only finitely-many non-blank cells on the tape -- far too few to encode an infinite list of reals.