Mr. Turing’s amazing machines - The Computing Universe: A Journey through a Revolution - page 116

the machine if this is the symbol that is read. The symbol on the arc indicates what the head overwrites in
the box. Thus reading a 0 from the state Q 0 = Even just takes us to the same state: reading a 1, takes us to
the other circle corresponding to Q 1 = Odd. We have also indicated the start and the halt conditions in the
diagram.
Similar diagrams are used to describe the behavior of “Finite State Machines” or FSMs that are often
used to summarize the behavior of devices whose actions depend not just on the current input but also on
the previous inputs. The FSM has enough memory to store a summary of a finite number of past inputs. A
combination lock is an example of an FSM. The lock cannot remember all the numbers dialed into the lock
but it remembers enough to know whether the would-be user has entered the correct small sequence of
numbers to open the lock. A Turing machine is just an FSM with an infinitely long tape that serves the same
function as memory in a computer.
We can now go on to construct Turing machines for adding, multiplying, copying, and so on. To build
up more complex machines it is convenient to reuse these simpler machines as components of the complex
machine, rather like subroutines in a software program. This greatly simplifies the construction of such
machines.