Re: Generation of permutations

["Chad R. Meiners" <crmeiners@hotmail.com>]

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

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.