Path: 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: 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 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