An Introduction to Formal Languages and Automata, 7th Edition

12.5 A QUESTION OF EFFICIENCY

As long as we are concerned only with computability or decidability, it makes little difference what model of Turing machine we use. But when we start looking at possible practical concerns, such as ease of implementation or efficiency, significant distinctions appear quickly. Here are two examples that give us a first look at these issues.

EXAMPLE 12.7

In Example 9.7 we constructed a single-tape Turing machine for the language

$$L=\left\{a^n{b}^n:n\ge 1\right\}.$$

A look at that algorithm will show that for w = aⁿbⁿ it takes roughly 2n steps to match each a with the corresponding b. Therefore, the whole computation takes O(n²) moves.

But, as we later indicated in Example 10.1, with a two-tape machine we can use a different algorithm. ...