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-06 17:26:34 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.socal.rr.com!cyclone3.kc.rr.com!news3.kc.rr.com!twister.socal.rr.com.POSTED!not-for-mail Message-ID: <3CD71F4D.C29A60FC@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: <3CD6B078.49954B6A@san.rr.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Date: Tue, 07 May 2002 00:26:33 GMT NNTP-Posting-Host: 66.75.151.160 X-Complaints-To: abuse@rr.com X-Trace: twister.socal.rr.com 1020731193 66.75.151.160 (Mon, 06 May 2002 17:26:33 PDT) NNTP-Posting-Date: Mon, 06 May 2002 17:26:33 PDT Organization: RoadRunner - West Xref: archiver1.google.com comp.lang.ada:23607 Date: 2002-05-07T00:26:33+00:00 List-Id: tmoran@acm.org wrote: > > > ... is generally taken to mean ... by folks who ... > The First Commandment to a writer is "Know your audience". Phrases > with an idiosyncratic meaning to one audience are just confusing when > directed to different audiences. The First Commandment to a newsgroup reader is "if you don't understand it, try google." Somehow, tho, I thought that any software engineer would have had at least one class about computability (or at least formal mathematics) and would therefore have recognised the form of the statement. If you don't recognise "a given set of machine instructions" as meaning any arbitrary set of programs then, well, I guess you haven't studied much formally. > Prof to students: "Here is a set of machine instructions in the form of > Ada source code. What do they do? Prove it." > Poor students: "How the heck should I know?" > Medium students: "It's a bubble sort, and here's a proof that it works." > Good students: "How the heck could I know?" But that's not the question. The question is "write a program that tells whether the input to that program is another program that will sort the list." The question isn't "does program X sort the list", but rather "does program Y reliably tell you that program X sorts a list, for any program X." How about this: Take the output from SHA-1 hashing a counter. Arrange the list in the order indicated by the result of the hash. Check to see if it's sorted, and halt if it is. Does that ever sort the list? Good students: "How the heck could I know?" The original comment was > to determine whether a set of instructions constitutes a > general sorting algorithm is obviously recursively > undecidable If you don't understand that sentence, then why argue with people who explain it to you? If "recursively undecidable" doesn't mean anything to you, then arguing that "a given set of instructions" is unintuitive is foolish. Implicit in the meaning of "recursively undecidable" is the quantifier in front of "a set of instructions." You asked what you're missing, and when you're told that, you argue that ... what, you shouldn't have missed it? Or that the person telling you what you missed is wrong? Or that since you're more ignorant than the Robert about the subject, he should educate you before pointing out your mistake? -- 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%.