Newsgroups: comp.lang.misc
Path: utzoo!utgpu!watserv1!tolstoy.waterloo.edu!mhcoffin
From: mhcoffin@tolstoy.waterloo.edu (Michael Coffin)
Subject: Re: Will this *thread* ever halt?
Message-ID: <1991Jun22.213750.18954@watserv1.waterloo.edu>
Sender: news@watserv1.waterloo.edu
Organization: University of Waterloo
References: <4457.Jun2021.35.1991@kramden.acf.nyu.edu> <ROCKWELL.91Jun22010647@socrates.umd.edu> <29254.Jun2219.22.4491@kramden.acf.nyu.edu>
Date: Sat, 22 Jun 1991 21:37:50 GMT
Lines: 41

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