Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!chaph.usc.edu!alcor.usc.edu!jeenglis
From: jeenglis@alcor.usc.edu (Joe English)
Newsgroups: comp.lang.misc
Subject: Re: Halting Problem Solved! Film at 11! (Was Re: definitions)
Message-ID: <17115@chaph.usc.edu>
Date: 6 May 91 08:01:41 GMT
References: <1991May4.192440.5527@sctc.com> <17088@chaph.usc.edu> <truesdel.673477298@sun418>
Sender: news@chaph.usc.edu
Organization: Free Roger Carasso!
Lines: 33
Nntp-Posting-Host: alcor.usc.edu

truesdel@nas.nasa.gov (David A. Truesdell) writes:
>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.

Yeah, but that doesn't mean that it has to _reach_ the halt
state.  There are an infinite number of strings that don't end
in 'q <RET>', and "ed" won't halt on any of them.[*]

The interesting question is not whether or not an editor
will halt on all inputs.  Looking at the problem
this way is like looking at Emacs as a finite state machine
accepting the regular expression ".*^X^C".  What's interesting
are questions like "If I invoke ESC-X towers-of-hanoi, will
it finish?"


[*] Actually, this isn't correct.  In an editor if you simply stop
    typing, it will "halt", but not in an "accepting state"
    (returning to the operating system).  


--Joe English

  jeenglis@alcor.usc.edu