Re: Generation of permutations

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

tmoran@acm.org wrote:
> 
> > ... is generally taken to mean ... by folks who ...
>   The First Commandment to a writer is "Know your audience".  Phrases
> with an idiosyncratic meaning to one audience are just confusing when
> directed to different audiences.

The First Commandment to a newsgroup reader is "if you don't understand
it, try google." 

Somehow, tho, I thought that any software engineer would have had at
least one class about computability (or at least formal mathematics) and
would therefore have recognised the form of the statement. If you don't
recognise "a given set of machine instructions" as meaning any arbitrary
set of programs then, well, I guess you haven't studied much formally.

>   Prof to students: "Here is a set of machine instructions in the form of
> Ada source code.  What do they do?  Prove it."
> Poor students: "How the heck should I know?"
> Medium students: "It's a bubble sort, and here's a proof that it works."
> Good students: "How the heck could I know?"

But that's not the question. The question is "write a program that tells
whether the input to that program is another program that will sort the
list." The question isn't "does program X sort the list", but rather
"does program Y reliably tell you that program X sorts a list, for any
program X."

How about this:
Take the output from SHA-1 hashing a counter. Arrange the list in the
order indicated by the result of the hash. Check to see if it's sorted,
and halt if it is. Does that ever sort the list? Good students: "How the
heck could I know?"

The original comment was 
> to determine whether a set of instructions constitutes a
> general sorting algorithm is obviously recursively
> undecidable

If you don't understand that sentence, then why argue with people who
explain it to you? If "recursively undecidable" doesn't mean anything to
you, then arguing that "a given set of instructions" is unintuitive is
foolish. Implicit in the meaning of "recursively undecidable" is the
quantifier in front of "a set of instructions." You asked what you're
missing, and when you're told that, you argue that ... what, you
shouldn't have missed it? Or that the person telling you what you missed
is wrong? Or that since you're more ignorant than the Robert about the
subject, he should educate you before pointing out your mistake? 

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