"Peter Webb" <webbfamily@DIESPAMDIEoptusnet.com.au> wrote in message news:4c1f0213$0$17174$afc38c87@news.optusnet.com.au... > > "Tim Little" <tim@little-possums.net> wrote in message > news:slrni1tkli.jrj.tim@soprano.little-possums.net... > > On 2010-06-21, Peter Webb <webbfamily@DIESPAMDIEoptusnet.com.au> wrote: > >> "Tim Little" <tim@little-possums.net> wrote in message > >> I do understand that. But I don't actually ask for a "finite algorithm" > >> in > >> my proof, I only require that I am provided a purported list of all > >> comptuable Reals. > > > > Later in the proof, you claim that the antidiagonal real is > > computable. In other words, that there exists a finite algorithm for > > computing it. > > > > > >> Yes, in practice, this means that each item is specified by a finite > >> algorithm, but so what? I ask for a purported list of all computable > >> Reals > >> and show there is at least one missing. > > > > At least one *what* missing? A real? Fine - Cantor's proof shows > > that there is a missing real. > > And if the nth digit of the nth term is computable, then so is the nth term > of the anti-diagonal, as there is an explicit construction of the nth digit > of the anti-diagonal based upon the nth digit of the nth term.
This is an easy mistake to make, and I imagine one of the standard "common mistakes students fall into". I've explained it elsewhere but briefly:
1. you know that for each n, the n'th real in the list is computable 2. i.e. for each n there is a (likely different) TM_n which computes the digit function for the n'th real 3. the problem is you want a new "subsuming" TM, TM_ALL which can take as input n, and return the n'th digit of the n'th real. 4. So, naively you want to "code" TM_ALL to say: get me TM_n(n). 5. But this isn't legal, because: - TM_n is a completely different TM - And you can't "embed" each of the (infinitely many) TM_n into the single TM_ALL because that wouldn't be a finite algorithm any more. - TM_n has a "Godel number" G_n that describes it, and IF you could compute that, you could then emulate TM_n to determine TM_n(n). The problem here is THE MAPPING n--->G_n ISN'T NECCESSARILY A COMPUTABLE FUNCTION!
Now for SOME lists it obviously CAN be the case that the function (m,n) ---> the n'th digit of the m'th real IS computable. It's easy to deliberately construct such lists. In this case, TM_ALL can obviously use this function to get TM_n(n) so the antidiagonal in this case IS a computable number. But this doesn't work in general.
Regards, Mike. ps. don't worry, this is the last time I'll mention this point unless you have specific questions about it.
