🚀 go-pugleaf

In article <29254.Jun2219.22.4491@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
>
>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''?

Lighten up, Mr. Bernstein.  (As the inimitable J. Buffet says, "Don't
ever forget---you might end up being wrong.")  The technique you
describe is well known by most computer scientists, and great for
finding cycles in graphs.  It doesn't make a "practical solution" to
the halting problem because can take a long, long time to run.  Here's
a quick exercise---maybe a 10 in Knuth's rating system.  How many
steps can the above algorith run, as a function of the number of
bits of state?  Estimate how long the algorithm would take
to decide that the following program indeed halts:

    for i := 1 to 2^31 do
    	for j := 1 to 2^31 do
    	    for k := 1 to 2^31 do
    	    	;

Can a solution to the halting problem be said to be "practical" if it
takes millenia to terminate when applied to a simple program that uses
less than 12 bytes of state?

The loop detection algorithm might actually be handy once in a while,
to detect programs that get into tight loops that don't change the
state.  But don't you think that calling it a "practical solution to
the halting problem" is a tad overblown?

-mike