From: Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov>
Subject: Re: Generation of permutations
Date: 06 May 2002 09:52:02 -0400
Date: 2002-05-06T13:58:46+00:00 [thread overview]
Message-ID: <uznzd8jul.fsf@gsfc.nasa.gov> (raw)
In-Reply-To: ab4ovt$1d51$1@msunews.cl.msu.edu
"Chad R. Meiners" <crmeiners@hotmail.com> writes:
> No that is not what Robert was saying. He was referring to Rice's Theorem
> for which you can clearly show that the problem of determining whether a
> given set of machine instructions will sort an given input is
> Turing-undecidable. How did you come to such a misinterpretation?
Doesn't sound like a "misinterpretation" to me.
Let's try some symbolic logic:
A : "a given set of machine instructions"
B : "a given input"
C : A sorts B
Rice's Theorem says statement C is "Turing-undecideable".
Question; does that mean C is "false"?
A' : "set of instructions emitted by GNAT for bubble sort"
B' : "a given input"
C' : A' sorts B'
So Rice's Theorem says statement C' is "Turing-undecideable".
Is C' "true"?
If C' is "true", does that mean A' "constitutes a general sorting
algorithm". I think so, if we assume B' is allowed to vary over all
possible inputs.
I suspect the problem here lies in the conflict between the English
meanings of "true" and "decideable", and the formal meaning of
"Turing-(un)decideable". We all believe that C' is "true", but that's
not the same as "Turing-decideable".
I'll leave it to someone else to give the formal definition of
"Turing-decideable"; I'm sure I'd get it wrong :).
>
>
> <tmoran@acm.org> wrote in message
> news:p_iB8.3409$9d1.36389081@newssvr21.news.prodigy.com... > > but
> to determine whether a set of instructions constitutes a general > >
> sorting algorithm is obviously recursively undecidable. > So the set
> of instructions emitted by Gnat when it compiles bubble sort > code
> may or may not constitute a general sorting algorithm, and whether >
> it does or not is undecidable? I learn something new every day.
>
>
--
-- Stephe
next prev parent reply other threads:[~2002-05-06 13:52 UTC|newest]
Thread overview: 88+ messages / expand[flat|nested] mbox.gz Atom feed top
2002-04-29 11:54 Generation of permutations Reinert Korsnes
2002-04-30 13:52 ` Ted Dennison
2002-04-30 14:20 ` Marin David Condic
2002-05-02 12:32 ` Robert Dewar
2002-05-02 15:47 ` Ted Dennison
2002-05-02 16:16 ` Mark Biggar
2002-05-03 13:04 ` Marin David Condic
2002-05-05 0:52 ` Robert Dewar
2002-05-05 23:11 ` tmoran
2002-05-06 2:13 ` Chad R. Meiners
2002-05-06 13:52 ` Stephen Leake [this message]
2002-05-09 17:44 ` Darren New
2002-05-09 18:07 ` Stephen Leake
2002-05-09 20:58 ` Darren New
2002-05-09 23:21 ` tmoran
2002-05-09 23:51 ` Darren New
2002-05-10 3:37 ` tmoran
2002-05-10 3:59 ` Darren New
2002-05-10 13:13 ` Robert Dewar
2002-05-25 16:21 ` Robert I. Eachus
2002-05-09 23:24 ` Robert Dewar
2002-05-09 23:48 ` Robert Dewar
2002-05-10 3:37 ` tmoran
2002-05-10 15:10 ` Chad R. Meiners
2002-05-11 4:04 ` Robert Dewar
2002-05-16 1:35 ` Chad R. Meiners
2002-05-11 4:05 ` Robert Dewar
2002-05-06 15:46 ` Wes Groleau
2002-05-06 16:21 ` Chad R. Meiners
2002-05-06 16:33 ` Darren New
2002-05-07 0:06 ` tmoran
2002-05-07 0:26 ` Darren New
2002-05-07 1:56 ` tmoran
2002-05-07 10:39 ` Robert Dewar
2002-05-07 17:25 ` Chad R. Meiners
2002-05-08 2:27 ` Robert Dewar
2002-05-08 8:44 ` Mats Karlssohn
2002-05-07 17:00 ` Wes Groleau
2002-05-06 21:33 ` Robert Dewar
2002-05-06 17:26 ` Marin David Condic
2002-05-07 7:35 ` tmoran
2002-05-07 13:22 ` Marin David Condic
2002-05-08 5:23 ` tmoran
2002-05-08 14:10 ` Marin David Condic
2002-05-09 16:20 ` Darren New
2002-05-09 19:04 ` tmoran
2002-05-08 16:20 ` Darren New
2002-05-08 17:31 ` tmoran
2002-05-08 17:39 ` Chad R. Meiners
2002-05-07 15:34 ` Darren New
2002-05-07 17:44 ` Chad R. Meiners
2002-05-07 19:58 ` tmoran
2002-05-07 21:05 ` Turing-undecidable languages (OT) Chad R. Meiners
2002-05-08 8:24 ` Danx
2002-05-08 17:16 ` Chad R. Meiners
2002-05-10 2:37 ` Robert Dewar
2002-05-08 9:16 ` Dmitry A. Kazakov
2002-05-08 17:18 ` Chad R. Meiners
2002-05-09 20:56 ` Dmitry A.Kazakov
2002-05-09 16:18 ` Chad R. Meiners
2002-05-10 2:52 ` Robert Dewar
2002-05-08 2:17 ` Generation of permutations Robert Dewar
2002-05-03 13:13 ` Ted Dennison
2002-05-03 13:24 ` Lutz Donnerhacke
2002-04-30 15:06 ` Hyman Rosen
2002-05-01 8:40 ` Adrian Hoe
2002-05-01 19:53 ` Hyman Rosen
2002-05-11 1:52 ` Steven Deller
2002-05-02 16:24 ` Mark Biggar
2002-04-30 17:12 ` Wes Groleau
2002-04-30 22:57 ` Robert Dewar
2002-05-01 0:54 ` tmoran
2002-05-01 9:42 ` Florian Weimer
2002-05-02 12:34 ` Robert Dewar
2002-05-01 12:43 ` Robert Dewar
2002-05-01 15:05 ` TO WHOM IT MAY CONCERN Wes Groleau
2002-05-02 12:27 ` More on copyright, (Re: TO WHOM IT MAY CONCERN) Robert Dewar
2002-05-08 13:56 ` Wes Groleau
2002-05-08 18:01 ` Robert Dewar
2002-05-08 18:31 ` Hyman Rosen
2002-05-09 13:41 ` Wes Groleau
2002-05-01 12:46 ` Generation of permutations Robert Dewar
2002-05-01 18:22 ` OT:Copyright, was " tmoran
2002-05-01 21:56 ` Robert Dewar
2002-05-01 23:45 ` tmoran
2002-05-02 11:58 ` Robert Dewar
2002-05-01 14:55 ` Wes Groleau
2002-05-02 12:41 ` Robert Dewar
replies disabled
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox