Show that the single-tape TMs that can not write on the portion the portion of the tape containing the input string recognize only regular languages.

The first part of the answer in a book said that:

We give a DFA $A$ that is equivalent to TM $M$. Design $A$ in two stages.

  1. We arrange the states and transitions of $A$ to simulate $M$ on the read-only input portion of the tape.

  2. We assign the accept states of $A$ to correspond to the action of $M$ on the read/write portion of the tapeto the right of the input.

Given below the whole answer (sorry for using pictures but the answer was so long and I do not understand it and I have not enough time to write it):

enter image description here enter image description here enter image description here

But I do not understand many points:

  1. Why the domain and the codomain of the defined function takes this form? and why only finitely many such functions exist as stated by the last line in the first paragraph?

  2. Why the author wrote $F_{\epsilon}$ as in the third paragraph? did he used the idea of epsilon transitions?

  3. The last paragraph in the solution I did not understand its idea at all?

Could anyone clarify the above questions for me please?

I saw an answer for the question here Single-tape Turing Machines with write-protected input recognize only Regular Languages but I did not understand it at all.


The general idea is that the TM has only finite memory while being in the input part of the tape. It can do arbitrary computations in the right part of the tape, but it can only observe a finite memory footprint of the input. It starts in the input part (on the left) and it can reenter the input part (from the right) arbitrarily often. But each time it enters the input part, the only thing that matters is the state it has when entering (or the fact that it starts from the left). And the only outcome of processing the (read-only) input part is the state it has when it exists (or the fact that it does not exit because it has accepted or rejected in the mean time).

1) That is already the reason for the domain and codomain. The domain is everything that matters about entering the input part, the codomain is everything that matters about exiting that part. Hence the function completely describes the behaviour of the TM on the input part. In a sense, the function contains everything the TM will ever find out about the word $s$.

Both domain and codomain are finite, hence so is the set of functions. Although the definition is about infinitely many words $s$, there will only be a finite number of different functions $F_s$.

2) $F_{\varepsilon}$ is not about $\varepsilon$-transitions. And it does not expand the previous definition. It is just the special case $s=\varepsilon$, that is the case of the empty input word. Or rather, the case of the empty prefix. After all, the paragraph where this appears is all about how $F_s$ can be computed incrementally along prefixes of $s$.

3) By now we have fully defined the automaton, except for acceptance. And the automaton state fully describes what the TM can do with the word we have read. We have not yet said anything about the part of the TM's computation that happens outside of the input word. The trick is that we do not have to delve into that computation. We just say that the state $F_s$ is accepting, if the word $s$ belongs to the TM's language. The paragraph has an explanation why that is well-defined.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.