> "Tim Little" <tim@little-possums.net> wrote in message > news:slrni1m5c1.jrj.tim@soprano.little-possums.net... >> 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[0] is very simple: the n'th element of the list is the real produced by the real-computing Turing machine[1] 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 [0] 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[2] directly nor stored on the tape[3].
More formal definitions of "computable number" would make the necessary step in proving your argument even harder.
-o
[0] A real is computable if and only if there is a Turing machine that computes it[1].
[1] 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.
[2] 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.
[3] 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.
