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-08 09:20:27 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: <3CD9505F.344C13EA@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: Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Date: Wed, 08 May 2002 16:20:27 GMT NNTP-Posting-Host: 66.75.151.160 X-Complaints-To: abuse@rr.com X-Trace: twister.socal.rr.com 1020874827 66.75.151.160 (Wed, 08 May 2002 09:20:27 PDT) NNTP-Posting-Date: Wed, 08 May 2002 09:20:27 PDT Organization: RoadRunner - West Xref: archiver1.google.com comp.lang.ada:23726 Date: 2002-05-08T16:20:27+00:00 List-Id: tmoran@acm.org wrote: > If your random program generator will create all possible configurations > of RAM, then one of those is going to be identical to the standard sort > algorithm and eventually you are going to come across it, guaranteed. If [...] I think you're making three of the usual mistakes: 1) A random program generator will not necessarily create all possible configurations of RAM unless you run it an unbounded number of times. 2) In trying to keep track of how many times you've done something, you wind up using memory that you might not have. For example, you can't take a machine with N bits and keep track of whether it has gone through every possible combination of those N bits. If it might run as long as 2**N steps, you need N bits of memory just to hold the counter telling you how many steps it has run. 3) Finite computers are uninteresting to theoreticians. :-) For exactly the reasons you're talking about, having an infinite (for some sufficiently large value of infinite) machine watch a finite machine is generally not worth studying. So a sort algorithm that only worked on lists up to a particular size is basically uninteresting, and doesn't really count as a "general sort". (These are "usual" in the sense that they seem common amongst people who haven't studied the topic a lot, worked out proofs, etc, and hence learned intuitively why certain things work and don't work. It's "usual" in the same way that people saying "language A and B are both turing complete" and thinking that says something about the power or usability of language A or language B in some useful sense.) -- 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%.