Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!hplabs!hpfcso!mjs
From: mjs@hpfcso.HP.COM (Marc Sabatella)
Newsgroups: comp.lang.misc
Subject: Re: Halting theory in practice (was Re: Array references cannot be made optimal)
Message-ID: <8960025@hpfcso.HP.COM>
Date: 16 Nov 90 19:12:06 GMT
References: <1990Nov15.101516.12198@cs.umu.se>
Organization: Hewlett-Packard, Fort Collins, CO, USA
Lines: 52

>Not long ago in this thread I remarked that the halting problem is
>solvable in practice. The response I got---from a computer scientist---
>was religious disbelief. It doesn't take much thought to apply theory to
>practice and put some reasonable bounds on the resources necessary to
>discover a loop---but computer scientists *don't do it*.

No, computer scientist object to your using the term "halting problem" to
described a reduced subset of the problem which was already known to be
solvable, using the phrase "in practice" to justify the corruption of the
problem.

Some analogies:

	Fermat's Last Theorem has been proven "in practice", where
	"in practice" is simply defined, conveniently, to mean for all "n"
	representable by an 8 bit two's complement integer.

Well, OK, this is probably true, but it hasn't proved the theorem itself, it
has just stated a rather obvious fact that happens to be subsumed by the
theorem.

	The four color theorem has been proven "in practice", where
	"in practice" is conveniently defined to mean "on all maps consisting
	solely of 2-inch square grids".

Big deal.  Same comment.

In fact, your "solution in practice" of the halting problem as well as my
examples really boils down to

	There are a finite number of integers "in practice", where
	"in practice" is conveniently defined to mean "integers between
	-0xffffffff and +0xffffffff.

Don't use the term "in practice" to corrupt the problem statement.

>Just undecidability. Of course, if you were to believe some of the
>people who argued with me in this group, you'd believe that sorting is
>not linear in the number of bytes being sorted

Again, no, no one disputes that, it is just that "number of bytes being
sorted" works out to a factor of #keys * log (#keys) whenever there is no
duplication of keys.

What you mean by your claims is true (well, I don't know about optimal adding
chains one way or the other); we take issue with your wording.

--------------
Marc Sabatella (marc@hpmonk.fc.hp.com)
Disclaimers:
	2 + 2 = 3, for suitably small values of 2
	Bill and Dave may not always agree with me