An Introduction to Formal Languages and Automata, 7th Edition

10.2 TURING MACHINES WITH MORE COMPLEX STORAGE

The storage device of a standard Turing machine is so simple that one might think it possible to gain power by using more complicated storage devices. But this is not the case, as we now illustrate with two examples.

Multitape Turing Machines

A multitape Turing machine is a Turing machine with several tapes, each with its own independently controlled read-write head (Figure 10.8).

The formal definition of a multitape Turing machine goes beyond Definition 9.1, since it requires a modified transition function. Typically, we define an n-tape machine by M = (Q,Σ, Γ, δ, q₀, □, F), where Q,Σ, Γ, q₀, F are as in Definition 9.1, but where

$$\delta :Q\times {\Gamma }^n\to Q\times {\Gamma }^n\times {\left\{L,R\right\}}^n\%$$

FIGURE 10.8

FIGURE 10.9

specifies ...