Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!mips!ptimtc!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: 5 May 91 21:01:38 GMT References: <30040@dime.cs.umass.edu> <1991May4.192440.5527@sctc.com> <17088@chaph.usc.edu> Sender: news@nas.nasa.gov Organization: NAS Program, NASA Ames Research Center, Moffett Field, CA Lines: 20 jeenglis@alcor.usc.edu (Joe English) writes: >I have to agree that the halting problem doesn't apply to >real computer programs, though. Many programs aren't >*supposed* to halt on every input (interactive processes, >network servers, etc.; these act like finite state transducers >and theoretically *should* be able to run forever.) What? You mean my text editor isn't supposed to exit when I'm done? (Well, an editor is an interactive process, isn't it?) "Input" refers to everything that is input into the process. Not individual lines, nor individual commands, everything. A FSM representing an editor will have a halting state. On the other hand, if the FSM lacks a "halting state", the solution is trivial. There is no "halting state" to reach, so of course it can't reach it. -- 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.'