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: 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.
From: Peter Webb on 18 Jun 2010 04:20
"Tim Little" <tim(a)little-possums.net> wrote in message news:slrni1m63n.jrj.tim(a)soprano.little-possums.net... > On 2010-06-18, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> I made no premise. > > Sure you did: you assumed that no list of computable numbers can > exist. You also assumed an incorrect definition of "computable". > No, I assumed that a list of all computable numbers can exist. Then I gave a simple algorithm which forms a computable number which is not on the list. I therefore proved that no list of all computable numbers can exist. It is *exactly* the same as Cantor's proof that the Reals cannot be listed. It is of interest because it is known that the computable numbers are countable. Therefore the property "cannot be listed" is *not* the same as the property "is uncountable". Cantor's diagonal proof does *not* show the Reals are uncountable; it just proves the much weaker statement that "the Reals cannot be listed". > > - Tim |