Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!elroy.jpl.nasa.gov!ncar!midway!midway!stephen From: stephen@pesto.uchicago.edu (Stephen P Spackman) Newsgroups: comp.lang.misc Subject: Re: Halting Problem Solved! Film at 11! (Was Re: definitions) Message-ID: Date: 6 May 91 05:56:03 GMT References: <333124@socrates.umd.edu> <30040@dime.cs.umass.edu> <1991May4.192440.5527@sctc.com> <30095@dime.cs.umass.edu> Sender: news@midway.uchicago.edu (NewsMistress) Organization: University of Chicago CILS Lines: 30 In-Reply-To: truesdel@nas.nasa.gov's message of 6 May 91 01: 57:22 GMT This thread is getting me down, because intelligent people are making fools of themselves. So now I'm going to have another go at making a fool of MYself. :-) I think the observation here is that actual computers are NOT (equivalent to) turing machines BECAUSE they have finite resources. Note that it doesn't matter WHAT the bound on resources is; so long as it is there, and has some value in each case, the theoretical observation that this is NOT REALLY a turing machine holds. So the question is, *can we get any mileage out of that*? What useful theorems could we prove if we were to grant (or assume, if it makes you feel better - maybe your computer is A LOT bigger than mine :-) that there IS SOME upper bound on machine state complexity? Now, I don't do theory, and I haven't spent a lot of time worrying about the structure of the appropriate theorems (though it does seem pretty obvious that a FINITE computer has an easy check for programme termination: wait until it has run enough cycles to be in EVERY state. By this point it has either halted or it is in an infinite loop, by a pigeonhole argument. It's not PRACTICAL, of course, but that doesn't mean it has no practical CONSEQUENCES); but it doesn't seem at all incoherent that it MIGHT be very important. And it certainly means there's room for different perspectives on what's "possible". ---------------------------------------------------------------------- stephen p spackman Center for Information and Language Studies systems analyst University of Chicago ----------------------------------------------------------------------