From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,c42dbf68f5320193 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2002-05-09 10:44:04 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newsfeed1.cidera.com!Cidera!cyclone.columbus.rr.com!cyclone3.kc.rr.com!news3.kc.rr.com!twister.socal.rr.com.POSTED!not-for-mail Message-ID: <3CDAB578.6F32339D@san.rr.com> From: Darren New X-Mailer: Mozilla 4.77 [en] (Windows NT 5.0; U) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.lang.ada Subject: Re: Generation of permutations References: <5ee5b646.0205041652.63032ba6@posting.google.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Date: Thu, 09 May 2002 17:44:03 GMT NNTP-Posting-Host: 66.75.151.160 X-Complaints-To: abuse@rr.com X-Trace: twister.socal.rr.com 1020966243 66.75.151.160 (Thu, 09 May 2002 10:44:03 PDT) NNTP-Posting-Date: Thu, 09 May 2002 10:44:03 PDT Organization: RoadRunner - West Xref: archiver1.google.com comp.lang.ada:23790 Date: 2002-05-09T17:44:03+00:00 List-Id: Stephen Leake wrote: > > "Chad R. Meiners" 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"? No, it means that you can't write a program that runs on a turing machine that will invariably decide in finite time whether C is true or not. C isn't false, it's undecidable. It's right there in the word. :-) Note that "undecidable" isn't talking about A or B or C as such. It's more talking about a program that *looks* at As and Bs and decides whether C is true. > 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". Yes. You have to understand that if you limit "A" to be "a set of instructions emitted by GNAT for bubble sort" then the question goes away. You can just write a program that outputs "true" without even looking at the inputs, and you'll be giving the right answer. But that same program won't work if you give it a different A'', which is a set of instructions emitted by GNAT for generating a random permutation of B''. It's the difference between asking "does this program sort the list" and "does this sort program sort the list". Of course the sort program sorts the list, because you told me it's a sort program. It's kind of like the difference between Big-O and Big-Theta in performance. Does a bubble sort run in O(N**2)? Yep. Can you sort faster? You can't tell just by looking at bubble sorts. No matter how many algorithms you look at, you'll never figure out if you've found the fastest one. You have to look at the *problem* to decide if you've found the fastest algorithm. > Is C' "true"? Yes, but irrelevant. > 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. Right. So? The question is not whether it's possible to look at one program and decide what it does. The question is whether it's possible to write a program to look at all programs and decide whether or not they sort. > 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". "Turing undecidable" means basically that there's no program you can write for a turing machine that given as input A will tell you whether C is true for all B's, if said turing machine program has to always be right and has to always finish in a finite amount of time. Of course for any *one* A you can decide this, but that's irrelevant because that program will not work on some sort that isn't A. Put it this way. Does the following program calculate square roots? Put_Line("5"); Well, if the input is 25, then yes, it calculates square roots. That's a simplification of the logic you're sort of applying there - sure, that a sort program sorts a list can be proven, but that's not what "sorting is undecidable" means. If sorting were decidable, it would be possible to look at any program and figure out reliably whether it sorts or not. Try this one: A": A buggy bubblesort that sorts B as long as the biggest value doesn't start at the beginning of the list. B": A list of numbers with the biggest value already in the middle C": Does A" sort B"? Well, yes, but again, irrelevant for exactly the same reason. No, A" isn't a general sort because it doesn't work when B" is different. For the same reason, sorting isn't decidable because your program to decide whether its a general sort gives the wrong answer when A' is a different program. -- Darren New San Diego, CA, USA (PST). Cryptokeys on demand. The 90/10 rule of toothpaste: the last 10% of the tube lasts as long as the first 90%.