Show that single-tape TMs that cannot write on the portion of the tape containing the input string recognizes only regular languages.

Question

The question and its answer is given in the following pictures:

But I do not know why he named the function he used as a characteristic function?and the intuition behind the definition the author gave to it is not clear for me? could anyone explain this for me please?

Answer 1

I agree that this can be a puzzling way to explain the situation. The point of this proof is to say:

• Because of the read-only restriction, it turns out a TM with a read-only tape has a finite list of features it can learn about its input. (I'll explain what these features are later.)
• Once you know those features, you know everything the TM can know about the input.
• Evidently, $M$ treats strings with the same feature-list in the same way. It can't tell them apart. If $x$ and $y$ are two strings with the same features, and $z$ is any other string, then $M$ treats $xz$ and $yz$ the same way (both accept or both reject).
• In fact, both $xz$ and $yz$ have the same feature-list.
• So, the corresponding DFA looks like this: the states correspond to the different feature-lists that words can have. The transition rule is like this: if you're on state $q$, that's a particular feature-list. Let $w$ be a word with that feature-list. On input $a$, go to the feature list for word $wa$. Because of the property in the previous bullet-point, this feature-list is well-defined.

Details follow.

---

1. The main point is that a TM with a read-only input is "very forgetful". A Turing Machine has two ways to remember: the state of its deterministic control, and whatever information it writes onto the tape.

2. Let's ask: when the TM moves from the input region into the writeable region, what information does it retain about the input string $x$? Because the TM can't write anything down, the only information it retains is whatever state it's currently in as it exits the read-only region. $M$ can write down that state onto the tape. $M$ doesn't remember anything else about the input (!).

3. Later, $M$ might go back into the read-only region. As before, whatever it does in that region, its only memory upon exiting will be whatever state $q^\prime$ it's finally in. (Note that it can't even reference its notes while it's in the read-only region.) $M$ doesn't remember anything else about the input.

4. This is the way that $M$ can extract information about the input: it dives into the read-only region, changes its state purely based on the input characters (it can't reference its written notes), then emerges in a particular state. It can write down that state; that state is the only memory it has about the input.

5. Because $M$ can't reference its written notes, there's an unchanging functional relationship $f(x,q)=q^\prime$: If $M$ enters the read-only region while in state $q$, and the read-only region has input $x$ in it, then $M$ will always exit the read-only region (or terminate within the read-only region) in state $q^\prime$. This function never changes because $M$ can never change the input, and its only instruction for what to do there comes from $x$ and $q$. This function doesn't care what $M$ has written on the tape because $M$ can't reference it when on the read-only section.

6. Hence for each input $x$, you can fill out a table like this: $$\begin{array}{r|l}\text{state when entering read-only} & \text{state when exiting} \\\hline q_1\\q_2\\q_3\\\vdots\\q_n\end{array}$$

Fill out the right-hand column by listing different states. If $M$ never exits the region, what should you write? Because the machine never leaves, it either accepts or halts. As a default answer, put $q_{accept}$ or $q_{reject}$ accordingly.

Add a final row for what happens at the very beginning when the TM starts in the read-only region (see point 2 above). Now the table contains all of the information about the string that $M$ is able to remember. It contains all of the information about the string that $M$ can write down on its writeable tape.

7. This table characterizes the complete behavior of $M$ on the input $x$. This table contains everything $M$ can ever learn about its input. Even what $M$ writes down on the writeable tape is fully determined by this table. Whether $M$ accepts or rejects is also determined by this table.

In particular, we have the following extension property: if $x$ and $y$ have the same table, then for any string $z$, $xz$ and $yz$ have the same table. ($M$ has no way to tell $x$ and $y$ apart, so it has no further way to tell $xz$ and $yz$ apart, so it behaves identically on both.) By the Myhill-Nerode theorem, the language of $M$ must be regular.

8. More concretely, if $M$'s behavior on $x$ is completely determined by the table for $x$, and if $xz$ and $yz$ always have the same table whenever $x$ and $y$ do, we can make a DFA for $M$ like this:

Let the states of the DFA correspond to these different possible tables (there are $|Q|^{|Q|+1}$ different possible tables. This is because there are $|Q|+1$ rows in the table, and any state in $Q$ can be an entry in the right column.) The starting state is the table for the empty word. The transition rule is well-defined because extensions $xz=yz$ of words with the same table have the same table. The accept and reject states are well-defined because you can tell whether $M$ will accept or reject the word $x$ based on the table for $x$.