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: mab@dst17.wdl.loral.com (Mark A Biggar) Subject: Re: What good is halting prob? Date: 1995/04/19 Message-ID: <1995Apr19.164149.12564@wdl.loral.com>#1/1 X-Deja-AN: 101283229 sender: news@wdl.loral.com references: <3n0ka7$b57@hermes.unt.edu> organization: Loral Western Development Labs newsgroups: comp.lang.ada,comp.edu Date: 1995-04-19T00:00:00+00:00 List-Id: 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. -- Mark Biggar mab@wdl.loral.com