Why can no one in sci.math understand my simple point?
in [Logic]
|
From: Tim Little on 20 Jun 2010 21:07 On 2010-06-21, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > "Mike Terry" <news.dead.person.stones(a)darjeeling.plus.com> wrote in message >> 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. Read the definition of computable real carefully, please! You need to show that there exists a finite algorithm that accepts input n, with *no* additional input, and produces the n'th digit. You don't get to put an upper bound on n when exhibiting the algorithm. The same algorithm must work for all n. For some fixed M, you could embed M digits of the diagonal into the algorithm, and the algorithm would work for all n < M. But that's not enough: it has to work for all n. > How is this number any less computable than the square root of 2? There exists a straightforward algorithm (e.g. Newton's method) to calculate square roots to arbitrary precision. You can embed the value 2 into an algorithm which accepts n as input, and applies Newton's method to generate the first n digits of sqrt(2). You cannot embed the list L into an algorithm which applies the antidiagonal procedure for arbitrary input n, as the list L is infinite. You can only embed finitely many digits of L, and so there will be an upper bound on the values of n for which the algorithm works. > I don't use the whole list. To calculate the nth digit of the > anti-diagonal I only need the first n terms to n decimal places > accuracy. That is a finite amount of data. However, you then need infinitely many different algorithms for increasing n. A number is only computable if the same algorithm works for all n. >> 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. > > Well, Cantor asks for a list of Reals. And D(m,n) is computable in > my case by definition No, it is not. The m'th entry is computable for each m, with a different algorithm for every m. For D to be computable, there must exist a *single* finite algorithm that subsumes them all. There exists no such algorithm. - Tim
From: |-|ercules on 20 Jun 2010 21:23 "Newberry" <newberryxy(a)gmail.com> wrote > Please CONSTRUCT the anti-diagonal in the space provided below. > > Virgil's anti-diagonal construction > BEGIN > > > > END Oh boy this will be funny. Watch as Virgin proves An AD(n) =/= L(n,n) -> An AD(n) =/= L(n,) using ... WAIT FOR IT An AD(n) = L(n,n) mod 2 + 4 Then he'll omit the term *new digit sequence* and bait and switch and swear black and blue its a NEW NUMBER and it's PROVABLY NOT ON THE LIST and CANTOR PROVED IT and WHAT AXIOM DARES CONTRADICT ZFC! But he won't give a straight answer to how many digits wide this set is 3 31 314 .... because he can't construct a new digit sequence that isn't computable. Herc
From: Peter Webb on 20 Jun 2010 21:27 "Newberry" <newberryxy(a)gmail.com> wrote in message news:b1d23660-1b7a-4682-affa-952cf2d9e03b(a)e34g2000pra.googlegroups.com... On Jun 20, 1:18 pm, Virgil <Vir...(a)home.esc> wrote: > In article > <f92c169d-ee85-40c2-aa82-c8bdf06f7...(a)j4g2000yqh.googlegroups.com>, > > WM <mueck...(a)rz.fh-augsburg.de> wrote: > > On 20 Jun., 17:51, "Jesse F. Hughes" <je...(a)phiwumbda.org> wrote: > > > > Cantor was this utterly insane freak who chose not to accept > > > Newberry's > > > word for it, and instead *prove* that there was no list of all real > > > numbers. Obviously, his proof is nonsense, because, after all, > > > Newberry > > > said there was no list. > > > His proof is nonsense because it proves that a countable set, namely > > the set of all reals of a Cantor-list and all diagonal numbers to be > > constructed from it by a given rule an to be added to this list, > > cannot be listed, hence, that this indisputably countable set is > > uncountable. > > That is a deliberate misrepresentation of the so called "diagonal proof". > > What that proof (not actually by by Cantor himself) ays is that any > listing of reals is necessarily incomplete because given such a listing > one can always construct a real not listed in it. Please CONSTRUCT the anti-diagonal in the space provided below. _______________________________ Well, I can't construct the anti-diagonal unless you tell me what the nth digit of the nth term in the list is. After all, if you don't tell me what is on the list, I possibly tell you waht computable Real is missing, and more than Cantor can tell you what Real is missing unless you show him the list first.
From: Tim Little on 20 Jun 2010 21:29 On 2010-06-20, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > Thus if your list contained say: > > .1111111 > .2222222 > .1111222 > > The antidiagonal is 0.212... > > Notice that I computed this quite easily? I notice that your algorithm only works for n < 4. >> You will not be able to fill that hole, because there are >> well-defined functions L for which antidiag(L) is *not* a >> computable real. There are even explicitly-definable such lists, >> and furthermore there are such lists where there are only two >> values in the range: for example, let L(n) = 0 if the n'th digit of >> Omega is 0, L(n) = 1/9 otherwise. > > I am having a bit of trouble computing even the first term of that. According to one of Chaitin's papers, the first term is 0. But that's irrelevant: it is either 0 or 1/9 and in *both* cases it is a computable real. You personally might not know what it is, I might not know what it is, but the list entry exists and is a computable real either way. > I am also wondering how Cantor would have felt about that. I can't > see that he can change a "1" to a "2" etc if he doesn't know what > the value is. You appear to be laboring under the misapprehension that Cantor had to change any value to anything. He proved that if *there exists* a list of reals, then *there exists* an antidiagonal real that is not on the list. If we don't know what is on the list, then we won't know what the antidiagonal is - but we still know it has one. > But you have made an excellent point in your example. When Cantor is > confronted with some digit as poorly defined your Chaitan's number > example It's not poorly defined at all; it is precisely defined. But even that is more than required: the proof even works for *undefinable* lists of reals. For every hypothetical mathematical object that is a list of reals, that list has an antidiagonal. > it can simply say "I don't care what the number actually is". There > is not the same luxury with computable Reals; this act of > arbitrary/random choice can make them uncomputable, as your example > shows. It is not arbitrary or random at all. Omega has a precise mathematical definition and is a single real value. > Well, yes, but I am failing to see how you are providing a list of > computable Reals when you won't actually tell me even what is the > first computable Real on the list. I did tell you with clear mathematical precision. > Cantor's algorithm requires slightly more than a set of Reals, it > also demands they are ordered for us - there is a mapping from N to > that set. I provided that mapping. It is precisely defined and mathematically unambiguous, merely difficult to use in practice. > That's still a nice example, that every item in a list can be > computable but the anti-diagonal is not. But I still don't think you > are really playing fair with this one. Fairness has nothing to do with it. I already provided far more than Cantor's proof assumes. > You have to tell me what the first, second, third etc items are on > the list. I mean, that's what a list is after all, a mapping from N, > and that is what Cantor's proof requires as input. As state before, Cantor's proof does not require any input at all. It proves the single *closed* proposition "there does not exist a complete list of real numbers". No free variables, no input. It is *not* a schema of theorems "L is not a complete list of real numbers", one for each L. In some fields of mathematics such schemata exist, but Cantor's theorem was not an example of such. - Tim
From: Peter Webb on 20 Jun 2010 21:34
"Tim Little" <tim(a)little-possums.net> wrote in message news:slrni1tcq4.jrj.tim(a)soprano.little-possums.net... > On 2010-06-20, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> "Tim Little" <tim(a)little-possums.net> wrote in message >>> No you couldn't, as it makes no assumption of any finite algorithm. >>> Only *your* alteration of Cantor's proof assumes any sort of finite >>> algorithm, as it is required for the definition of "computable real". >> >> I don't say anything about finite algorithms. I just ask for a list of >> computable Reals, in the same form a Cantor asks for a list of Reals. > > If you don't realize that "finite algorithm" is contained within the > definition of "computable real" that you use, there really is no use > in continuing this line of conversation any further. Goodbye. > 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. 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. Exactly the same as in Cantor's original proof. Producing the purported list of all computable Reals is your problem. That you cannot do this is exactly my point, yes I know there is no finite algorithm for calculating every computable Real, that is what I am trying to prove - that there can be no list of exactly the computable numbers. Any more than there can be no list of all Reals. And its not because the computable Reals are uncountable ... they are enumerable but not recursively enumerable. > > - Tim |