Path: utzoo!attcan!uunet!cs.utexas.edu!yale!cmcl2!kramden.acf.nyu.edu!brnstnd
From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: comp.lang.misc
Subject: Re: Array references cannot be made optimal
Message-ID: <13530:Nov1419:56:3790@kramden.acf.nyu.edu>
Date: 14 Nov 90 19:56:37 GMT
References: <11839@life.ai.mit.edu> <3975:Nov1323:25:4390@kramden.acf.nyu.edu> <1990Nov14.150535.25991@cs.umu.se>
Organization: IR
Lines: 46

In article <1990Nov14.150535.25991@cs.umu.se> christer@cs.umu.se (Christer Ericson) writes:
> In article <3975:Nov1323:25:4390@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
    [ on the practical solution to the halting problem ]
> You think this is new?

No, I don't. I think computer science (as opposed to real-world computer
programming) has regressed more than it has progressed in the last
twenty years.

In particular, modern computer scientists believe that the best known
sorting methods are asymptotically suboptimal. They believe the dogma
about the halting problem so firmly that they refuse to think through to
a practical solution. So when I remind people of what was widely known
in the sixties, I get attacked for my ``mathematical mistakes.''

> If a program, or rather a computer, is restricted to
> a finite number of states (which all modern computers are) then it's nothing
> more than a finite automaton and therefore the halting problem for these
> machines is solvable *in theory*.

Right. It's also solvable in practice.

> Practically, given the size of available
> memory on todays machines, for most problems I'd say it's not.

Are you trying to contribute to this discussion? In the article you're
responding to I gave quite precise estimates of the amount of work
necessary: twice as much memory for the variables you want to detect
cycling, and three times slower not counting housekeeping whenever those
variables are used. Now you express some vague opinion that this is not
practical, when obviously factors of two and three are the norm during
debugging.

> Also, the metod
> you described is nothing new, it's a commonly used metod to find cycles in
> iterative procedures

In fact, I didn't even bother to review the details of how to detect
loops in general, because any reader who doesn't understand can look up
the exercises in Knuth.

> Solving the halting problem for a Turing machine

We are talking about practical problems, not Turing machines.

---Dan