brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (11/21/90)
Skip if you saw Charles' error. In article <1990Nov20.143600.12451@dce.ie> ch@dce.ie (Charles Bryant) writes: > In a series of articles and replies, Dan Bernstein claims to have solved > the halting problem because he has an algorithm that will take a program P > and determine whether or not it halts using not more than twice the amount > of memory, and three times the time that running P would. No, that is not correct. ``At most three times as long as before P begins the second cycle of a loop'' is correct, and it is guaranteed finite. I do not claim to be the one who solved the halting problem for finite machines---in fact, all the relevant ideas can be traced back to Tarski. The technical details of applying the technique were well known by the sixties. Furthermore, it's inaccurate to call the method an ``algorithm.'' And ``not more than twice the amount of memory'' is incorrect. > Therefore I propse my optimised version: run P. Amusing, but incorrect, as there exist programs which do not terminate. ---Dan P.S. Any opinions on whether this is polite enough?