Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!samsung!think.com!snorkelwacker!ai-lab!ai.mit.edu!misha
From: misha@ai.mit.edu (Mike Bolotski)
Newsgroups: comp.lang.misc
Subject: Re: Array references cannot be made optimal
Message-ID: <11839@life.ai.mit.edu>
Date: 13 Nov 90 14:19:10 GMT
References: <5079@lanl.gov> <7659:Nov620:58:5990@kramden.acf.nyu.edu> <MISHA.90Nov7191750@just-right.ai.mit.edu> <23904:Nov905:22:5290@kramden.acf.nyu.edu>
Sender: news@ai.mit.edu
Reply-To: misha@ai.mit.edu
Organization: MIT Artificial Intelligence Laboratory
Lines: 76

In article <23904:Nov905:22:5290@kramden.acf.nyu.edu>, brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
|> In article <MISHA.90Nov7191750@just-right.ai.mit.edu> I write:
|> > In article <7659:Nov620:58:5990@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
|> > > pointers (arrays) are pre-indexed appropriately. Could one of you CS
|> > > types please illustrate to Jim that finding optimal addition chains in a
|> > > general computation is equivalent to solving the halting problem?
|> > Bzzt.  But thanks for playing, Dan.
|> > Optimal addition is NP.
|> 
|> Bzzt. But thanks for playing, Mike.
|> 
|> Finding optimal addition chains in a general computation is most
|> certainly equivalent to the halting problem. Since no CS types have
|> stepped forward, I'll illustrate.

Consulting that a standard reference text in the field, "Compilers:
Principles, Techniques and Tools", by Aho, Sethi, and Ullman 
reveals the following on page 517.

"Finding an optimal assignment of registers to variables is difficult,
 even with single-register values. Mathematically, the problem is
 NP-complete."

Now this is register assignment, not evaluation order, but Dan's 
"outline of proof"  switched the problem to allocation of address
register.  But not to despair:

"The order in which computations are performed can affect the 
 efficiency of the target code. [..] Picking a best order is
 another difficult, NP-complete problem." (p 518).

|> Outline of proof: Take a program. Add an array[2], x. Read x[0] and x[1]
|> from the outside. Use x[0]. In a subroutine, use x[1] repeatedly and
|> then exit. Replace every exit with a call to the subroutine.
|> 
|> Now if the program does not exit, it is best to keep &x[1] around. If
|> the program exits, it is best to keep only &x[0] around. Q.E.D.

The above is not a proof. It is not even close to a proof. In fact,
I suspect you have the common misconception that the halting problem
consists of determining whether a particular program will ever halt
or not.  I suggest you consult a standard theory of computation 
text, such as Hopcroft and Ullman for a definition, and examine
what a proof by reduction to a Ktm looks like.

[ Timer description deleted due to irrelevance ].

|> Q.E.D.

Right.

|> Indeed. (As a matter of fact, it's quite feasible to solve the halting
|> problem in practice---the algorithm just depends on the program.)

If this statement was made with full knowledge of what the halting
problem is, it would have been a wonderful .sig quote. 


Excerpted from another article by Dan, replying to Jim Giles:

|> I simply don't understand where you and Mike are getting this ridiculous
|> assertions from. What problems are you fantasizing you've solved here?
|> Where are your purported proofs?

The louder you yell your mistakes, Dan, the more embarassing they become.
Especially since you are venturing out of the safe realm of opinion and 
dealing with facts that can be proven mathematically. 

-- 
Mike Bolotski          Artificial Intelligence Laboratory, MIT
misha@ai.mit.edu       Cambridge, MA

Okay, just this once: 

"It's quite feasible to solve the halting problem in practice."
  -- Dan Bernstein