determine whether there are an equal number of a’s and b’s without repeated
back-and-forth movement of the read-write head.
Remember that the various models of Turing machines are considered
equivalent only with respect to their ability to do things, not with respect to ease
of programming or any other efficiency measure we might consider. We will
return to this important point in Chapter 14.
Multidimensional Turing Machines
A multidimensional Turing machine is one in which the tape can be viewed as
extending infinitely in more than one dimension. A diagram of a twodimensional Turing machine is shown in Figure 10.12.
Figure10.12
The formal definition of a two-dimensional Turing machine involves a
transition function δ of the form
δ : Q × Γ→ Q × Γ ×{L, R, U, D},
where U and D specify movement of the read-write head up and down,
respectively.
To simulate this machine on a standard Turing machine, we can use the twotrack model depicted in Figure 10.13. First, we associate an ordering or address
with the cells of the two-dimensional tape. This can be done in a number of