Re: Generation of permutations

[Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov>]

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

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 !

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

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.

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

Actually, the correct analogy to what I'm saying is "Does the
following program find the square root of 25?".

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 :).

-- 
-- Stephe