Re: Generation of permutations

[dewar@gnat.com (Robert Dewar)]

"Chad R. Meiners" <crmeiners@hotmail.com> wrote in message news:<abgnvp$1u9q$1@msunews.cl.msu.edu>...
> "Robert Dewar" <dewar@gnat.com> wrote in message
> news:5ee5b646.0205091548.cd99d4c@posting.google.com...

> >   To prove this, we assume the halting problem and then
> >   prove by equivalence to this problem. Let's take a
> >   bubble sort and in the middle of it, run some arbitrary
> >   Turing machine till it halts. But now the general
> >   algorithm will have to be able to determine if it
> >   halts (algorithm is a good sort) or does not halt
> >   (algorithm is junk, runs for ever).
> 
> I just wanted you correct an error in this informal proof.  The proof should
> go like this.

I see no error in the proof, you are somehow misreading what I wrote. Perhaps
you misunderstand my short hand. When I say "assume the halting problem", I
mean "assume that we have already shown that the halting problem for Turing
Machines is undecidable". Was that your problem?

I really can't understand your problem otherwise?

The informal proof above is exactly correct, and seems quite clear to me, so
if it does not seem clear to you, you are misreading it.


> 
> Assume the existence of Is_Sort(x) (The program that decides if x is a
> general sorting algorithm)
> 
> We can construct Halt(Y,Z) (The program that decides if program Y halt on
> input Z) as follows
> 
> Build a machine x'(w) such that x' runs Y(Z) and then runs a bubble sort on
> w.
> 
> run Is_Sort(x')
> 
> return true if x' is a sorting algorithm
> return false if x' is not a sorting algorithm
> 
> end of Halt
> 
> Thus Halt is decidable
> But Halt is undecidable thus contradiction
> Ergo, Is_Sort cannot exist.
> Is_Sort is undecidable.
> 
> You should note that Robert's proof is in essence correct except that he
> assumes that the wrong machine exists.  This could have easily been a typo
> but a very grievous one at that since the entire proof depends upon the
> correct assumption.