Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!emory!gatech!udel!haven.umd.edu!socrates.umd.edu!socrates!rockwell From: rockwell@socrates.umd.edu (Raul Rockwell) Newsgroups: comp.lang.misc Subject: Re: Halting Problem Solved! Film at 11! (Was Re: definitions) Message-ID: Date: 15 May 91 02:06:55 GMT References: <1991May14.054813.18427@sbcs.sunysb.edu> <30514@dime.cs.umass.edu> Sender: rockwell@socrates.umd.edu (Raul Rockwell) Organization: Traveller Lines: 47 In-Reply-To: yodaiken@chelm.cs.umass.edu's message of 14 May 91 15: 55:13 GMT Victor Yodaiken: The kind of looping that makes Turing machines undecidable is quite different from the kind of looping we get in real machines. On a turing machine while(true)i = i+1; is a truly infinite loop, each iteration takes us to a new state. But on a real computer, while(true)i = i+1; *will* repeat state (or crash the program). Here we have a *finite* loop. er.. I hate to say this, but (brought to you through sheer brute effort): Assuming I agree with you, so what? First off, a loop of the form while(true) i=i+1 implemented on a turing machine is NOT what make the turing machine undecidable. (In fact, it is trivial to determine if that loop halts: if the machine is using arbitrary precision arithmetic, it won't halt. if the machine is using a finite state arithmetic it will or won't halt depending on how the overflow condition is defined). What makes turing machines undecidable (to gloss over all the details) is that you can write programs of arbitrary complexity. (NOTE: not infinite complexity, arbitrary complexity -- circularly defined for the purposes of this article as complexity sufficient to be undecidable that some program H can not determine if this complex program halts.) Second off, all I said was that unbounded loops and recursion must be eliminated. I carefully did not describe any specific mechanism for doing so. If your recognizer can determine that while(true) i=i+1 will halt on your system, then it is fine to include it. The key here is to eliminate any ambiguous cases. A simple example of which is while(true) i = f(i) :-). Personally though, I wouldn't bother considering this case as a halting case (why bother)? Anyways, if your point is that for a finite state machine with n states, a table with n entries is going to be able to list whether each state halts, I understand the concept. Or, if your point was that a binary machine capable of representing at most n bits of information has at most 2^n states, then yes I understand that too. Thank you for pointing it out. Raul Rockwell