🚀 go-pugleaf

In article <ROCKWELL.91Jun22010647@socrates.umd.edu> rockwell@socrates.umd.edu (Raul Rockwell) writes:
> Dan Bernstein:
>    Don't be stupid. The analyzer will always halt, because the
>    original computer either enters a loop (in which case the analyzer
>    detects the loop) or itself halts (in which case the analyzer halts
>    too).
> Detecting loops on a machine with n states requires O(2^n) states in
> the analyzer.

This is the equivalent in computer ``science'' of an old wives' tale.

Would you like to prove it, Raul? Let me guess: You were taught in
computer science class that the halting problem could be solved for
n-state machines with a 2^n-state machine that simply kept track of
which states had been seen so far. *Therefore*, said your professor, the
halting problem was solvable for FSMs in theory, but not in practice.
How's that for a guess? ``This method for solving the problem takes
exponential time. Therefore the problem is not in P.''

Anyone who reads Knuth (which, I gather, has fallen out of favor among
computer scientists, as their students no longer know enough math to
understand the first two pages) will find out that to detect loops in a
sequence X_{n+1} = f(X_n), you do NOT need to store all previous X_k and
compare X_{n+1} to each in turn. All you need to do is generate X_n and
X_{2n} simultaneously, then compare the two. Can you prove this, Raul?
Can you figure out how to adapt it to make a practical solution to the
halting problem? Congratulations. Now what do you think of the statement
``Detecting loops on a machine with n states requires O(2^n) states in
the analyzer''?

---Dan