Question

Prove that a single-tape Turing Machine that is not allowed to write on the input portion of the tape can only recognize regular languages.

Answer 1

Ans:

Let M = (Q, Σ, Γ, q₀, q_accept, q_reject) be a single-tape TM that cannot write on the input portion of the tape. A typical case when M works on an input string x is as follows: the tape head will stay in the input portion for some time, and then enter the non-input portion (i.e., the portion of the tape on the right of the |x|^th cells) and stay there for some time, then go back to the input portion, and stay there for some time, and then enter the non-input portion, and so on. We call the event that the tape head switches from input portion to non-input portion an out event, and the event that the tape head switches from non-input portion to input-portion an in event.

Let first_x denote the state that M is in just after its first “out” event (i.e., the state of M when it first enters the non-input portion). In case M never enters the non-input portion, we assign first_x = q_accept if M accepts x, and assign first_x = q_reject if M does not accept x. Next, we define a characteristic function f_x such that for any q ∈ Q, f_x(q) = q' implies that if M is at state q and about to perform an “in” event, the next “out” event will change M in state q' ; in case M never enters the non-input portion again, we assign f_x(q) = q_accept if M enters the accept state inside the input portion, and qreject otherwise.

It is easy to check that if for two strings x and y, if first_x = first_y and for all q, f_x(q) = f_y(q), we have x and y are indistinguishable by M. (That is, M accepts xz if and only if M accepts yz.) As there are finite choices of first_x and f_x (precisely, |Q|^|Q|+1 such choices), the number of distinguishable strings are finite. By Myhill-Nerode theorem, the language recognized by M is regular.