Why can no one in sci.math understand my simple point?
in [Logic]
|
From: Peter Webb on 18 Jun 2010 03:47 "Tim Little" <tim(a)little-possums.net> wrote in message news:slrni1m2q9.jrj.tim(a)soprano.little-possums.net... > On 2010-06-18, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> "Tim Little" <tim(a)little-possums.net> wrote in message >>> Cantor's construction applied directly to lists of computable numbers >>> shows almost nothing. Given any list of computable reals, you can >>> produce an antidiagonal real not on the list. Unfortunately the >>> construction says nothing about whether the antidiagonal is computable >>> or not. >> >> Of course its computable. It is a trivial programming exercise to form a >> computable number not on the list, by simply doing digit substitutions. > > Only if the list itself is a computable function. Cantor's proof does > not depend on any such assumption. > If you give me a purported list of all computable numbers, I can explicitly construct a Real not on the list. Of course this number is computable; there is a simple algorithm to compute it. > >> Cantor's proof provides an explicit and simple algorithm to form >> such a number, and it is extremely easy to compute. > > If there exists no algorithm for computing the original list, how do > you propose to use Cantor's proof to make an algorithm for the > antidiagonal of that list? Cantor's proof just requires a list of numbers. If you give me a purported list of all computable numbers, I can produce a computable number not on the list. > > >>> It takes quite a bit of extra work (not part of Cantor's proof) to >>> deduce that there is no computable list of all computable reals. >> >> Cantor's proof applied to computable numbers proves it immediately and >> simply. > > First you have to define the notion of "computable list", and set up > the theorems proving properties about how computable lists and > computable numbers relate. > No I don't, any more than Cantor had to that for all Reals. You cannot produce a list of all computable Reals. Just as you can't produce a list of all Reals. This does not however prove that either is an uncountable set; in fact the set of all computable numbers is countable. > >>> I agree. It was Herc's deranged ramblings that brought computability >>> into this discussion in the first place, when they really are >>> completely irrelevant to Cantor's proof. >>> >> > >> Well, they are relevant if you try and make the mental jump from >> "cannot be listed" to "are therefore uncountable". This simply does >> not follow. > > It follows immediately from the definitions. You appear to have some > bizarre definition of "list" that Cantor never used, employing > concepts not developed until many decades later. > No. And in fact Cantor's diagonal proof does not prove the Reals are uncountable, just that they cannot be listed. Which is all he claimed. In fact the computable Reals can't be listed either, using exactly the same diagonal proof, but they are countable. > >> The computable Reals cannot be listed either, but they are >> definitely countable. > > The computable reals can be listed and are countable. > > >> A Cantor construction applied to a purported list of all computable >> Reals will identify a computable Real not on the list. > > No, it will not. > Yes, it will. Give me any list of computable numbers and I will produce a computable number not on the list. All I have to do is constrruct the diagonal number; this is clearly computable (as the diagonal construction "computes" it), and its not on the list. Go on, try it. If you think you have an explicit list of all computable Reals, produce it for me. "Computing" the anti-diagonal is easy. > >> The diagonal is explicitly constructible given the list. > > The definition of computable number does not include any > presupposition of being supplied with infinite lists of infinite digit > sequences. To be computable, a number must be constructible by a > finite algorithm *without* being given the list. Don't take my word > for it, look up the definition yourself. > We are assuming every number on the list is computable; that is the premise. You give me that list. I take the nth digit of the nth number on the list. The nth number is given to me as part of the list, and so by definition is computable. I look at the nth digit. That is obviously computable. If it is a "1", change it to a "2", and if it is anything else change it to a "1". That is a obviously computable. This is a trivially easy construction that is clearly computable which will give me a computable number not on the list. > > - Tim
From: Peter Webb on 18 Jun 2010 03:49 "Tim Little" <tim(a)little-possums.net> wrote in message news:slrni1m302.jrj.tim(a)soprano.little-possums.net... > On 2010-06-18, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> The diagoinal number is clearly computable. There is a very simple >> algorithm >> for generating it, and this algorithm is easily implemented in a Turing >> Machine. > > Only if you presuppose that the list is initially encoded on the tape > of the Turing Machine. No, I just assume that the list is given to me first, and I can use that list to define/calculate the missing number. That is exactly the same proviso as used in Cantor's proof that you cannot form a list of all Real numbers. > No such proviso is made in the definition of > computable number: it must start from a blank tape. > > The rest of your post is based on your false premise and so snipped. > > > - Tim
From: Peter Webb on 18 Jun 2010 03:56 "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. (This is like arguing with somebody who doesn't understand Cantor's proof that you cannot list all Reals. The proof is very simple, but people don't believe it. If all else fails, I get them to propose a list, and show it has a missing Real. I am happy to explicitly construct a computable Real that isn't on your purported list of all computable Reals). But yet they are countable.
From: Peter Webb on 18 Jun 2010 04:08 "Tim Little" <tim(a)little-possums.net> wrote in message news:slrni1m5nm.jrj.tim(a)soprano.little-possums.net... > On 2010-06-18, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> Wrong. Cantor's diagonal construction explicitly forms a Real not on >> that list, and the Cantorm diagonal number is obviously constructibe >> if every item in the list is constructible. > > You are now mixing up "constructible" with "computable", getting > yourself even more confused. > They are synonyms. Just use "computable" if you like. > It is certainly possible to have a list of computable numbers that is > not computable itself. For example: Chaitin's Omega is not > computable. Define a list L such that the n'th entry on the list > consists of all 1's if the n'th digit of Omega is 1, otherwise it is > all 0's. > You haven't explicitly provided a list of computable Reals. I don't know what Real is in (say) position 657. You can do exactly the same thing with Cantor's original proof that the Reals cannot be listed. You can't form the anti-diagonal of your "list" because you haven't explicitly stated what Reals appear in each position of the list. > Do you agree that every entry in the list is computable? Yes. >Do you think > that the diagonal is therefore computable? > No. Exactly the same thing could be said about Cantor's original proof that the Reals cannot be listed. Every entry is a real, just as every element in your list is a computable Real. So? > >> If you believe that you have a list of all computable Reals, I can >> use a diagonal argument to explicitly construct a Real not on the >> list. This number is obviously computable; Cantor provides an >> explicit algorithm for constructing it, which can be implemented in >> a few lines of code or in a TM. > > Again, look up the definition of "computable number". Note carefully > the absence of the Turing machine being provided with an infinite list > of infinite sequences. Well, perhaps you should provide me with your definition of a computable number. But try and explain to me how the following is not computable: 1. You give me a list of numbers which by definition are all computable. 2. I consider the nth Real in the list. This is computable. I check the nth digit. This is computable. I do the computation of substituting everything except "2" with the character "2", except if its a "2" when I substitute a "1". Clearly computable. Yet this number cannot appear anywhere in the list. This is in no way different to Cantor's proof that the Reals cannot be listed. Yet the computable Reals are countable. Go figure. > > Come back when you have at least checked a basic definition of the > terms you are using. > I have. And the anti-diagonal number is clearly computable if every number on the list is computable, which is the premise. Which means the list cannot be of *all* computable numbers. > > - Tim
From: Peter Webb on 18 Jun 2010 04:16
"Tim Little" <tim(a)little-possums.net> wrote in message news:slrni1m606.jrj.tim(a)soprano.little-possums.net... > On 2010-06-18, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> Give me a list of all computable Reals. > > I specified such a list previously in this thread. It is not a > computable list, but you didn't ask for a computable list - just a > list of computable reals. They are not the same thing. > Cantor said that given a list of Reals, he can generate a Real not on the list. P Webb says that given a list of computable Reals, he can form a computable Real not on the list. The proof is identical. But yet computable numbers are countable. > >> I will use Cantor's diagonal argument to explicitly construct a Real >> which isn't on the list. This is diagonal number clearly computable > > In this case it clearly is not computable. Give me a list which you claim contains all computable numbers, and I will explicitly compute a missing number. > > >> as there is an explicit construction for it. > > No, there is only a finite algorithm *relative to* being provided with > the list initially. Yes, exactly as in Cantor's proof that the Reals cannot be listed. > There is no algorithm to produce the antidiagonal > starting without input, Yes, exactly as per Cantor's proof that the Reals cannot be listed. > which being computable would require. > Cantor's proof requires the list to be specified in advance. So does mine. It is exactly the same proof. And this is deliberate. The whole point is to demonstrate that Cantor's proof does *not* show the Reals are uncountable; it shows they cannot be listed. This only works because I am using *exactly* the same form of proof. > Come back when you read what the term "computable number" means. > You give me a list of computable numbers. Every number on that list is computable. Therefore the nth digit of every Real on the list is computable. The digit substitution rule is computable. Therefore the anti-diagonal Real is computable. |