"Tim Little" <email@example.com> wrote in message news:firstname.lastname@example.org... > On 2010-06-18, Peter Webb <webbfamily@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?
>Do you think > that the diagonal is therefore computable? >
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.
> >> 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.