Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!jarthur!nntp-server.caltech.edu!mustang!data.nas.nasa.gov!sun418.nas.nasa.gov!truesdel From: truesdel@nas.nasa.gov (David A. Truesdell) Newsgroups: comp.lang.misc Subject: Re: Halting Problem Solved! Film at 11! (Was Re: definitions) Message-ID: Date: 6 May 91 06:10:10 GMT References: <333124@socrates.umd.edu> <30040@dime.cs.umass.edu> <1991May4.192440.5527@sctc.com> <30095@dime.cs.umass.edu> Sender: news@nas.nasa.gov Organization: NAS Program, NASA Ames Research Center, Moffett Field, CA Lines: 45 stephen@pesto.uchicago.edu (Stephen P Spackman) writes: >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. This is true in a theoretical sense, but in practical terms, it really doesn't make that much of a difference. Remember the number of possible states grows exponentially! >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. Nice idea, but you've missed something fundamental. A turing machine consists of a state machine AND its "tape". You need to account for the initial state of the tape as well. You could have a two state FSM (one is the halted state) which will run, not in an infinite loop, but as long as the tape "tells" it to. The only "easy" cases I know of are: No halted state, and no loops. Anything else can get really hard, really fast. Assuming that there IS an answer, which is not always the case. > 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". Indeed. -- T.T.F.N., dave truesdell (truesdel@nas.nasa.gov) 'And Ritchie said, "Let there be portability!" And nothing happened, so Ritchie realized that he had his work cut out for him.'