🚀 go-pugleaf

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