Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!spool.mu.edu!olivea!genie!udel!haven.umd.edu!socrates.umd.edu!socrates!rockwell From: rockwell@socrates.umd.edu (Raul Rockwell) Newsgroups: comp.lang.misc Subject: Re: Will this *thread* ever halt? Message-ID: Date: 23 Jun 91 16:34:39 GMT Article-I.D.: socrates.ROCKWELL.91Jun23113439 References: <1991Jun18.172115.7185@clipper.ingr.com> <4457.Jun2021.35.1991@kramden.acf.nyu.edu> <29254.Jun2219.22.4491@kramden.acf.nyu.edu> Sender: rockwell@socrates.umd.edu (Raul Rockwell) Organization: Traveller Lines: 20 In-Reply-To: brnstnd@kramden.acf.nyu.edu's message of 22 Jun 91 19: 22:44 GMT Dan Bernstein: 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''? Ok, so I need to buy myself a copy of Knuth... (again) There's still the minor problem that a machine with n bits has 2^n states... -- Raul