Re: Generation of permutations

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

Stephen Leake wrote:
> 
> "Chad R. Meiners" <crmeiners@hotmail.com> writes:
> 
> > No that is not what Robert was saying.  He was referring to Rice's Theorem
> > for which you can clearly show that the problem of determining whether a
> > given set of machine instructions will sort an given input is
> > Turing-undecidable.  How did you come to such a misinterpretation?
> 
> Doesn't sound like a "misinterpretation" to me.
> 
> Let's try some symbolic logic:
> 
> A : "a given set of machine instructions"
> B : "a given input"
> C : A sorts B
> 
> Rice's Theorem says statement C is "Turing-undecideable".
> 
> Question; does that mean C is "false"?

No, it means that you can't write a program that runs on a turing
machine that will invariably decide in finite time whether C is true or
not. C isn't false, it's undecidable. It's right there in the word. :-)

Note that "undecidable" isn't talking about A or B or C as such. It's
more talking about a program that *looks* at As and Bs and decides
whether C is true.

> A' : "set of instructions emitted by GNAT for bubble sort"
> B' : "a given input"
> C' : A' sorts B'
> 
> So Rice's Theorem says statement C' is "Turing-undecideable".

Yes. You have to understand that if you limit "A" to be "a set of
instructions emitted by GNAT for bubble sort" then the question goes
away. You can just write a program that outputs "true" without even
looking at the inputs, and you'll be giving the right answer. But that
same program won't work if you give it a different A'', which is a set
of instructions emitted by GNAT for generating a random permutation of
B''.

It's the difference between asking "does this program sort the list" and
"does this sort program sort the list".  Of course the sort program
sorts the list, because you told me it's a sort program.

It's kind of like the difference between Big-O and Big-Theta in
performance. Does a bubble sort run in O(N**2)? Yep. Can you sort
faster?  You can't tell just by looking at bubble sorts. No matter how
many algorithms you look at, you'll never figure out if you've found the
fastest one. You have to look at the *problem* to decide if you've found
the fastest algorithm.

> Is C' "true"?

Yes, but irrelevant.
 
> If C' is "true", does that mean A' "constitutes a general sorting
> algorithm". I think so, if we assume B' is allowed to vary over all
> possible inputs.

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.
 
> I suspect the problem here lies in the conflict between the English
> meanings of "true" and "decideable", and the formal meaning of
> "Turing-(un)decideable". We all believe that C' is "true", but that's
> not the same as "Turing-decideable".

"Turing undecidable" means basically that there's no program you can
write for a turing machine that given as input A will tell you whether C
is true for all B's, if said turing machine program has to always be
right and has to always finish in a finite amount of time. Of course for
any *one* A you can decide this, but that's irrelevant because that
program will not work on some sort that isn't A.
 


Put it this way. Does the following program calculate square roots?
   Put_Line("5");

Well, if the input is 25, then yes, it calculates square roots.

That's a simplification of the logic you're sort of applying there -
sure, that a sort program sorts a list can be proven, but that's not
what "sorting is undecidable" means. If sorting were decidable, it would
be possible to look at any program and figure out reliably whether it
sorts or not.

Try this one:
A": A buggy bubblesort that sorts B as long as the biggest value doesn't
start at the beginning of the list.
B": A list of numbers with the biggest value already in the middle
C": Does A" sort B"?

Well, yes, but again, irrelevant for exactly the same reason. No, A"
isn't a general sort because it doesn't work when B" is different. For
the same reason, sorting isn't decidable because your program to decide
whether its a general sort gives the wrong answer when A' is a different
program.

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