Python for philosophers

[Steven D'Aprano]

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