Figure10.11
It is important to keep in mind the following point. When we claim that a
Turing machine with multiple tapes is no more powerful than a standard one, we
are making a statement only about what can be done by these machines,
particularly, what languages can be accepted.
Example 10.1
Consider the language {a n b n }. In Example 9.7, we described a laborious method
by which this language can be accepted by a Turing machine with one tape.
Using a two-tape machine makes the job much easier. Assume that an initial
string a n b m is written on tape 1 at the beginning of the computation. We then
read all the a’s, copying them onto tape 2. When we reach the end of the a’s, we
match the b’s on tape 1 against the copied a’s on tape 2. This way, we can
It is important to keep in mind the following point. When we claim that a
Turing machine with multiple tapes is no more powerful than a standard one, we
are making a statement only about what can be done by these machines,
particularly, what languages can be accepted.
Example 10.1
Consider the language {a n b n }. In Example 9.7, we described a laborious method
by which this language can be accepted by a Turing machine with one tape.
Using a two-tape machine makes the job much easier. Assume that an initial
string a n b m is written on tape 1 at the beginning of the computation. We then
read all the a’s, copying them onto tape 2. When we reach the end of the a’s, we
match the b’s on tape 1 against the copied a’s on tape 2. This way, we can