Re: Generation of permutations

["Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org>]

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


<tmoran@acm.org> 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.