"Peter Webb" <webbfamily@DIESPAMDIEoptusnet.com.au> wrote in message news:4c1b24ce$0$17177$afc38c87@news.optusnet.com.au... > > "Tim Little" <tim@little-possums.net> wrote in message > news:slrni1m2q9.jrj.tim@soprano.little-possums.net... >> On 2010-06-18, Peter Webb >> <webbfamily@DIESPAMDIEoptusnet.com.au> wrote: >>> "Tim Little" <tim@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
QUESTION 1: But ask yourself: is the list of all computable real numbers itself computable? Each real in such a list is computable but can you find a computable function that says which computable real is mapped to 0, which computable real is mapped to 1, which computable real is mapped to 2, and so on?
> construct a Real not on the list. Of course this number is > computable; there is a simple algorithm to compute it.
But ask yourself: since the algorithm you use to compute it calls on the "algorithm" I asked you about in QUESTION 1, is your algorithm depending on another "algorithm" that is non-computable?
>>> 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.
But ask yourself: since there is no computable way to generate a list of all computable reals does that mean that there is no non-computable ways of getting such a list?
> 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.
No, because Cantor's diagonal argument applies to lists that are not computable as well as to lists that are computable.
> In fact the computable Reals can't be listed either, using > exactly the same diagonal proof, but they are countable.
No, computable reals can be listed but there is no computable algorithm that can generate such a list. But if you were given such a list then you could create an anti-diagonal number not on the list. That anti-diagonal, though, is non-computable since it is generated from a non-computable list. <-- But note, what I just wrote there applies to the algorithm in QUESTION 1, not the algorithm you use to generate the anti-diagonal. That is, the anti-diagonal algorithm, in the sense of which digits are changed on the diagonal (e.g. 9-->0, 1-->2, etc), is obviously computable. Please read:
>>> 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.
Yes it is, but there is no finite way of getting such a list (although each real in the list is generated by a finite algorithm).
>>> 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.
Yes, every real in the list is computable. But ask yourself: is the function that maps each natural to each of these reals itself computable?
