Article View: comp.lang.misc
Article #4171Re: Will this *thread* ever halt?
From: Raul Rockwell
Date: Sat, 22 Jun 1991 06:06
Date: Sat, 22 Jun 1991 06:06
12 lines
1148 bytes
1148 bytes
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. Except for trivial cases, this is far more than n+n states. -- Raul <rockwell@socrates.umd.edu>
Technical Details
Message-ID:
<ROCKWELL.91Jun22010647@socrates.umd.edu>Path:
arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!ncar!gatech!udel!haven.umd.edu!socrates.umd.edu!socrates!rockwellReferences:
<1991Jun12.194212.21395@clipper.ingr.com> <10452.Jun1317.26.4791@kramden.acf.nyu.edu> <1991Jun18.172115.7185@clipper.ingr.com> <4457.Jun2021.35.1991@kramden.acf.nyu.edu>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!ncar!gatech!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.91Jun22010647@socrates.umd.edu> Date: 22 Jun 91 06:06:47 GMT References: <1991Jun12.194212.21395@clipper.ingr.com> <10452.Jun1317.26.4791@kramden.acf.nyu.edu> <1991Jun18.172115.7185@clipper.ingr.com> <4457.Jun2021.35.1991@kramden.acf.nyu.edu> Sender: rockwell@socrates.umd.edu (Raul Rockwell) Organization: Traveller Lines: 12 In-Reply-To: brnstnd@kramden.acf.nyu.edu's message of 20 Jun 91 21: 35:19 GMT