Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site wdl1.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!bellcore!decvax!decwrl!sun!wdl1!jbn
From: jbn@wdl1.UUCP
Newsgroups: net.ai
Subject: Re: Re: A halting problem
Message-ID: <951@wdl1.UUCP>
Date: Wed, 22-Jan-86 15:54:26 EST
Article-I.D.: wdl1.951
Posted: Wed Jan 22 15:54:26 1986
Date-Received: Fri, 24-Jan-86 21:33:42 EST
Sender: notes@wdl1.UUCP
Organization: Ford Aerospace, Western Development Laboratories
Lines: 24
Nf-ID: #R:kestrel:-410100:wdl1:91300001:000:1368
Nf-From: wdl1!jbn    Jan 22 12:53:00 1986


     First, it's always worth bearing in mind that the halting problem is
undecidable only for machines with infinite storage.  For machines with
finite memory, one must eventually either repeat a previous state or halt.
     There's a cute way to detect that a program in finite memory is in
a true infinite loop.  I got this from Scott Johnson, and I think that
it has actually been used in some system at Cornell used for teaching
elementary programming.  
     The approach is to use two copies of an interpreter, both running
the same program.  But one cycles twice for each cycle of the other.
At the end of each cycle, the states of the two interpreters are
compared.  (This can be done cheaply by maintaining a running checksum
of the interpreter's state with a commutative checksum algorithm; then,
as each variable changes, we subtract the old value from the checksum and
add the new value.  If the checksums of both interpreters match, we have to
compare the entire memories of both interpreters, but this doesn't happen
often.)  If the states of the two interpreters match, an infinite loop
has been detected.  There's a considerable overhead in doing all this;
it slows down the interpreter by a factor of 3 or so, but for small student
jobs in a batch environment it can be a win, since it kills the trivial looping 
programs very fast.

					John Nagle