Why can no one in sci.math understand my simple point?
in [Logic]
|
From: Owen Jacobson on 19 Jun 2010 23:50 On 2010-06-18 03:56:21 -0400, Peter Webb said: > "Tim Little" <tim(a)little-possums.net> wrote in message > news:slrni1m5c1.jrj.tim(a)soprano.little-possums.net... >> On 2010-06-18, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >>> If you can construct a list of all computable numbers (which you >>> can't), then Cantor's diagonal proof will construct a number not on >>> the list. And that number is definitely computable, because there is >>> a simple algorithm for producing it. Take the nth digit of the nth >>> item on the list >> >> That requires having the list be computable or provided as input, >> neither of which is assumed or proven. >> > > Cantor's proof that there can be no list of all Reals also requires the > list to be provided first. > > The form of the proof is identical - you give me a purported list of > all Reals with some property, and I prove the existence of at least one > Real which has that property which is not on the list, thus proving the > list did not contain all numbers with that property. Cantor used the > property "is Real", I used the property "is computable". > >> Rest snipped as it is based on your false premise. >> >> >> - Tim > > If you believe that you can list all computable numbers, you are > welcome to try and do so. Its a pointless exercise, as I can always > form a computable Real not on the list, but try anyway. Pick a G�del numbering scheme for the Turing machines. Then, given this scheme, the list of computable reals[0] is very simple: the n'th element of the list is the real produced by the real-computing Turing machine[1] with the n'th lowest G�del number (so the 0th element of the list is the real produced by the lowest-numbered machine, the 1st element of the list is the real produced by the next-lowest-numbered machine, and so on). Determining whether a Turing machine computes a real is not a computable problem, but that does not prevent such a list from existing. The antidiagonal of this list differs from every computable number, and there is a simple and effective algorithm for computing it *given the list*, but to show a contradiction you'd still have to prove that this number is computable in exactly sense [0] below. This is (likely) impossible, as this list itself is uncomputable, and the list can neither be embedded in a Turing machine's transition function[2] directly nor stored on the tape[3]. More formal definitions of "computable number" would make the necessary step in proving your argument even harder. -o [0] A real is computable if and only if there is a Turing machine that computes it[1]. [1] A Turing machine computes a real r if and only if, starting with an encoding of some natural number m on its tape, it halts with an encoding of the m'th digit of r on the tape. [2] Keeping in mind that a Turing machine has finitely many states Q and finitely many symbols L, the image of the transition function contains at most |Q| * |L| elements -- far too few to encode an infinite list of reals. [3] At every step, a Turing machine has only finitely-many non-blank cells on the tape -- far too few to encode an infinite list of reals.
From: Tim Little on 19 Jun 2010 23:50 On 2010-06-20, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > "Tim Little" <tim(a)little-possums.net> wrote in message >> Where is the phrase "provided in advance" used in the proof? > > Because Cantor's proof requires us to know the nth digit of the nth > item on the list. No, it just requires that the list L (a mathematical object) be of the type that an n'th digit of the n'th item *exists*. > Indeed Cantor's proof starts with a list No, Cantor's proof starts with a conditional assumption that some mathematical object *is* a list. > If you don't what is on the list already, you cannot possibly prove > that some Real is missing. Now it looks like your deficiency might be in knowing what a proof in predicate logic is. You don't need a separate proof for each list, each one based on the contents of that list. You have a single proof that there does not exist a mathematical entity satisfying the definition of a surjective mapping from natural numbers to reals. > My proof is *exactly* the same, except for inserting the word > "computable" in front of Real. And therefore deficient as making that textual substitution leaves a gap between Cantor's proof that antidiag(L) is a real, and your substituted claim that antidiag(L) is computable real. > Give me a list of all computable numbers in the same form as > Cantor's proof requires a purported list of all Reals, ie a list > where the nth digit of the nth term is known. The constructive portion Cantor's proof requires nothing more than a mapping from N to R. In particular, it does not require that the n'th digit of the n'th term in that mapping "is known". That requirement is entirely due to your imagination. > So by definition if the list contains only computable Reals, we know > the nth digit of each term. Careful with your quantifiers! For a list of computable reals, the following is true: for all n, there exists Turing machine T such that T(n) computes the n'th digit of L(n), but the following is false: there exists Turing machine T such that for all n, T(n) computes the n'th digit of L(n). You appear to be claiming the latter. Are you? - Tim
From: Tim Little on 20 Jun 2010 00:09 On 2010-06-20, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > "Tim Little" <tim(a)little-possums.net> wrote in message >> If you intend your proof to be "exactly the same as Cantor's, but with >> the only difference being the word "computable" in front of the word >> "Real"", it must start with a conditional introduction. In other >> words, something like: >> >> "Suppose that L is a list of computable Reals. That is, L is a >> function from N to R and for all n in N, there exists a Turing >> Machine T_n such that when provided with k as input, T_n halts and >> outputs the k'th decimal digit of L(n)." > > That's not how Cantor's proof starts. Correct: It didn't feature any mention of computable reals (but as I recall it did feature the relevant properties of the definition of a real number). I am presuming that you want *your* proof to substitute "computable real" for "real", and therefore you need to substitute the definition of computable real number for the definition of real number. That means you also need to make that substitution in the definition of a list of computable real numbers. Are you starting to see now why it makes no sense to just drop "computable" in front of every occurrence of the word "real" in the proof? - Tim
From: Tim Little on 20 Jun 2010 00:19 On 2010-06-20, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > Of course it is computable. > > Cantor provides an explicit algorithm for computing it. Cantor provides an explicit algorithm for computing it with the list L as input. Look again at the definition of "computable real". Is "the algorithm may take as input an auxiliary list of infinite many real numbers" part of that definition? > I make no mention of finite algorithms. I just do *exactly* the same > construction, but applied to a purported list of all computable > Reals instead of a purported list of all Reals. The definition of your term "computable real" includes references to "finite algorithm". So you do make reference to a finite algorithm, and Cantor does not. > Cantor: Lets form an anti-diagonal using this explicit construction > based upon the nth digit of the nth Real on the list. It is > obviously a Real, and it is obviously missing. Cantor did not make any assumption that it was "obviously" a real. In fact, he went to some trouble to *prove* that it specified a real number. > Peter: Lets form an anti-diagonal using this explicit construction > based upon the nth digit of the nth computable Real on the list. It > is obviously a computable Real, and it is obviously missing. You, on the other hand, make no effort whatsoever to prove that the antidiagonal number is computable. If you actually did, you would run into insuperable difficulties. The devil is in the details in any mathematical proof. You are actively *avoiding* the details and just assuming they work out. That renders your so-called proof invalid, and is exactly why I accept Cantor's and not yours. At this point, and in this respect, it is clear that you are just as much of a crank as JSH and WM. - Tim
From: Tim Little on 20 Jun 2010 00:24
On 2010-06-20, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > "Tim Little" <tim(a)little-possums.net> wrote in message >> Only if the list itself is a recursively enumerable function. >> Cantor's proof makes no such assumption. > > Yes it does. It requires that the nth digit of the nth term can be > calculated. No, it merely assumes that such a digit exists. > This is not quite as strong as being re, but it is close. It is not at all close. - Tim |