Why can no one in sci.math understand my simple point?
in [Logic]
|
From: Tim Little on 19 Jun 2010 21:15 On 2010-06-19, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > Of course it is computable. Cantor provides a simple construction > for the number. Only if the list itself is a recursively enumerable function. Cantor's proof makes no such assumption. - Tim
From: Tim Little on 19 Jun 2010 21:24 On 2010-06-19, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > You haven't specified the list. I have to guess at some of the > entries in the list, as I don't actually know and cannot determine > which TMs halt. I have explicitly specified the list (which is actually a lot more than Cantor's proof requires). It is not my problem whether you are incapable of determining which TM's halt. It is a well-defined mathematical function with all the properties assumed in Cantor's proof. Likewise the following is a valid list of binary digits: f(n) = 1 if there are infinitely many prime pairs of the form (p, p+n), f(n) = 0 otherwise. It doesn't matter whether or not you personally know the value of f(2), or even whether there exists an algorithm to find out: it is still a well-defined mathematical object. Are you now starting to see the difference between the term "list" (as used in Cantor's proof) and "recursively enumerable list" (as you are using in yours)? - Tim
From: Tim Little on 19 Jun 2010 21:26 On 2010-06-19, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > Take the list, determine the nth digit of the nth item, blah > blah. Remember, just as in Cantor's proof, you have to provide the > list first. You don't get to "take the list" to compute the diagonal, as the list is an infinite object in contradiction to the requirement of "finite algorithm" in the definition of "computable real". - Tim
From: Peter Webb on 19 Jun 2010 21:59 "Virgil" <Virgil(a)home.esc> wrote in message news:Virgil-20BC96.00395219062010(a)bignews.usenetmonster.com... > In article <4c1c6011$0$17176$afc38c87(a)news.optusnet.com.au>, > "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > >> "Tim Little" <tim(a)little-possums.net> wrote in message >> news:slrni1okg1.jrj.tim(a)soprano.little-possums.net... >> > On 2010-06-19, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> >> "Tim Little" <tim(a)little-possums.net> wrote in message >> >>> Your "simple fact" is simply wrong. Look up the definition of >> >>> "computable real" and get back to us. >> >> >> >> Why? >> > >> > Because you clearly don't know how a computable real is defined. >> > >> > >> >> If you believe there is an error in what I have said, identify it. >> > >> > I have, many times now. >> > >> > >> >> Or give me at least a hint. As a start, my argument rests on two >> >> observations: >> >> >> >> 1. Cantor's diagonal construction, when applied to a purported list >> >> of all computable Reals, will produce a computable Real not on the >> >> list. >> > >> > The latter part is incorrect. It produces a real, but not a >> > computable real. If you believe otherwise, provide a proof that the >> > antidiagonal real is computable. >> > >> >> Well, there are lots of definitions of a computable Real, I will use >> Wikipedia's most intuitive definition: "computable reals, are the real >> numbers that can be computed to within any desired precision by a finite, >> terminating algorithm." >> >> 1. Given a list of computable Reals, we can identify the nth computable >> Real >> on the list by simply counting down to the nth entry. >> >> 2. Given the nth computable Real on the list, we can count off and >> identify >> the nth digit of this Real. >> >> 3. With the nth digit of the Real, we can use Cantor's construction to >> identify the nth digit of the anti-diagonal. >> >> 4. As we can specify every digit in the anti-diagonal explicitly and to >> any >> desired degre of accuracy, it is therefore computable. > > But that requires that the list be given in advance, so that > "anti-diagonal" is not really a single number so much as a function from > lists to numbers with value depending on the particular list being > chosen. So I am not quite confident that that situation qualifies as a > computable number, which should not, in my mind, be dependent on a > particular list of numbers being given. > Cantor's proof that Reals cannot be listed requires an explicit list, such that the nth digit of the nth term can be determined. My proof follows exactly the same form. >> >> 5. But the anti-diagonal number does not appear on the list. >> >> 6. Therefore, the list could not have included all computable Reals. >> >> Exactly the same as Cantor's proof that the Reals cannot be listed. The >> only >> difference is that I have to prove that the anti-diagonal is also >> computable, but because Cantor's proof explicitly constructs the >> anti-diagonal it is clearly computable (as long as every item in the list >> is >> computable, which is the starting assumption which we prove to be >> incorrect, >> just like in Cantor's original proof). > > Actually not. The starting assumption had better be that list contains > EVERY computable number if you are trying to prove something INcorrect. > That is the premise in Cantor's original proof - that it contains every Real - and this is the premise in my slight reworking of it - that it contains every computable Real. > It is perfectly possible to have lists of computable numbers which are > not complete in which case the anti-diagonal construction proves nothing. Indeed. And its perfectly possible to have lists of Reals which are not complete in which Cantor's construction proves nothing. Cantor's proof starts with a purported list of all Reals; I start with a purported list of all computable Reals. The proof is *exactly the same*; that's the whole point, if it was different it would not prove that just because a set cannot be explicitly listed does not imply it is uncountable. What Cantor proved (in more modern parlance) is that there is no recursively enumerable function from N -> R. That is not the same as the set is uncountable. There is no r.e. function N -> computable Reals, but these are still countable. >> >> >> >> HTH >> >> Peter Webb
From: Peter Webb on 19 Jun 2010 22:06
"Tim Little" <tim(a)little-possums.net> wrote in message news:slrni1qn3c.jrj.tim(a)soprano.little-possums.net... > On 2010-06-19, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> Well, there are lots of definitions of a computable Real, I will use >> Wikipedia's most intuitive definition: "computable reals, are the >> real numbers that can be computed to within any desired precision by >> a finite, terminating algorithm." > > Most intuitive, and also least mathematically useful. However, we can > work with that. The input to the algorithm is the desired precision > and the output is a suitable approximant, correct? > > >> 1. Given a list of computable Reals, we can identify the nth >> computable Real on the list by simply counting down to the nth >> entry. > > That is only a "finite, terminating algorithm" if the list is finite. > Since the only input to the algorithm is the desired precision, your > recipe only works if you can embed the list into the algorithm. > No. You could level the same argument against Cantor's original proof. For a number to be computable, it must be able to be calculated to any required degree of accuracy (according to the definition we have just both agreed on). This is obviously true of the anti-diagonal. After all, nobody can write down the full decimal expansion of 1/3. But it is clearly computable, because it can be determined to any arbitrary degree of accuracy. The anti-diagonal is the same; even if we cannot write down the full infinite decimal expansion, we can compute it to any required degree of accuracy. > The rest of your argument depends upon this non-algorithmic step, and > so is snipped. Cantor provides an explicit algorithm for constructing (computing) the anti-diagonal. > > > However, it occurs to me that your misunderstanding may be deeper than > I expected. Let's consider a simpler case: "lists" of length 1. > Suppose x is a real number, say Chaitin's Omega. Is x+1 computable? > No. There is no algorithmic procedure for calculating omega+1q to arbitrary accuracy. > If so, why? > > If not, how does this differ from "suppose L is a list of real > numbers. Is antidiag(L) computable?" > Because there is an algorithmic procedure for calculating the anti-diagonal to any required degree of accuracy. > - Tim |