Problem Solving in Automata, Languages, and Complexity

190 TURING MACHINES

Figure 4.15: A two-dimensional DTM.

tape head tape

head

( > a 00

Figure 4.16: Configuration change of Exercise 6(b).

(a) Describe how to represent the machine configuration of a two-

dimensional DTM. Use this notation to formally define the notion

of a function computed by a two-dimensional DTM.

(b) Design a two-dimensional DTM to change from its initial tape

configuration (a) to a new configuration (b), as shown in Figure

4.16.

(c) Show that a two-dimensional DTM can be simulated by a multi-

tape DTM. Therefore, all functions computed by two-dimensional

DTM’s are Turing-computable.

We say that a pushdown automaton is deterministic if for any configu-

ration, at most one instruction can be applied. Show that every deter-

ministic pushdown automaton can be simulated by a two-tape DTM.

(We will show in Section 4.7 that all context-free languages are Turing-

accept able .)