From: sxc@itd.dsto.gov.au
Subject: Re: What good is halting prob?
Date: 1995/04/21
Date: 1995-04-21T00:00:00+00:00 [thread overview]
Message-ID: <3n8mht$iqh@fang.dsto.gov.au> (raw)
In-Reply-To: cppD7880n.32B@netcom.com
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
next prev parent reply other threads:[~1995-04-21 0:00 UTC|newest]
Thread overview: 75+ messages / expand[flat|nested] mbox.gz Atom feed top
1995-03-17 0:24 Should internet support software be written in Ada? Bill Brooks
1995-03-17 8:47 ` Anthony Shipman
1995-03-19 22:06 ` David Weller
1995-03-23 15:05 ` Theodore Dennison
1995-03-24 10:26 ` Fred J. McCall
1995-03-27 9:50 ` Robb Nebbe
1995-03-27 19:43 ` State machines and Goto's (was Re: Should internet support software be written in Ada?) Robert I. Eachus
1995-03-27 23:14 ` Arthur Evans Jr
1995-03-29 0:00 ` Dan
1995-04-01 0:00 ` Mike White
1995-04-04 0:00 ` Robert Dewar
1995-04-06 0:00 ` Theodore Dennison
1995-04-06 0:00 ` Norman H. Cohen
1995-04-07 0:00 ` Tucker Taft
1995-04-07 0:00 ` Robert Dewar
1995-04-07 0:00 ` Mike White
[not found] ` <3ma7rt$smt@kaiwan009.kaiwan.com>
[not found] ` <dewar.797514490@gnat>
[not found] ` <3meunj$66u@felix.seas.gwu.edu>
1995-04-20 0:00 ` CS teachers who can't code their way outta a paper bag Richard A. O'Keefe
1995-03-27 14:24 ` Should internet support software be written in Ada? Theodore Dennison
1995-03-28 0:00 ` Robert Dewar
1995-03-28 9:32 ` Fred J. McCall
1995-03-29 0:00 ` Theodore Dennison
1995-03-29 0:00 ` Robert I. Eachus
1995-03-31 0:00 ` Theodore Dennison
1995-04-05 0:00 ` Wes Groleau
1995-04-07 0:00 ` State machines and Goto's (was Re: Should internet support software be written in Ada?) Wes Groleau
1995-04-07 0:00 ` Robert Firth
[not found] ` <D6qyv0.6Jv@nntpa.cb.att.com>
1995-04-19 0:00 ` Fergus Henderson
1995-04-19 0:00 ` Fred J. McCall
1995-04-19 0:00 ` George Haddad
1995-04-20 0:00 ` Mark A Biggar
1995-04-20 0:00 ` State machines and Goto's (was Re: Sho Brian Hanson
1995-04-20 0:00 ` State machines and Goto's (was Re: Should internet support software be written in Ada?) Bill Winn
1995-04-20 0:00 ` Robert Dewar
1995-03-22 23:08 ` Should internet support software be written in Ada? Keith Thompson
[not found] ` <3mrv7h$3mq@larry.rice.edu>
[not found] ` <3msnu4$6am@kaiwan009.kaiwan.com>
[not found] ` <KUBEK.95Apr18213646@insage.gerii.insa-tlse.fr>
[not found] ` <cppD792GC.1uI@netcom.com>
1995-04-20 0:00 ` Teaching OO/C++ Philip Machanick
[not found] ` <dewar.798207931@gnat>
[not found] ` <cppD78ywq.B31@netcom.com>
[not found] ` <dewar.798240702@gnat>
1995-04-19 0:00 ` Problems with proofs Brian Harvey
1995-04-19 0:00 ` Robert Dewar
1995-04-20 0:00 ` Robin Rowe
1995-04-20 0:00 ` Robin Rowe
1995-04-20 0:00 ` Robert Dewar
1995-04-21 0:00 ` Robin Rowe
1995-04-21 0:00 ` Robert Dewar
1995-04-20 0:00 ` Robert Dewar
1995-04-20 0:00 ` Steve Tate
1995-04-20 0:00 ` Apology to Steve Robin Rowe
1995-04-21 0:00 ` Problems with proofs Larry Kahn
[not found] ` <3n1fsv$lgd@butch.lmsc.lockheed.com>
1995-04-20 0:00 ` Robin Rowe
1995-04-20 0:00 ` Garlington KE
[not found] ` <dewar.798093453@gnat>
1995-04-20 0:00 ` What good is halting prob? Max Hailperin
[not found] ` <3me1qs$n4a@theopolis.orl.mmc.com>
[not found] ` <3mevmu$8an@felix.seas.gwu.edu>
[not found] ` <3mh75i$8eu@rational.rational.com>
[not found] ` <3mjihr$iqq@felix.seas.gwu.edu>
[not found] ` <3mp20f$80t@kaiwan009.kaiwan.com>
1995-04-20 0:00 ` Academic CS Losers? Phillip Fanous
1995-04-21 0:00 ` Bill Winn
[not found] ` <cppD75t6F.47M@netcom.com>
[not found] ` <EACHUS.95Apr17172831@spectre.mitre.org>
[not found] ` <cppD77Ex6.E77@netcom.com>
[not found] ` <3mve9b$gaj@news.cais.com>
1995-04-18 0:00 ` What good is halting prob? Jay M Martin
1995-04-19 0:00 ` Steve Tate
1995-04-20 0:00 ` Jay M Martin
1995-04-21 0:00 ` Steve Tate
1995-04-21 0:00 ` Ray Toal
[not found] ` <cppD7880n.32B@netcom.com>
1995-04-19 0:00 ` Randolph Crawford
1995-04-19 0:00 ` Robert Dewar
1995-04-20 0:00 ` Robin Rowe
1995-04-20 0:00 ` Robert Dewar
1995-04-20 0:00 ` Robin Rowe
1995-04-21 0:00 ` Brian Hanson
1995-04-21 0:00 ` sxc [this message]
[not found] ` <dewar.798172270@gnat>
[not found] ` <cppD786FM.1u9@netcom.com>
[not found] ` <dewar.798207364@gnat>
[not found] ` <cppD78xMv.49w@netcom.com>
1995-04-19 0:00 ` Robb Nebbe
[not found] ` <3n0ka7$b57@hermes.unt.edu>
[not found] ` <dewar.798232482@gnat>
1995-04-19 0:00 ` Mark A Biggar
1995-04-19 0:00 ` Steve Tate
1995-04-19 0:00 ` Robert Dewar
1995-04-19 0:00 ` Mark A Biggar
1995-04-19 0:00 ` Richard Ladd Kirkham
1995-04-19 0:00 ` Robert Dewar
1995-04-20 0:00 ` Richard Ladd Kirkham
1995-04-20 0:00 ` Robert Dewar
1995-04-21 0:00 ` Mark A Biggar
1995-04-21 0:00 ` Robert I. Eachus
1995-04-21 0:00 ` Robert Dewar
replies disabled
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox