Article View: comp.lang.misc
Article #4177Re: Will this *thread* ever halt?
From: Raul Rockwell
Date: Sun, 23 Jun 1991 16:34
Date: Sun, 23 Jun 1991 16:34
20 lines
1653 bytes
1653 bytes
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 <rockwell@socrates.umd.edu>
Technical Details
Message-ID:
<ROCKWELL.91Jun23113439@socrates.umd.edu>Path:
arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!spool.mu.edu!olivea!genie!udel!haven.umd.edu!socrates.umd.edu!socrates!rockwellReferences:
<1991Jun18.172115.7185@clipper.ingr.com> <4457.Jun2021.35.1991@kramden.acf.nyu.edu> <ROCKWELL.91Jun22010647@socrates.umd.edu> <29254.Jun2219.22.4491@kramden.acf.nyu.edu>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!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: <ROCKWELL.91Jun23113439@socrates.umd.edu> 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> <ROCKWELL.91Jun22010647@socrates.umd.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