🚀 go-pugleaf

David Gudeman:
   By the way, the term "Turing machine" refers to a specific
   architecture, and does not describe all machines with infinite
   state spaces.  ...  A Turing machine has an infinite read-write
   tape with a movable head and only four possible actions (as I
   recall).  There are very few applications where it is useful to
   model a computer as a TM -- infinite or not.

Except that each "cell" on a turing machine tape represents a FSM of
arbitrary complexity.  The "four actions" of a TM are:

(1) do a state transition in the FSM
(2) move to the FSM on the left
(3) move to the FSM on the right
(4) "halt" or "suspend" (transition to an undefined state)

So any FSM is a restricted case of a turing machine, and turing
machines are trivially useful for anything that a FSM is useful for.

Often when people speak of turing machines, they think of one where
every FSM has only two states, and numbers are implemented as strings
of ones.  This particular instance of a turing machine is quite a bit
more limited than turing machines in general.

And while the basic definition of a turing machine only has rules for
a transition to an adjacent FSM you can usually make transitions to
FSMs located arbitrary distances away (as long as the states of the
intervening FSMs are known).  Note that you don't have to enumerate
the states and transitions, as long as each FSM is finite.

The way I understand it, the only kind of machine with an infinite
state space that can't be modeled by a TM is one with non-denumerable
state state space.

Raul Rockwell