and that of the eraser E will be
The result is a single Turing machine that combines the action of C,A, and E as
indicated in Figure 9.8.
Another useful, high-level viewof Turing machines involves pseudocode. In
computer programming, pseudocode is a way of outlining a computation using
descriptive phrases whose meaning we claim to understand. While this
description is not usable on the computer, we assume that we can translate it into
the appropriate language when needed. One simple kind of pseudocode is
exemplified by the idea of a macroinstruction, which is a single-statement
shorthand for a sequence of lower-level statements. We first define the
macroinstruction in terms of the lower-level language. We then use the
macroinstruction in a program with the assumption that the relevant low-level
code is substituted for each occurrence of the macroinstruction. This idea is very
useful in Turing machine programming.
Example 9.13
Consider the macroinstruction
if a then q j else q k ,
with the following interpretation. If the Turing machine reads an a, then
regardless of its current state, it is to go into state q j without changing the tape
content or moving the read-write head. If the symbol read is not an a, the
machine is to go into state q k without changing anything.
To implement this macroinstruction requires several relatively obvious steps
of a Turing machine.