"Peter Webb" <webbfamily@DIESPAMDIEoptusnet.com.au> wrote in message news:4c1e2b53$0$316$afc38c87@news.optusnet.com.au... > > "Tim Little" <tim@little-possums.net> wrote in message > news:slrni1r0ra.jrj.tim@soprano.little-possums.net... > > On 2010-06-20, Peter Webb <webbfamily@DIESPAMDIEoptusnet.com.au> wrote: > >> Explain to me how my requirements for the input list of all > >> computable Reals is different to Cantor's requirements for the input > >> list of all Reals, other than the requirement that every item on the > >> list is computable? > > > > It is not. Your error comes later. > > > > Cantor's proof includes a construction taking a list L and defining an > > antidiagonal real antidiag(L) from it. Your error is supposing that > > this construction is a finite algorithm fitting the definition of > > "computable real". It is not. By stretching the definition of > > "algorithm" somewhat, it can be supposed to be an algorithm accepting > > finite input n and infinite input L, and producing the n'th > > antidiagonal digit. This is a stretch since algorithms are normally > > not supposed to have infinite inputs. > > The calculation of the nth digit only requires the first n digits to n > decimal places, and hence it is clearly a finite algorithm. > > Its simply ludicrous to suggest that the antidiagonal is not computable > given that a very simple algorithm will explicitly churn it out.
Not so - the "very simple algorithm" you are suggesting requires "the input list" in its raw (infinite) form as input. As such, this is not an algorithm that can be implemented on a Turing machine. I.e. the algorithm is not the sort of algorithm that counts as "computable". Maybe you will dispute this, but it's been explained to you several times (including one of my posts), and you can always go away and look up the definition of computable function / Turing Machine etc., but it seems you've not done this.
> > > > > However, there is no way that you can then prove the existence of a > > finite algorithm accepting only the *finite* input n and producing the > > n'th antidiagonal digit. > > > > Of course I can prove the existence of a finite algorithm. I can produce it. > > To produce the nth decimal of the anti-diagonal, look at the first n items > on the purported list of all computable Reals.
There! Was I right, or was I right? :-)
There is an infinite amount of data on this "purported list", and you are not allowed to base a computable function on an infinite amount of input data. To do so shows you simply do not understand what computable means.
Now IF you could codify all this data somehow into a finite program, so you had a computable function D(m,n) which produced the n'th digit of the m'th number in the list, you would be OK. But you DON'T have such a computable function D.
What you DO have, is for each m, a computable function D_m (n) which produces the n'th digit of the m'th number in the list. But how can you use these individual D_m in the definition of the antidiagonal? (You can't...)
Do you not see this distinction?
Knowing the existence of all the individual D_m is equivalent to knowing that the list (sequence of numbers) consists of computable reals.
Knowing the existence of D (which is a single computable function) is equivalent to having a *computable* list of computable reals.
Cantor's proofs do not require computable lists, they work with just any old lists...
> Then substitute "1" for "2" > blah blah. How is that not a finite algorithm?
As explained it is not a finite algorithm because it uses as input an infinite source of data.
By your reckoning every single real number is computable, because we can have a TM that just accepts as input an infinite tape with the entire digit sequence encoded on it, and outputs that digit sequence.
Surely you must be aware that this is NOT what computability means?
