patternMinor
Is it decidable whether a Turing machine modifies the tape, on a particular input?
Viewed 0 times
theinputdecidabletapemodifiesmachineturingparticularwhether
Problem
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$?
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$?
Solution
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:
-
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.
-
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.
-
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!
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:
-
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.
-
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.
-
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!
Context
StackExchange Computer Science Q#67259, answer score: 9
Revisions (0)
No revisions yet.