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=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,86fd56abf3579c34 X-Google-Attributes: gid103376,public X-Google-Thread: 10db24,77f71d0bde4c5bb4 X-Google-Attributes: gid10db24,public From: srt@zaphod.csci.unt.edu (Steve Tate) Subject: Re: What good is halting prob? Date: 1995/04/19 Message-ID: <3n3oh8$sgu@hermes.unt.edu>#1/1 X-Deja-AN: 101283237 distribution: world references: <3n0ka7$b57@hermes.unt.edu> <1995Apr19.164149.12564@wdl.loral.com> followup-to: comp.lang.ada,comp.edu organization: University of North Texas newsgroups: comp.lang.ada,comp.edu Date: 1995-04-19T00:00:00+00:00 List-Id: Mark A Biggar (mab@dst17.wdl.loral.com) wrote: > In article dewar@cs.nyu.edu (Robert Dewar) writes: > >yes, quite right: (one equivalence proof = two reduction proofs) > >Ah well, difficult to type in accurate text books into a newsgroup :-) > All true, but for the type of problems we have been discussing is usually > sufficies to show that Problem X reduces to the Halting Problem and not > vis-versa because we already know that the Halting Problem is unsolvable > and that's what we are trying to show about Problem X. Be careful about what wording you use though. If you want to show that problem X is non-recursive (i.e., non-computable) then you only have to do one reduction. However, this is not an equivalence proof, and you should not be lulled into thinking that X and the Halting Problem are equivalent because they are both non-computable. Among the non-computable problem there are many "degrees" of non-computable functions, some harder in a very important way than others. In fact, the halting problem is one of the *easier* non-computable problems! -- Steve Tate --- srt@cs.unt.edu | "As often as a study is cultivated by narrow Dept. of Computer Sciences | minds, they will draw from it narrow University of North Texas | conclusions." -- John Stuart Mill, 1865. Denton, TX 76201 |