"Peter Webb" <webbfamily@DIESPAMDIEoptusnet.com.au> wrote in message news:4c1eafa3$0$1025$afc38c87@news.optusnet.com.au... > > "Mike Terry" <news.dead.person.stones@darjeeling.plus.com> wrote in message > news:B8WdnX3itoZ7zYPRnZ2dnUVZ7qednZ2d@brightview.co.uk... > > "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. > > No. Computing the the anti-diagonall to n places only requires the first n > items on the list to n digits of accuracy. > > And it clearly is computable. I can compute it. I take the nth digit of the > nth term, and ... blah blah.
Yes, of course the first n digits of any number are computable, for a fixed n.
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 not 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] OR - 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!
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 to 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 notation :)
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 every single real number r, computable or not.
So having "a finite algorithm to calculate a number to n decimal places for 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 sqrt(2).
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 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. > > I don't have to look it up. I know it.
Well, clearly not given what you've said above... :-)
