In article <4c1aea06$0$17174$afc38c87@news.optusnet.com.au>, "Peter Webb" <webbfamily@DIESPAMDIEoptusnet.com.au> wrote:
> "Tim Little" <tim@little-possums.net> wrote in message > news:slrni1jng7.jrj.tim@soprano.little-possums.net... > > On 2010-06-17, Peter Webb <webbfamily@DIESPAMDIEoptusnet.com.au> wrote: > >> Cantor's proof applied to computable numbers proves you cannot form > >> a computable list of computable numbers. > > > > 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. > Cantor's proof provides an explicit and simple algorithm to form such a > number, and it is extremely easy to compute. > > > > 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. > > > > > > > >> Cantor's proof applied to Reals proves you cannot form a computable > >> list of Reals. > > > > Incorrect, and even WTF-worthy. Cantor's proof *is* applied to reals, > > and nothing in it has anything whatsoever to do with computability. > > > > Correct. I never said otherwise. > > > > > >> The property "that you cannot form a computable list" is not the > >> same as the property "is uncountable". For example, computable > >> numbers have the first property but not the second. > > > > 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. The > computable Reals cannot be listed either, but they are definitely countable. > > > > > > >> Cantor's proof is about what can be expressed in a list, and not > >> directly about uncountable sets (which don't even get mentioned in > >> the proof). > > > > "Cannot be expressed in a list" is actually one of many equivalent > > definitions for the term "uncountable". Whether Cantor himself used > > that specific word is irrelevant - the mathematical content of his > > proof was to establish uncountability. > > > > So, are the computable number uncountable? > > A Cantor construction applied to a purported list of all computable Reals > will identify a computable Real not on the list. The diagonal is explicitly > constructible given the list. Therefore by your rule/definition whatever > they are uncountable. But in fact they are countable. How do you explain > this? > > > > > - Tim
According to every definition I can find, the computability of a particular number ought not be dependent on the existence of any particular listing of a countable set of numbers unless the ordering in that listing is itself computable.
So that the computability of a number cannot be dependent on any particular listing unless that listing is itself computable.
Is there, for example, a computable well ordering of all computable numbers?
