Re: Generation of permutations

[Darren New <dnew@san.rr.com>]

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%.