6
$\begingroup$

Is $L=\{\langle M,w \rangle|M\text{ does not modify the tape on input w}\}$ decidable?

We could tell if a TM does not modify the tape on any input by checking if there are no transitions in $M$ that write on the tape, but can it be decided for a given $w$?

$\endgroup$
9
$\begingroup$

Yes, this is decidable. Here are two different proofs of that fact.

A counting proof

Define a configuration to be the state of the tape, the location of $M$'s head, the state that $M$'s finite control is in, and whether or not $M$ has written to the tape yet. Note that for a fixed $w$, if $M$ does not modify the tape on input $w$, there are only finitely many possible configurations, let's say $N$ of them. $N$ can be easily computed; it is about $2 \times (\text{len}(w) + 2|M|) \times |M|$ where $|M|$ is the number of states in $M$'s finite control. (See footnote *.)

So, run $M$ on input $w$ and keep track of all the configurations it enters. One of three things must happen:

  • After at most $N$ steps, $M$ modifies the tape. In that case you know $\langle M,w \rangle \notin L$ and there's no need to keep simulating $M$.

  • After at most $N$ steps, $M$ halts without ever modifying the tape. In that case you know $\langle M,w \rangle \in L$ and there's no need to keep simulating $M$.

  • After at most $N$ steps, $M$ repeats some prior configuration without ever modifying the tape and thus enters a cycle. In that case you know $M$ will loop forever on input $w$, without modifying the tape, so $\langle M,w \rangle \in L$ and there's no need to keep simulating $M$.

Thus, after simulating $M$ for $N$ steps, we learn whether $M$ will ever modify the tape on input $w$.

Footnote *: In this proof I will consider as equivalent all configurations where the head is more than $|M|$ cells to the right of the input and that differ only in the location of $M$'s head, and I consider as equivalent all configurations where the head is more than $|M|$ cells to the left of the input and that differ only in the location of $M$'s head. Why? If it ever reaches one of those configurations without modifying the tape, then it will loop forever without modifying the tape. This follows by a pigeonhole argument; the finite control can't count higher than $|M|$, i.e., if it reaches one of those configurations, then some state of the finite control must have repeated during the time when it's wholly to the right/left of the input, so it has entered a loop.

A conceptual proof

For a given $w$, if $M$ doesn't write to the tape, it is equivalent to a two-way deterministic finite automaton (2DFA). So, you can write down a 2DFA with the following three properties:

  1. The DFA has a single accepting state $q_a$, with a self-loop (once it accepts, it stays accepting forever). All other states are non-accepting.

  2. If $M$ never writes to the tape on input $w$, the behavior of the 2DFA on input $w$ is equivalent to the behavior of $M$, and the 2DFA never transitions to the special accept state $q_a$ and never accepts.

  3. If $M$ does write to the tape on input $w$ at some point, the behavior of the 2DFA is equivalent up until the point $M$ first writes to the tape; thereafter the 2DFA follows a transition to the special accept state $q_a$ and thus accepts.

How do we build such a 2DFA? The 2DFA is just a copy of the finite control of $M$ (which is a finite automaton), except that it moves to $q_a$ whenever $M$'s finite control would modify the tape:

  • If $M$'s finite control has a transition $q_i \to q_j$ when symbol $i$ is under the head $i$ and this transition doesn't write anything, then the 2DFA has the same transition.

  • If $M$'s finite control has a transition $q_i \to q_j$ when symbol $i$ is under the head $i$ and this transition does write to the tape, the 2DFA has a transition $q_i \to q_a$ on symbol $i$.

Now the question just becomes: given a 2DFA, does it accept on input $w$? This is decidable, as every 2DFA is equivalent to a (possibly exponentially larger) ordinary DFA.

Comparison of proofs

Either proof suffices to show that $L$ is decidable. The counting proof has the advantage of not requiring fancy machinery like 2DFA. The conceptual proof shows both that $L$ is decidable and something stronger: if we restrict attention to a single fixed $M$, then the set of $w$ such that $\langle M,w \rangle \in L$ is in fact a regular language (since 2DFA are equivalent in power to DFAs). Pretty nifty!

$\endgroup$
  • $\begingroup$ I see. The key is that the set of computations that lead to the first write is regular. Thanks! $\endgroup$ – Raphael Dec 13 '16 at 13:31
  • 1
    $\begingroup$ What if a TM keeps moving the tape head to the right without ever modifying the contents of the tape? Then the TM will never enter the same configuration twice, but will still loop forever. How would we know that this TM should be accepted using the first approach you described? $\endgroup$ – user1354784 Dec 14 '16 at 18:21
  • $\begingroup$ @user1354784, good point. I overlooked that. See edited answer and Footnote *. Does it look right now? $\endgroup$ – D.W. Dec 14 '16 at 18:52

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.