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=-0.4 required=5.0 tests=AC_FROM_MANY_DOTS,BAYES_00 autolearn=no 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-07 17:06:29 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news.tele.dk!small.news.tele.dk!194.42.224.136!diablo.netcom.net.uk!netcom.net.uk!btnet-peer!btnet!diablo.theplanet.net!diablo.theplanet.net!psiuk-p2!psiuk-p3!uknet!psiuk-n!news.pace.co.uk!nh.pace.co.uk!not-for-mail From: "Marin David Condic" Newsgroups: comp.lang.ada Subject: Re: Generation of permutations Date: Tue, 7 May 2002 09:22:45 -0400 Organization: Posted on a server owned by Pace Micro Technology plc Message-ID: References: <5ee5b646.0205041652.63032ba6@posting.google.com> NNTP-Posting-Host: dhcp-200-133.miami.pace.co.uk X-Trace: nh.pace.co.uk 1020777768 1744 136.170.200.133 (7 May 2002 13:22:48 GMT) X-Complaints-To: newsmaster@news.cam.pace.co.uk NNTP-Posting-Date: 7 May 2002 13:22:48 GMT X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 5.50.4522.1200 X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4522.1200 Xref: archiver1.google.com comp.lang.ada:23682 Date: 2002-05-07T13:22:48+00:00 List-Id: That's kind of where I was going. Assume you have a data set on a disk. Assume you have a processor capable of accessing that disk and that it has an instruction set represented by 32 bit numbers with some fixed quantity of memory. Fill that memory with random 32 bit numbers. Set the processor to start running at instruction 0. Did the data set on disk get sorted? No? Go back to filling memory again. (Or you could do it with a list in memory, or whatever preconditions you want to establish...) The problem, quite obviously, is that you can't determine in advance that whatever set of instructions you generated doesn't contain an infinite loop. So did the program get stuck in an infinite loop or is it just taking a *really* long time to sort the data? Given that you can't examine the random set of instructions and determine with certainty that any given combination contains an infinite loop & reject that pattern, you can't use it as a slow sort algorithm - assuming that one of the rules of slow sorting is that you guarantee the algorithm will eventually result in a sorted list of data. MDC -- Marin David Condic Senior Software Engineer Pace Micro Technology Americas www.pacemicro.com Enabling the digital revolution e-Mail: marin.condic@pacemicro.com wrote in message news:PsLB8.6706$cT1.98522399@newssvr21.news.prodigy.com... > So "recursively undecidable" is a fancy way of saying it may get stuck > in an infinite loop, and, assuming he didn't mean to allow that, mcondic's > algorithm is perfectly good as a (slow) sorting algorithm.