Re: Generation of permutations

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

Stephen Leake wrote:
> 
> Darren New <dnew@san.rr.com> writes:
> 
> > Right. So? The question is not whether it's possible to look at one
> > program and decide what it does. The question is whether it's possible
> > to write a program to look at all programs and decide whether or not
> > they sort.
> 
> That's _your_ question. The question _I_ was addressing, as posed by
> TMoran, was "Is the sequence of instructions emitted by GNAT when it
> compiles bubble sort a program that sorts it's input".

Well, I was addressing the "misinterpretation" claim. I don't think
anyone claimed that the instructions emitted by compiling a bubble sort
don't sort the list. I thought TMoran was saying that he was surprised
that sorting was recursively undecidable since he can prove a bubble
sort does indeed sort. But that's not what "recursively undecidable"
means.

I was addressing this:
--------
> > but to determine whether a set of instructions constitutes a general
> > sorting algorithm is obviously recursively undecidable.

>   So the set of instructions emitted by Gnat when it compiles bubble sort
> code may or may not constitute a general sorting algorithm, and whether
> it does or not is undecidable?  I learn something new every day.
---------

That's a misinterpretation of what "general sorting algorithm" and
"recursively undecidable" means. Hence, that you're asking a different
question is kind of ... irrelevant, and therefore not addressed.
Everything you said was correct, except for any implication that it
relates to undecidability.

> You have to be careful in newsgroup discussions to pay attention to
> the question the poster is asking, and not assume they are talking
> about what you are talking about !

Well, you said "it doesn't sound like a misinterpretation to me". I was
explaining how the second part of the quote between the lines there is a
misinterpretation of the first part. 

> Ok. So what Tom Moran and I were missing was the notion that A _must_
> be allowed to vary over _all_ instruction sequences, not just _a
> particular_ instruction sequence. That's an extremely important
> distinction, and it was _not_ clear in Robert's original post,
> although I can see how he thought it was implied.

Correct. It's easy to prove that (say) a bubble sort does indeed sort.
It's impossible to reliably determine if a given set of instructions
(i.e., one given to you, not one chosen by you) does indeed sort an
arbitrary list of numbers.

"A given set of instructions" means whatever set I give you, not one
that you get to pick. This is normal math-speak, so I'm not surprised
that it was considered implied. Consider

function square(a : double) return double is return a * a; end square;
  -- (assuming I got the syntax right)

This "squares a given number". I.e., it squares whatever number you give
it. If it doesn't work for any number you give it, then it doesn't
"square a given number", at least in normal math-speak. 

> I agree that this is a trivial question. That's why Tom Moran was
> surprised at Robert's response. (we are way lost in he said/she said
> at this point :).

I think so.  I think the original point was that a slow-sort can't be
implemented by generating random instruction sets until you find one
that is a sort program, because you can't tell if any arbitrary
randomly-generated set of instructions is a sort or not. Sure, if you
design the code to be a sort, you can tell it's a sort, and even prove
it's a sort, but you can't generate programs at random and say anything
in particular about them.

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