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

computabilitycomputational complexityformal-languagesturing-machines

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

enter image description here
enter image description here

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?

Best Answer

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.

  1. 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.

  1. 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$.

Related Question