Why can no one in sci.math understand my simple point?
in [Logic]
|
From: Newberry on 25 Jun 2010 23:37 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? The digits of pi, e, sqrt(2) etc. can be generated by an algorithm. We can certainly list such algorithms suitably defined. > > 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: Newberry on 26 Jun 2010 00:02 On Jun 15, 1:03 am, Derek Holt <ma...(a)warwick.ac.uk> wrote: > On 15 June, 07:15, "Peter Webb" <webbfam...(a)DIESPAMDIEoptusnet.com.au> > wrote: > > > > > > > "|-|ercules" <radgray...(a)yahoo.com> wrote in message > > >news:87ocucFrn3U1(a)mid.individual.net... > > > > Consider the list of increasing lengths of finite prefixes of pi > > > > 3 > > > 31 > > > 314 > > > 3141 > > > .... > > > > Everyone agrees that: > > > this list contains every digit of pi (1) > > > Sloppy terminology, but I agree with what I think you are trying to say.. > > > > as pi is an infinite digit sequence, this means > > > > this list contains every digit of an infinite digit sequence (2) > > > Again sloppy, but basically true. > > > > similarly, as computable digit sequences contain increasing lengths of ALL > > > possible finite prefixes > > > Not "similarly", but if you are claiming that all Reals which have finite > > decimal expansions can be listed, this is correct. > > > > the list of computable reals contain every digit of ALL possible infinite > > > sequences (3) > > > No. You cannot form a list of all computable Reals. If you could do this, > > then you could use a diagonal argument to construct a computable Real not in > > the list. > > A little more precisely, there does not exist a computable bijection > from the natural numbers to the set of all computable reals. > > But the set of computable reals is of course countable so there does > exist a list of all computable reals - but not a computable list. Does this list have an anti-diagonal? > > Derek Holt. > > > > > > OK does everyone get (1) (2) and (3). > > > No. (3) is not true, as it is based on a false premise (that the computable > > Reals can be listed). > > > > There's no need for bullying (George), it's just a maths theory. Address > > > the statements and questions and add your own. > > > > Herc > > > -- > > > If you ever rob someone, even to get your own stuff back, don't use the > > > phrase > > > "Nobody leave the room!" ~ OJ Simpson- Hide quoted text - > > - Show quoted text -- Hide quoted text - > > - Show quoted text -
From: Virgil on 26 Jun 2010 01:48 In article <b3413a4e-567b-4dfb-8037-21f14b826ede(a)g1g2000prg.googlegroups.com>, Newberry <newberryxy(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?
From: Peter Webb on 26 Jun 2010 02:22 "Virgil" <Virgil(a)home.esc> wrote in message news:Virgil-71EA75.23485925062010(a)bignews.usenetmonster.com... > In article > <b3413a4e-567b-4dfb-8037-21f14b826ede(a)g1g2000prg.googlegroups.com>, > Newberry <newberryxy(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. 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: Virgil on 26 Jun 2010 03:00
In article <4c259cd4$0$1029$afc38c87(a)news.optusnet.com.au>, "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > "Virgil" <Virgil(a)home.esc> wrote in message > news:Virgil-71EA75.23485925062010(a)bignews.usenetmonster.com... > > In article > > <b3413a4e-567b-4dfb-8037-21f14b826ede(a)g1g2000prg.googlegroups.com>, > > Newberry <newberryxy(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. > > 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. Both countability and listability appear to be the case if and only if a listing exists, but neither requires specifying that listing. Is that not so? |