Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!yale!cmcl2!kramden.acf.nyu.edu!brnstnd
From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: comp.lang.misc
Subject: Re: Halting theory in practice (was Re: Array references cannot be made optimal)
Message-ID: <26926:Nov1920:08:5290@kramden.acf.nyu.edu>
Date: 19 Nov 90 20:08:52 GMT
References: <1990Nov15.101516.12198@cs.umu.se> <8960025@hpfcso.HP.COM>
Organization: IR
Lines: 27

In article <8960025@hpfcso.HP.COM> mjs@hpfcso.HP.COM (Marc Sabatella) writes:
  [ several analogies ]

Two differences: 1. The practical problems people want to solve go well
beyond the special cases dealt with in each of your analogies. 2. You
are not solving the theoretical problem stated, so you have no right to
call it a solution. The limits you introduced are entirely artificial.

On the theoretical side, the method I outlined *is* a solution to the
halting problem, because all machines are finite. On the practical side,
it detects a huge number (in my experience, practically every case) of
nonterminating programs in a reasonable time. Your analogies are neither
theoretically correct nor practically correct.

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

But it's silly to say ``sorting is k log k when the keys are distinct''
when you can make the much more precise statement ``sorting is linear
per byte in all cases.'' After all, when there are duplicate keys, the
former bound can be much worse than the latter.

---Dan