Problem Solving in Automata, Languages, and Complexity

Let us define such a machine more precisely: An infinite-tape DTM A& =
(Q, C, I’., 6, s) has finitely many states and infinitely many tapes. Its transition
function 6 is a function from Q x I’+ to (Q U {h}) x I? x {L, R, S}? An
instruction of the form

b(q, ae2.e l ak) = (p, blb2 l l l b,, D1D2 l l + Dn)

means that if M is in state q, and the tape heads of the first k: tapes are

reading symbols al, ~2, l. l , ak, respectively, and the other tape heads are

reading B, then &! changes the state to p, replaces the symbols scanned by

the first m tape heads by bl, b2, l l l , b,, respectively, and moves the first n

tape heads in the directions D1, 02, l l 0, D,, respectively.

Example 4.14 Prove that for any language A C - (O+l)*, there is an infinite-

tape LIT’M M that accepts L.

Proof. We note that the domain of the transition function 6 is infinite; that
is, 6 may contain an infinite number of instructions. Thus, we can simply use
one set of instructions to deal with one particular input. First, we copy the
ith symbol xi of input to the (1x1- i + 2)nd tape. Then, in a single move, we
read all symbols of the input and decide to accept it or not. More precisely,
the transition function S for the machine M for A is defined as follows:

J(% B) = (P, 8 L),

&vl’**ak) = (p,Bal-a&), for allal,...,ak EC,

d(p, Bal l l oak> = (h, Bk+‘, S), if ak l l +a2a1 E A,

where p is a state other than the initial state s and the final state h. cl

Exercises 4.3

1. Describe the details of the last part of the one-tape DTM A&’ of Theorem
   4.11 which simulates a two-way DTM A& That is, show the instructions
   of &P that restore the output from the two-track form to the one-track
   form. For instance, it should change the tape configuration

to the configuration BaBabbabB, and change the tape configuration

a

to the configuration BabbB -*