Re: Generation of permutations

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

Sorry for the delayed response; I was away.

"Robert Dewar" <dewar@gnat.com> wrote in message
news:5ee5b646.0205102004.6142053c@posting.google.com...
> 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?

No, your proof has a logical error in it along with its the language
ambiguity.  It doesn't existablish proof of equivalance nor does it prove
that Is_Sort is undecidable.  It fails to prove that Is_Sort might exist
without needing to depend upon the halting problem.  This is why we must
assume that Is_Sort is decidable and show that this leads to a
contradiction.

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

While I am sure you understand why Is_Sort is undecidable, you have gone
about proving it incorrectly.  You might argue that there is enough
reasoning within your argument for anyone to "see" why it is correct.  For
someone that is willing to believe your proof, this argument might suffice,
but a skeptic would raise the problem I mentioned above.  The skeptic,
however, cannot argue with my proof by contradiction because it leaves no
room to argue.

Please note that I was not saying that you are completely off the mark, but
instead that you were not careful in your proof and made in an error that
anyone might have made since the error is not obvious.

-CRM