🚀 go-pugleaf

RWALLACE@vax1.tcd.ie writes:
>                                        As someone pointed out, a real
>computer isn't a finite state machine because it includes the person
>operating it

A human being may or may not be a finite state machine, but the
effect he he has on a computer system is merely to add a finite
number of transitions to the computer. (Striking one of the finite
number of keys changes the interrupt state on a PC, putting in
a new disk changes many of the bits on that mass storage device).

You can't model exactly which inputs the human will provide, but
you can reason about behavior under any possible set of inputs.
In effect, a person at a computer is running a huge finite
automata through an input string consisting of his actions.

Take the initial state to be one of the finite number of
states which represents the introduction of the virus into
the system.  Mark the finite number of states which represent
"infection" as final states.  The question: "can infection occur"
is merely the question "does this FA have a nonempty language."
That question can be settled in finite time by testing the FA
on every input string of length less than or equal to the number
of states in the FA.  Do this once for every initial "infection"
state, and the result follows. :-)

You may need to add a few more states to better model
the input devices and the clock.

>(well the whole universe has a finite number of states
>but we're getting way beyond anything of practical use).

Yep.

                            Greg Fife
                            gnf3e@virginia.edu , virginia.bitnet
                            uunet!virginia!uvacs!gnf3e