Why can no one in sci.math understand my simple point?
in [Math]
|
Prev: power of a matrix limit A^n
Next: best way of testing Dirac's new radioactivities additive creation Chapt 14 #163; ATOM TOTALITY
From: Mike Terry on 21 Jun 2010 19:18 "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote in message news:4c1eb265$0$11181$afc38c87(a)news.optusnet.com.au... > > "Mike Terry" <news.dead.person.stones(a)darjeeling.plus.com> wrote in message > news:a_mdnZe4xaoOxIPRnZ2dnUVZ8umdnZ2d(a)brightview.co.uk... > > "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote in message > > news:4c1d86f0$0$18229$afc38c87(a)news.optusnet.com.au... > >> > >> "Mike Terry" <news.dead.person.stones(a)darjeeling.plus.com> wrote in > > message > >> news:NNqdnTtg2LuExoDRnZ2dnUVZ8lKdnZ2d(a)brightview.co.uk... > >> > "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote in message > >> > news:4c1c6be3$0$17177$afc38c87(a)news.optusnet.com.au... > >> >> > >> >> "Tim Little" <tim(a)little-possums.net> wrote in message > >> >> news:slrni1om15.jrj.tim(a)soprano.little-possums.net... > >> >> > On 2010-06-19, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> > > wrote: > >> >> >> So Cantor's proof when applied to computable Reals proves exactly > >> >> >> what in your opinion? > >> >> > > >> >> > That there is a real not on the list. > >> >> > > >> >> > > >> >> >> I might remind you that as the form of proof is identical to that > >> >> >> used by Cantor for all Reals, whatever you believe that Cantor's > >> >> >> proof applied to computable Reals proves, his proof applied to all > >> >> >> Reals must prove the same thing. > >> >> > > >> >> > It does prove exactly the same thing: in both cases, all such lists > >> >> > omit at least one real. > >> >> > > >> >> > > >> >> >> Its the same proof, after all, except limitting the set to just > >> >> >> computable Reals. > >> >> > > >> >> > No, there is a slight difference: the antidiagonal is a real number. > >> >> > It does not necessarily produce a computable real number. > >> >> > > >> >> > >> >> Of course it is computable. Cantor provides a simple construction for > > the > >> >> number. > >> > > >> > No, you're misunderstanding the meaning of computable. > >> > > >> > Hopefully you will be OK with the following definition: > >> > > >> > A real number r is computable if there is a TM (Turing machine) > >> > T which given n as input, will produce as output > >> > the n'th digit of r. > >> > > >> > So let us suppose there is a list L (not a "computable list", just a > >> > "list") > >> > of computable numbers in [0,1], covering all computerable numbers. > >> > > >> > [You have your own strange definition of "list", but I am using the > >> > term > >> > with it's standard mathematical meaning: L is just a function mapping > >> > N > >> > (natural numbers) to CR (computable reals). Perhaps we should also > > insist > >> > that lists are injections (no duplicates) - that's fine. YOU seem to > > want > >> > to define "list" to only include "computable" functions from N to CR, > > but > >> > that is NOT what everybody else (including Cantor) means by "list"!] > >> > > >> > L : N --> CR > >> > > >> > so we have the sequence (=list) of computable reals: > >> > > >> > ( L(0), > >> > L(1), > >> > L(2), > >> > ....) > >> > > >> > Each computable real has it's digital representation, so this list can > > be > >> > written: (using d(m,n) for n'th digit of L(m) > >> > > >> > L(0) digits : d(0,0), d(0,1), d(0,2), ... > >> > L(1) digits : d(1,0), d(1,1), d(1,2), ... > >> > L(2) digits : d(2,0), d(2,1), d(2,2), ... > >> > ... > >> > > >> > Now, given m and n, is there necessarily a TM that can take m and n as > >> > inputs, and ouput d(m,n)? > >> > > >> > Well, each L(m) individually is computable: there is a corresponding > >> > TM, > >> > TM_m such that given n as input it will compute d(m,n). We could say: > >> > > >> > TM_m (n) = d(m,n) > >> > > >> > But all the TMs can be different and completely unrelated to each > >> > other. > >> > > >> > Can we say there will always be a *single* TM TM_ALL_m, which > >> > "subsumes" > >> > all > >> > the TM_n, i.e. if given m and n as input, will compute d(m,n)? I.e. > >> > > >> > for all m,n: TM_ALL_m (m,n) = d(m,n) ????? > >> > > >> > Unfortunately for your argument, the answer is NO. > >> > > >> > But that is exactly what you would need to argue that the anti-diagonal > > is > >> > computable: You need a TM that could calculate d(m,m), but this needs > > the > >> > TM TM_ALL_m, and we do not have that! > >> > > >> > I know what you want to say at this point! :) You want to say that I > > have > >> > "explicitly given you" d(m,n), and I can only do this if d(m,n) is > >> > computable. (Right?) And you want to tell me that Cantor's diagonal > >> > proof > >> > is the same? > >> > > >> > Well, this is a misreading of Cantor's proof! Look closely: > >> > > >> > Paraphrasing of Cantor's proof: > >> > > >> > Given a function L: N --> [0,1], there > >> > exists r in [0,1], such that > >> > for all n, r != L(n) [i.e. r is not in the list] > >> > > >> > Proof: > >> > 1) Suppose L: N-->R > >> > 2) Define LD: (NxN)-->{0,1,2,3,4,5,6,7,8,9} > >> > such that LD(m,n) = n'th digit of L(m) > >> > 3) Define RD: N-->R > >> > such that RD(m) = [...antidiagonal digit m...] > >> > 4) Then RD determines a real r in [0,1] > >> > 5) Show for all n, r != L(n) from defn. of r above. > >> > > >> > Where in this proof does Cantor require LD(m,n) to be computable? > > (Answer > >> > = > >> > nowhere.) > >> > > >> > I think maybe you are thinking it must be computable, due to your > >> > misleading > >> > use of the phrase "explicitly given", but actually all Cantor does is > >> > argue > >> > that IF a (any) function L (not necessarily computable) EXISTS mapping > >> > N > >> > to > >> > [0,1], the mere existence of L implies the existence of a corresponding > >> > real > >> > r not in the list L. There is nothing requiring real computer programs > > to > >> > actually compute anything here! It's just a mathematical proof of > >> > existence > >> > of something. > >> > > >> > >> What you are writing above is *not* Cantor's diagonal proof as it appears > > on > >> a million websites. > > > > Well, I claim that it is at least OBVIOUSLY EQUIVALENT to what Cantor is > > saying. It's true I didn't go to a web site and cut and paste any > > "official" text from his original document, but in essence my > > understanding > > is: > > > > 1. Cantor shows that any map from N to R cannot be "onto" R. > > 2. That my proof above sketches this out: > > - Cantor equates real numbers with their digit sequences > > (This is why I go from L to LD) > > - Cantor shows the existence of a new digit sequence, via > > the antidiagonal argument > > (That is what I do in step (3). RD is my new digit sequence.) > > - Cantor proves that RD is a new digit sequence > > - and that consequenctly the corresponding real number > > is not in the original map L. > > > > So I think my proof follows Cantor's pretty closely, although it is my own > > notation. Given the amount of effort I put into trying to help you, I'm > > disappointed you can't get over some minor notationaly differences to > > follow > > what I'm saying. > > The whole point of what I am doing is to use his original proof in its > original form. > > Introducing new notation is a crank's way of arguing. > > Why not look at my proof, which follows Cantor's proof, instead of changing > te notation to produce a proof which you claim is equivalent and arguing > about that different proof, which you claim differs only in notation? > OK, I said I'd do that below, so we'll see. I'd not actually seen any statement from you of the full Cantor proof that you keep referring to. Still, it's on "millions of websites", so I'm expecting when it finally comes it will be super precise and thorough, and so really easy for me to pin down the flaw you're asking for. Especially as my proof above was already pretty detailed, but that wasn't good enough for you... :) > > > > You've also given no indication of in what way you think > > my proof differs from Cantors! (Well, that would be OK if my proof was > > "nothing like" Cantor's but that's clearly not the case as I've just > > explained, so I'm left mystified by your claim...) > > > >> > >> The whole point of my post was to use Cantor's proof exactly, which alows > > me > >> to demonstrate that Cantor's proof does *not* in of itself prove the > >> uncounatbility of the Reals. > >> > >> Perhaps if you were to tell me where you think the error in my very > >> simple > >> proof is, then we would be making progress. > > > > Sure I'll do this. To avoid a further "that's not Cantor's proof" claim > > from you, please quote exactly what proof of Cantor's you want me to > > comment > > on. > > > > There can be no list of all Reals. > > Imagine such a list of purported Reals exists. Compute the anti-diagonal > number as follows ... blah blah. This Real is not on the list. Um... Seriously? That's your version of Cantor's proof that appears on "millions of websites" and is your final and most detailed statement of the proof that you're capable of? You do realise that my own proof said the same but in more precise terms than you, e.g. not missing out important key steps? (I don't think you do...) Still, I said I'd do it so I'll try and work with you. Also you've missed out a key bit, presumably because it's not important to you, but it's the bit you're overlooking! OK, here's Cantor's official proof (according to you, but I've added a key step which you missed out, and funnily enough it's the bit you've overlooked.): Thm: There can be no list of all Reals. Proof: 1. Imagine such a list of purported Reals exists. 2. Compute the anti-diagonal number as follows ... blah blah. [I'm quite happy with the blah blah bit :) ] [But I'm NOT happy with your use of the verb "Compute" since it could suggest the formal maths meaning of "computable function", whereas in fact we just mean "DEFINE the antidiagonal..." Still, let's carry on with your word, and just keep this in mind] 3a. The antiadiagonal corresponds to a REAL NUMBER Reason: ANY DIGIT SEQUENCE CORRESPONDS TO A REAL NUMBER. 3b. This Real is not on the list. Now I do a "change all" from Real to Computable Real to get your alleged proof: Thm: There can be no list of all computable Reals. Proof: 1. Imagine such a list of purported computable Reals exists. 2. Compute the anti-diagonal number as follows ... blah blah. [I'm quite happy with the blah blah bit:)] [But I'm NOT happy with your use of the verb "Compute" since it could suggest the formal maths meaning of "computable function", whereas in fact we just mean "DEFINE the antidiagonal..." Still, let's carry on with your word, and just keep this in mind] 3a. The antiadiagonal corresponds to a COMPUTABLE REAL NUMBER Reason: ANY DIGIT SEQUENCE CORRESPONDS TO A COMPUTABLE REAL NUMBER. 3b. This computable Real is not on the list. The wrong step is (3a). (The one missed out from your version of Cantor's proof.) It is not true that any digit sequence corresponds to a computable real number. The antidiagonal is a Real number, since ANY digit sequence determines a Real number, but if you want to claim it's computable, actual proof is required for this. Note also, if we did a "change all" instead from Real to "rational Real" the proof would break down in exactly the same place. (As others on this thread have already pointed out.) Maybe you think you can patch up (3a) and prove the conclusion so the proof can carry on from there? (In fact, it's obvious you think this from your posts.) However, already you've failed in your original claim which was that simply by doing the "change all" Cantor's proof must "automatically" remain valid, while you can see from above that it does not. Feel free to try and prove (3a) yourself and complete the proof, but remember the definition of "computable real" used in (3a) does not allow algorithms with infinite input data. Anyway, I've done what I said I would do here which is point out where the "change all" argument goes wrong... Regards, Mike.
From: Mike Terry on 21 Jun 2010 19:29 "WM" <mueckenh(a)rz.fh-augsburg.de> wrote in message news:50a455fe-4b9b-46c9-8f41-99077ece6339(a)z8g2000yqz.googlegroups.com... > On 21 Jun., 21:35, "Mike Terry" > <news.dead.person.sto...(a)darjeeling.plus.com> wrote: > > > > It is an irrational number. Add it at first position to the former > > > list L0, obtain L1. Now construct the diagonal of L1 (according to a > > > fixed scheme). It is certainly an irrational number. Add ist to the > > > list L1 at first position, obtain list L2. Now construct the > > > diagonal, ... and continue. I this way you get a countable set > > > consisting of all rationals and of all diagonal numbers of these > > > lists. > > > > No... What you get is an infinite sequence of lists (L0, L1, L2, ...) > > > > Each Ln in the sequence contains all rationals, and Ln contains the > > antidiagonals for L0,...L(n-1). Ln doesn't contain its own antidiagonal, > > and doesn't contain any antidiagonals for Lm with m>n. > > Correct. Therefore the set of antidiagonals appears to be uncountable > = unlistable. But it is countable. I don't see why you say it appears to be uncountable. (See below) > > > > > This set is certainly not countable, because you can prove that > > > there is always a diagonal number not in the list. > > > > What set? > > The set of antidiagonals that can be constructed (by a given > substitution rule) from an infinite sequence of lists. Ah, OK. So we have (L0, L1, L2, ...), and corresponding to each Ln we have an antidiagonal An. So we have a sequence (A0, A1, A2, ...). But (A0, A1, A2, ...) is obviously countable. Above you say it's "certainly not countable", but it is. [Snipped rest of post] Regards, Mike.
From: Virgil on 21 Jun 2010 19:32 In article <e0b8cbfa-70a9-4be3-a08f-117e0af7fc9b(a)q12g2000yqj.googlegroups.com>, WM <mueckenh(a)rz.fh-augsburg.de> wrote: > On 21 Jun., 22:17, Virgil <Vir...(a)home.esc> wrote: > > > > > > > But the set of all diagonals constructed according to the scheme given > > > above is countable but cannot be listed. > > > > Whatever do yu mean by "the set of all diagonals"? > > If you mean one "diagonal" for each possible list, that set of diagonals > > is not countable. > > If you mean the set of all "diagonals" for a single list, that is not > > countable either, since each of uncountably many permutations of the > > list produces a different "diagonal". > > Take a list of all rationals. Construct, accordingto a given > substitution rule the antidiagonal. Add it at first position to the > list. Construct, according to the given rule the antidiagonal, add > it ... and so on. You are saying given a list, create its anti-diagonal and prepend it to that list. Repeat with the new list ad infinitum. > > The number of antidiagonal is countable. Nevertheless it cannot be > listed. I see no problem in listing the set of such anti-diagonals. They can even be listed in the order in which each anti-diagonal is to be created. Note that the list of anti-diagonals so far created is finite so long as the number of iterations is finite, and only becomes infinite when the process achieves infinitely many iterations, and thus it is countable. Which such anti-diagonals does WM claim remain unlisted? > > > > > > > > > > Cantor has shown that the set of all reals cannot biject with the > > > > naturals, ergo, the set of all reals is NOT of countable cardinality. > > > > > The same proof shows that some countable sets are of not countable > > > cardinality. > > > > I have yet to see such a "proof" > > That is impossible, because you will not recognize it. Since WM's such proofs always take place in an environment incompatible with standard set theories such as FOL+ZFC, they are not binding on such theories. > > But for the lurkers: > The complete infinite binary tree contains, by definition, all real > numbers between 0 and 1 as infinite paths, i. e., as infinite > sequences { 0, 1 }^N of bits. > > > 0, > / \ > 0 1 > / \ / \ > 0 1 0 1 > / > 0 ... > > > The set { K_k | k in N } of nodes K_k of the tree is countable. > > > K_0 > / \ > K_1 K_2 > / \ / \ > K_3 K_4 K_5 K_6 > / > K_7 ... > > The tree is constructed by extending the configurations B_j as > explained below: > > _________________ > B_0 = > > K_0 > _________________ > B_1 = > > K_0 > / > K_1 > _________________ > B_2 = > > K_0 > / \ > K_1 K_2 > _________________ > B_3 = > > K_0 > / \ > K_1 K_2 > / > K_3 > _________________ > > B_4 = > > K_0 > / \ > K_1 K_2 > / \ > K_3 K_4 > _________________ > ... > _________________ > B_j = > > K_0 > / \ > K_1 K_2 > / \ > K_3 K_4 ... > ... > ... K_j > _________________ > ... > _________________ > > The complete infinite binary tree (including all those infinite paths > which consist of nodes and edges only) is constructed by a countable > number of steps. In no step more than one infinite paths is extended. > Hence there are not more than countably many infinite paths. I have no idea what sort of definition of "countability" of infinite sets that WM is using, but it is necessarily nonstandard, and thus is irrelevant here if it does not apply precisely to those sets which may be put into bijection with the set of naturals and no others. > Nevertheless these paths cannot be enumerated. Thus, by any STANDARD definition of "countable", the set of them is NOT a countable set. By definition, a set which cannot be ennumerated (or listed) is NOT countable by the definition which defines countability of infinite sets as having a bijection with the set of naturals (also called a listing, or an ennumeration).
From: Mike Terry on 21 Jun 2010 19:49 "Mike Terry" <news.dead.person.stones(a)darjeeling.plus.com> wrote in message news:MemdnYQCNsKlV4LRnZ2dnUVZ8gGdnZ2d(a)brightview.co.uk... > "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote in message > news:4c1eafa3$0$1025$afc38c87(a)news.optusnet.com.au... > > > > "Mike Terry" <news.dead.person.stones(a)darjeeling.plus.com> wrote in > message > > news:B8WdnX3itoZ7zYPRnZ2dnUVZ7qednZ2d(a)brightview.co.uk... > > > "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote in message > > > news:4c1e2b53$0$316$afc38c87(a)news.optusnet.com.au... > > >> > > >> "Tim Little" <tim(a)little-possums.net> wrote in message > > >> news:slrni1r0ra.jrj.tim(a)soprano.little-possums.net... > > >> > On 2010-06-20, Peter Webb <webbfamily(a)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! 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" could mean: "..a finite algorithm to calculate (the number to n decimal places for all n)" [i.e. the equivalent of my TM_ALL above] or "..(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 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 > :) > > CalcDigit_4(n) > { > 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 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... :-) 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...) > > Mike.
From: Mike Terry on 21 Jun 2010 20:29
"Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote in message news:4c1f0213$0$17174$afc38c87(a)news.optusnet.com.au... > > "Tim Little" <tim(a)little-possums.net> wrote in message > news:slrni1tkli.jrj.tim(a)soprano.little-possums.net... > > On 2010-06-21, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > >> "Tim Little" <tim(a)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. |