Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!sdd.hp.com!news.cs.indiana.edu!rutgers!cmcl2!kramden.acf.nyu.edu!brnstnd From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein) Newsgroups: comp.lang.misc Subject: Re: Will this *thread* ever halt? Message-ID: <29254.Jun2219.22.4491@kramden.acf.nyu.edu> Date: 22 Jun 91 19:22:44 GMT References: <1991Jun18.172115.7185@clipper.ingr.com> <4457.Jun2021.35.1991@kramden.acf.nyu.edu> Organization: IR Lines: 31 In article 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