Python for philosophers
Steven D'Aprano
steve+comp.lang.python at pearwood.info
Sun May 12 22:41:35 EDT 2013
On Mon, 13 May 2013 12:34:13 +1200, Gregory Ewing wrote:
> In the most general terms, the Python interpeter (or any other computer
> system, for that matter) can be thought of as something with an internal
> state, and a transition function that takes the state together with some
> input and produces another state together with some output:
>
> F(S1, I) --> (S2, O)
>
> (Computer scientists call this a "finite state machine", because there
> is a limited number of possible internal states -- the computer only has
> so much RAM, disk space, etc.)
That's not what finite state machine means. A finite state machine
doesn't refer to the number of physical states of the underlying hardware
implementing the device, it refers to the number of external states of
the computation being performed. For example, a traffic light may be
modelled by a Finite State Machine with three states: Red, Amber, Green.
It may actually be implemented by a general purpose computer with
trillions of internal states, or by a specialised electrical circuit, or
by clockwork. The implementation doesn't matter. What matters is the
three external states, any input to the device, plus the transition rules
between them.
Python is not well-modelled as a Finite State Machine. Python is
equivalent in computing power to a Turing Machine, while Finite State
Machines are much weaker, so there are things that Python can do that a
FSM cannot.
--
Steven
More information about the Python-list
mailing list