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-07 00:36:05 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!bloom-beacon.mit.edu!nycmny1-snh1.gtei.net!cpk-news-hub1.bbnplanet.com!news.gtei.net!newscon02.news.prodigy.com!newsmst01.news.prodigy.com!prodigy.com!postmaster.news.prodigy.com!newssvr21.news.prodigy.com.POSTED!3bae8248!not-for-mail From: tmoran@acm.org Newsgroups: comp.lang.ada Subject: Re: Generation of permutations References: <5ee5b646.0205041652.63032ba6@posting.google.com> X-Newsreader: Tom's custom newsreader Message-ID: NNTP-Posting-Host: 67.115.105.241 X-Complaints-To: abuse@prodigy.net X-Trace: newssvr21.news.prodigy.com 1020756911 ST000 67.115.105.241 (Tue, 07 May 2002 03:35:11 EDT) NNTP-Posting-Date: Tue, 07 May 2002 03:35:11 EDT Organization: Prodigy Internet http://www.prodigy.com X-UserInfo1: Q[R_PJSCTS@[SPTX\JKXOFXBWR\HPCTL@XT^OBPLAH[\BTUCCNSKQFCY@TXDX_WHSVB]ZEJLSNY\^J[CUVSA_QLFC^RQHUPH[P[NRWCCMLSNPOD_ESALHUK@TDFUZHBLJ\XGKL^NXA\EVHSP[D_C^B_^JCX^W]CHBAX]POG@SSAZQ\LE[DCNMUPG_VSC@VJM Date: Tue, 07 May 2002 07:35:11 GMT Xref: archiver1.google.com comp.lang.ada:23615 Date: 2002-05-07T07:35:11+00:00 List-Id: > "Marin David Condic" > A better (slower) algorithm would be > to > generate a random set of machine > > instructions, execute them, see if it sorted the list > > You could see if it sorted some particular list, but to > determine whether a set of instructions constitutes a > general sorting algorithm is obviously recursively > undecidable. So this is not a well formed method. I tried an experiment*: the data is three letters chosen from 'a' .. 'c', the instructions are for a machine with instructions: compare and skip if greater, swap, jump, and stop. Generating random 16 line programs, and random data strings, and aborting any program still running after 50 instruction cycles, there were 125801 successes in 874199 tries. Testing each of the successful programs against all possible combinations of three letters from 'a' .. 'c', 9 of the programs successfully sorted all combinations, ie, were general routines capable of sorting any input data in their universe. 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. * Program available on request.