Date: Jun 21, 2010 7:49 PM
Author: Mike Terry
Subject: Re: Why can no one in sci.math understand my simple point?
"Mike Terry" <email@example.com> wrote in message
> "Peter Webb" <webbfamily@DIESPAMDIEoptusnet.com.au> wrote in message
> > "Mike Terry" <firstname.lastname@example.org> wrote in
> > news:B8WdnX3itoZ7zYPRnZ2dnUVZ7qednZ2d@brightview.co.uk...
> > > "Peter Webb" <webbfamily@DIESPAMDIEoptusnet.com.au> wrote in message
> > > news:email@example.com...
> > >>
> > >> "Tim Little" <firstname.lastname@example.org> wrote in message
> > >> news:email@example.com...
> > >> > On 2010-06-20, Peter Webb <webbfamily@DIESPAMDIEoptusnet.com.au>
> > >> >> Explain to me how my requirements for the input list of all
> > >> >> computable Reals is different to Cantor's requirements for the
> > >> >> list of all Reals, other than the requirement that every item on
> > >> >> list is computable?
> > >> >
> > >> > It is not. Your error comes later.
> > >> >
> > >> > Cantor's proof includes a construction taking a list L and defining
> > >> > antidiagonal real antidiag(L) from it. Your error is supposing
> > >> > 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
> > >> > finite input n and infinite input L, and producing the n'th
> > >> > antidiagonal digit. This is a stretch since algorithms are
> > >> > not supposed to have infinite inputs.
> > >>
> > >> The calculation of the nth digit only requires the first n digits to
> > >> decimal places, and hence it is clearly a finite algorithm.
> > >>
> > >> Its simply ludicrous to suggest that the antidiagonal is not
> > >> 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.
> > No. Computing the the anti-diagonall to n places only requires the first
> > items on the list to n digits of accuracy.
> > And it clearly is computable. I can compute it. I take the nth digit of
> > nth term, and ... blah blah.
> Yes, of course the first n digits of any number are computable, for a
> You are just saying that GIVEN n, there is a TM: TM_n that computes the
> first n digits of the antidiagonal with only finite input. Well, that's
> too amazing if you think about it :-)
> What you need to be able to claim is that there is single TM_ALL using
> finite input data, such that TM_ALL will calculate ALL the antidiagonal
> digits (i.e. infinitely many of them). So your approach above fails,
> because either you have to :
> - fix n [in which case I agree you are only using a finite
> amount of input data from the original list, but your
> TM_n doesn't do the required job for ALL m (i.e. it
> can't handle m>n]
> - not fix n [in which case you have an algorithm of sorts that
> can generate ALL antidiagonal digits, but it requires
> as input the FULL Cantor input list, which is
> an INFINITE amount of data]
> > How is this number any less computable than the square root of 2?
> > In both cases there is a finite algorithm to calculate the number to n
> > decimal places for all n.
> No that's exactly not what computable means!
Hmmm, it occurs to me on re-reading that maybe I mis-parsed your sentence.
If so I appologise for teaching you to suck eggs below! (But I'm not sure
whether I misunderstood.)
"..a finite algorithm to calculate the number to n decimal places for all n"
"..a finite algorithm to calculate
(the number to n decimal places for all n)"
[i.e. the equivalent of my TM_ALL above]
"..(a finite algorithm to calculate the number to n decimal places)
for all n"
[i.e. the equivalent of my TM_n above existing for each n]
I originally read your meaning as the latter.
If you did mean the former, then my last post still correctly points out
that it needs infinite input data, so that sort of goes against other things
you're saying about only needing finite data to get n decimal places...
> OBVIOUSLY every real (computable or not) can be "computed to n decimal
> places for all n". That's because every FINITE set can be computed simply
> by an algorith that internally encodes every element of the set.
> Let's be clear about this, because I doubt you said what you really meant
> say, so lets get this issue out of the way. Take Pi = 3.14159...
> Obviously 3 is computable.
> Obviously 3.1 is computable.
> Obviously 3.14 is computable.
> Obviously 3.141 is computable.
> Well, the last number is getting pretty complicated (4 digits) so let's
> check that one. A function like this will do: (excuse the "C" like
> if (n == 1) Output 3 // digit 1
> else if (n == 2) Output 1 // digit 2
> else if (n == 3) Output 4 // digit 3
> else if (n == 4) Output 1 // digit 4
> else Output 0 // ..the rest :)
> There we go - a finite algorithm computing 3.141
> Similarly 5,6,7 digits, and so on.
> If we FIX n, and just look at the first n digits of Pi, OF COURSE THAT
> NUMBER IS COMPUTABLE! It's just a longer version of CalcDigit_4!
> Now reread what you stated:
> -- In both cases there is a finite algorithm to calculate the number to n
> -- decimal places for all n.
> So what you wrote is trivial, since it applies without any thought to
> single real number r, computable or not.
> So having "a finite algorithm to calculate a number to n decimal places
> all n" is useless as a definition of computable number.
> OK - what SHOULD the definition of computable number say?
> Clearly the definition should (and does) require that there is ONE
> algorithm, which we might call CalcDigit_All in line with my earlier
> examples, which can calculate the n'th digit for all n.
> Maybe you think this is saying the same thing as you said, but it's not.
> The order of qualifiers is different. Specifically, your definition was:
> Defn: r is computable if...
> for all n
> exists finite algorithm CalcDigit_n (m)
> CalcDigit_n(m) = m'th digit of r if m<=n
> The proper definition is:
> Defn: r is computable if...
> exists finite algorithm CalcDigit_All (m)
> CalcDigit_n(m) = m'th digit of r for ALL m
> Specifically, for sqrt(2), there is clearly a suitable CalcDigit_All
> algorithm that will accept m as input and produce the m'th digit of
> There is not necessarily a suitable CalcDigit_All for your antidiagonal
> number, unless you can prove such exists (using only a finite amount of
> input data)
> > > As such, this is not an
> > > algorithm that can be implemented on a Turing machine. I.e. the
> > > is not the sort of algorithm that counts as "computable". Maybe you
> > > dispute this, but it's been explained to you several times (including
> > > 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
> > > this.
> > I don't have to look it up. I know it.
> Well, clearly not given what you've said above... :-)
Although, now I'm thinking maybe that wasn't your mistake and it was just in
not recognising that although for any n you can get to the n'th decimal
place with finite input data, if you have one algorithm which is to work for
ALL n that still requires infinite input data. (Because the amount of data
you need as a function of n grows without bound as n grows, and the
algorithm and input data has to be fixed up front before n is given...)