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: dewar@cs.nyu.edu (Robert Dewar)
Subject: Re: What good is halting prob?
Date: 1995/04/19
Message-ID: <dewar.798322519@gnat>#1/1
X-Deja-AN: 101283266
references: <dewar.798207364@gnat> <3n0ka7$b57@hermes.unt.edu>
 <dewar.798232482@gnat> <1995Apr19.164149.12564@wdl.loral.com>
organization: Courant Institute of Mathematical Sciences
newsgroups: comp.lang.ada,comp.edu
Date: 1995-04-19T00:00:00+00:00
List-Id: <comp.lang.ada>

Mark Biggar says:

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

On the other hand, suppose we had already solved problem X, and then
managed to reduce the halting problem to problem X. That would be
quite interesting :-)