From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-0.3 required=5.0 tests=BAYES_00,FREEMAIL_FROM, REPLYTO_WITHOUT_TO_CC autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,c42dbf68f5320193 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2002-05-15 18:40:15 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!iad-peer.news.verio.net!news.verio.net!solaris.cc.vt.edu!news.vt.edu!msunews!not-for-mail From: "Chad R. Meiners" Newsgroups: comp.lang.ada Subject: Re: Generation of permutations Date: Wed, 15 May 2002 21:35:15 -0400 Organization: Michigan State University Message-ID: References: <5ee5b646.0205041652.63032ba6@posting.google.com> <3CDAB578.6F32339D@san.rr.com> <5ee5b646.0205091548.cd99d4c@posting.google.com> <5ee5b646.0205102004.6142053c@posting.google.com> Reply-To: "Chad R. Meiners" NNTP-Posting-Host: arctic.cse.msu.edu X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 6.00.2600.0000 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 Xref: archiver1.google.com comp.lang.ada:24140 Date: 2002-05-15T21:35:15-04:00 List-Id: Sorry for the delayed response; I was away. "Robert Dewar" 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