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: sxc@itd.dsto.gov.au
Subject: Re: What good is halting prob?
Date: 1995/04/21
Message-ID: <3n8mht$iqh@fang.dsto.gov.au>#1/1
X-Deja-AN: 101370076
references: <3kaksj$iur@isnews.calpoly.edu> <cppD77Ex6.E77@netcom.com>
 <3mve9b$gaj@news.cais.com> <cppD7880n.32B@netcom.com>
organization: DSTO Australia
newsgroups: comp.lang.ada,comp.edu
Date: 1995-04-21T00:00:00+00:00
List-Id: <comp.lang.ada>

In article <cppD7880n.32B@netcom.com>, Robin Rowe <cpp@netcom.com> wrote:
>In article <3mve9b$gaj@news.cais.com>,
>Randolph Crawford <crawford@cais2.cais.com> wrote:
>>If you can identify a different problem as being basically the same as
>>the halting problem....
>
>The "if" was the point of my question. How do you prove equivalence to 
>the halting problem?

You don't need to >prove< equivalence of a problem to the halting problem
for it to be of practical use.  You only need to be able to >recognise< 
that your problem is essentially the same as, or subsumes the halting
problem.

The same goes for complexity (big-O) analysis in many cases.  I often
find it useful to do informal complexity estimates when designing or
reviewing software.

-- Steve