38 Chapter 1 Embedded Computing
cells, each of which contains a symbol. The tape can move back and forth under-
neath the head; the head can both read and write symbols on the tape. Because
the tape may be of infinite length, it can describe infinite-state computations. An
operating cycle of a Turing machine consists of the following
steps.
1. The machine uses the head to read the symbol in the tape cell underneath the
head.
2. The machine erases the symbol on the cell underneath the head.
3. The machine consults its program to determine what to do next. Based on
the current state and the symbol that was read, the machine may write a new
symbol and/or move the tape.
4. The machine changes its state as described by the program.
The Turing machine is a ...