Why can no one in sci.math understand my simple point?
in [Logic]
|
From: Aatu Koskensilta on 23 Jun 2010 08:22 Tim Little <tim(a)little-possums.net> writes: > You were the one applying the term "recursively enumerable" to a > function. I was merely correcting your mistake. It's perfectly meaningful to say a function is or is not recursively enumerable. To say f : N --> N is recursively enumerable is to say there's a recursive enumeration of {<0,f(0)>, <1,f(1)>, <2,f(2)>, ... }, the graph of f. It's an elementary theorem of recursion theory that if a function is recursively enumerable it's recursive. Peter of course wasn't following this standard usage. -- Aatu Koskensilta (aatu.koskensilta(a)uta.fi) "Wovon man nicht sprechan kann, dar�ber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: Aatu Koskensilta on 23 Jun 2010 08:24 "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> writes: > Well, the algorithm is clearly computable. If you give me a purported > list of all computable numbers, I can compute a missing number. Give how? We can't in any literal sense be given infinitary objects such as an infinite list of computable reals. -- Aatu Koskensilta (aatu.koskensilta(a)uta.fi) "Wovon man nicht sprechan kann, dar�ber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: Aatu Koskensilta on 23 Jun 2010 08:28 "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> writes: > Because Wikipedia only claims that the computable numbers are > recursive, not that they are recursively enumerable. > > If you nthink that they are recursively enumerable, you have to > produce a partial recursive function whose domain is exactly the > uncomputable numbers, and I dare say you can't do that. You're quite thoroughly confused. It might be a good idea to read the first few chapters in a good recursion theory text if you feel compelled to comment on these matters in news. -- Aatu Koskensilta (aatu.koskensilta(a)uta.fi) "Wovon man nicht sprechan kann, dar�ber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: WM on 23 Jun 2010 08:40 On 23 Jun., 13:54, Sylvia Else <syl...(a)not.here.invalid> wrote: > On 23/06/2010 8:34 PM, WM wrote: > > > > > > > On 23 Jun., 04:18, Sylvia Else<syl...(a)not.here.invalid> wrote: > >> On 23/06/2010 11:33 AM, Sylvia Else wrote: > > >>> On 23/06/2010 11:03 AM, Virgil wrote: > >>>> In article > >>>> <2000e81b-7c5a-41be-b6af-98f96f2fb...(a)w31g2000yqb.googlegroups.com>, > >>>> WM<mueck...(a)rz.fh-augsburg.de> wrote: > > >>>>> On 22 Jun., 21:34, Virgil<Vir...(a)home.esc> wrote: > > >>>>>>>> But (A0, A1, A2, ...) is obviously countable. Above you say it's > >>>>>>>> "certainly > >>>>>>>> not countable", but it is. > > >>>>>>> The set is certainly countable. But it cannot be written as a list > > >>>>>> But it HAS been written as a list (A0, A1, A2, ...), > > >>>>> Does this list contain the anti-diagonal of (..., An, ... A2, A1, A0, > >>>>> L0)? > > >>>> Since (..., An, ... A2, A1, A0, L0) does not appear to be a list, why > >>>> should there be any antidiagonal for it? > > >>> Ach! Let's scrap A0 - it's confusing. > > >>> If we let L_n be the nth element in the list L0, and An the > >>> anti-diagonal of the An-1, An-2,...., A1, L_1, L_2, L_3,... > > >>> then > > >>> L_1 > >>> A1 > >>> L_2 > >>> A2 > >>> L_3 > >>> A3 > >>> L_4 > >>> ... > > >>> is a list. I'm still thinking about that. > > >>> Sylvia. > > >> Hmm... > > >> A1 is the antidiagonal of L1 L2 L3... > > >> A2 is the antidiagonal of L1 A1 L2 L3... > > >> A3 is the antidiagonal of L1 A1 L2 A2 L3 L4... > > >> Each An is thus constructed from a list that is different from the list > >> into which it is inserted. So the construction does not lead to a list > >> that should contain its own anti-diagonal, and it doesn't. > > > Ln = > > > An > > ... > > A2 > > A1 > > A0 > > L0 > > > Does your bijection contain the anti-diagonal of > > (..., An, ... A2, A1, A0, L0)? > > I don't understand why you've recast it back to that form. That is a an abbreviation of the construction I proposed. Of course the "..." stand only for an infinite sequence of well defined digits at finite places. > You can't > even form the anti-diagonal of that - what would the first digit of the > antidiagonal be? What would the last digit of a normal Cantor-diagonal? Why should the first digit be more important than the last one? An infinite sequence of digits (that is not converging and not defined by a finite formula, like Cantor's diagonal sequence) is as undefined when the last digit is missing as it is when the first digit is missing. Regards, WM
From: WM on 23 Jun 2010 08:44
On 23 Jun., 14:24, Aatu Koskensilta <aatu.koskensi...(a)uta.fi> wrote: > "Peter Webb" <webbfam...(a)DIESPAMDIEoptusnet.com.au> writes: > > Well, the algorithm is clearly computable. If you give me a purported > > list of all computable numbers, I can compute a missing number. > > Give how? We can't in any literal sense be given infinitary objects such > as an infinite list of computable reals. > That is wrong. Many real numbers can be given by finite definitions like pi or SUM1/n^2 or 0,3 or 0.333... and can be expanded as infinite sequences of digits. In the same way a list of all finite definitions including all computable, all definable, all identifyable and all however specified reals in all possible language can be given. Here it is: 0 1 00 01 10 11 000 .... Regards, WM |