🚀 go-pugleaf

In article <MISHA.90Nov7191750@just-right.ai.mit.edu> misha@ai.mit.edu (Mike Bolotski) writes:
> 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.

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.

You may object that you were thinking about algorithms, not
computational methods: the program *must* exit.

Okay, no problem. Add a timer to the program. (I.e., increment a counter
once every so many steps, where each step takes bounded time.) Only call
the subroutine if the timer is even. It is known that an algorithm to
determine the parity of the final result of such a counter for any
program is equivalent to an algorithm for solving the halting problem.
(In fact, much more general statements are true, but this is enough.)
Q.E.D.

> You can argue practicality, but not theory.

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

---Dan