Why can no one in sci.math understand my simple point?
in [Logic]
|
From: WM on 26 Jun 2010 06:18 On 26 Jun., 00:32, "Mike Terry" > > Please let me know: Does the list consisting of A0, A1, A2, A3, ... > > contain its antidiagonal or not? > > No, of course not. The set of all these antidiagonals A0, A1, A2, A3, ... constructed according to my construction process and including the absent one is a countable set. > > > > That is not a problem. It shows however, that there are countable sets > > that cannot be listed. > > How exactly does it show that there are countable sets that cannot be > listed? > See the one above: The results of my construction process. > > OK, but you've still not given any explanation why you think the > antidiagonals of your process cannot be listed! (I'm genuinely baffled.) You said so yourself, few lines above. Regards, WM
From: Newberry on 26 Jun 2010 09:53 On Jun 25, 11:22 pm, "Peter Webb" <webbfam...(a)DIESPAMDIEoptusnet.com.au> wrote: > "Virgil" <Vir...(a)home.esc> wrote in message > > news:Virgil-71EA75.23485925062010(a)bignews.usenetmonster.com... > > > In article > > <b3413a4e-567b-4dfb-8037-21f14b826...(a)g1g2000prg.googlegroups.com>, > > Newberry <newberr...(a)gmail.com> wrote: > > >> > > No. (3) is not true, as it is based on a false premise (that the > >> > > computable > >> > > Reals can be listed). > > > How is countability any different from listability for an infinite set? > > > Does not countability of an infinite set S imply a surjections from N > > to S? And then does not such a surjection imply a listing? > > It implies a listing must exist, but does not provide such a listing. Does such a listing have an anti-diagonal? > The computable Reals are countable, but you cannot form them into a list of > all computable Reals (and nothing else) where each item on the list can be > computed. > > In order to list a set, it has to be recursively enumerable. Being countable > is not sufficient.
From: Charlie-Boo on 26 Jun 2010 11:59 On Jun 25, 10:24 am, "Jesse F. Hughes" <je...(a)phiwumbda.org> wrote: > Charlie-Boo <shymath...(a)gmail.com> writes: > > On Jun 24, 8:49 am, Aatu Koskensilta <aatu.koskensi...(a)uta.fi> wrote: > >> Charlie-Boo <shymath...(a)gmail.com> writes: > >> > On Jun 15, 2:15 am, "Peter Webb" > > >> >> No. You cannot form a list of all computable Reals. > > >> > Of course you can - it's just the list of Turing Machines. > > >> No, it's not. > > > I asked for a counterexample, to no avail. Don't you think you should > > substantiate your statement or retract it? > > > Each Turing Machine represents some computable real (all computable > > reals are included) and you can list those Turing Machines. The > > Turing Machine represents it as well as any other system of > > representation. > > It is not the case that every TM represents some computable real. > > Example 1: The TM that never halts and never changes the tape does not > represent a computable real. It depends on the system of representation. An empty tape typically represents 0. > Example 2: The TM that repeatedly changes the value in one cell, never > halting, does not represent a computable real. The sequence of values put into a given cell defines the decimal expansion of a real number. Every machine must distinguish between scratch values and actual output. Having a certain cell represent output is also common. Google "Turing Machines". C-B > Other than that, of course, your response was mighty insightful. > -- > Jesse F. Hughes > "I just define real numbers to be all those on the number line, as > they were defined before Dedekind and Cauchy." > -- Ross Finlayson's simple definition.- Hide quoted text - > > - Show quoted text -
From: Charlie-Boo on 26 Jun 2010 12:06 On Jun 25, 3:25 pm, Virgil <Vir...(a)home.esc> wrote: > In article > <adaa005c-c180-4ce0-8d2c-81da912c6...(a)w12g2000yqj.googlegroups.com>, > > > > > > Charlie-Boo <shymath...(a)gmail.com> wrote: > > On Jun 24, 8:49 am, Aatu Koskensilta <aatu.koskensi...(a)uta.fi> wrote: > > > Charlie-Boo <shymath...(a)gmail.com> writes: > > > > On Jun 15, 2:15 am, "Peter Webb" > > > > >> No. You cannot form a list of all computable Reals. > > > > > Of course you can - it's just the list of Turing Machines. > > > > No, it's not. > > > I asked for a counterexample, to no avail. Don't you think you should > > substantiate your statement or retract it? > > > Each Turing Machine represents some computable real (all computable > > reals are included) and you can list those Turing Machines. The > > Turing Machine represents it as well as any other system of > > representation. > > Aren't there Turing machines that don't represent any real at all? No. In general terms, every TM computes some result from its input. Agree? Then if we start with an empty tape, it represents a constant. How we map its execution history determines which real number that represents. There is generally a way to indicate which actions constitute output, which is needed when we use an infinite representation such as its real number binary expansion. If the executon history can be finite, we can map all finite strings into real numbers, as well as the infinite ones as described above. C-B > > > > > > C-B > > > > -- > > > Aatu Koskensilta (aatu.koskensi...(a)uta.fi) > > > > "Wovon man nicht sprechan kann, dar ber muss man schweigen" > > > - Ludwig Wittgenstein, Tractatus Logico-Philosophicus- Hide quoted text - > > - Show quoted text -- Hide quoted text - > > - Show quoted text -
From: Charlie-Boo on 26 Jun 2010 12:19
On Jun 25, 11:37 pm, Newberry <newberr...(a)gmail.com> wrote: > On Jun 25, 7:24 am, "Jesse F. Hughes" <je...(a)phiwumbda.org> wrote: > > > > > > > Charlie-Boo <shymath...(a)gmail.com> writes: > > > On Jun 24, 8:49 am, Aatu Koskensilta <aatu.koskensi...(a)uta.fi> wrote: > > >> Charlie-Boo <shymath...(a)gmail.com> writes: > > >> > On Jun 15, 2:15 am, "Peter Webb" > > > >> >> No. You cannot form a list of all computable Reals. > > > >> > Of course you can - it's just the list of Turing Machines. > > > >> No, it's not. > > > > I asked for a counterexample, to no avail. Don't you think you should > > > substantiate your statement or retract it? > > > > Each Turing Machine represents some computable real (all computable > > > reals are included) and you can list those Turing Machines. The > > > Turing Machine represents it as well as any other system of > > > representation. > > > It is not the case that every TM represents some computable real. > > > Example 1: The TM that never halts and never changes the tape does not > > represent a computable real. > > > Example 2: The TM that repeatedly changes the value in one cell, never > > halting, does not represent a computable real. > > If the Turing machine is hacked such that it outputs a digit on any > state transition does it not represent a real? Yes. But that's hard to control. A simple representation (map) that should satisfy everyone: Your alphabet is {0,1,2} and every time there are two instances of 2 on the tape then the (finite) string between the left-most pair is the next output. Thus every TM will output some sequence of strings that defines a real number. (The empty sequence represents 0.) It is trivial to calculate in binary (using only 0 and 1) and output any desired string surrounded by 2 whenever we want, then immediately erase one of the 2's. Thus every real number will be defined by some TM. > The digits of pi, e, sqrt(2) etc. can be generated by an algorithm. We > can certainly list such algorithms suitably defined. Right again. C-B > > > > > > Other than that, of course, your response was mighty insightful. > > -- > > Jesse F. Hughes > > "I just define real numbers to be all those on the number line, as > > they were defined before Dedekind and Cauchy." > > -- Ross Finlayson's simple definition.- Hide quoted text - > > > - Show quoted text -- Hide quoted text - > > - Show quoted text -- Hide quoted text - > > - Show quoted text - |