brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (11/09/90)
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