A Turing machine with each cell accessed at most $10$ times has an equivalent NFA

Question

I am confused by the following claim:

Let $T$ be a (decider, single-tape) Turing machine with the property that for every input, every cell on its tape is accessed at most $10$ times. Then there is a (nondeterministic) finite automaton equivalent to $T$.

The assumption says that there are only finitely many possible crossing sequences, i.e. the sequence of internal states that the machine has at a given cell on a given input. The text says the proof is "just have enough states to remember the current crossing sequence and update that information as each successive input symbol is read."

I do not understand this construction at all. For example, to remember the crossing sequence at a given cell we need to keep track of the contents of the entire tape, and does the nondeterminism come in somehow when deciding on which cell to "track"?

The text is part of Sipser's solution manual, problem 7.20 or 7.49 depending on the edition. One idea I played with is to have a state of the NFA for every crossing sequence and move non-deterministically from it to every possible next sequence.

Answer 1

Here is a solution based on crossing sequences:

To begin with, assume w.l.o.g that the machine moves to the right end of the input before halting -- this may make the number of times the machine crosses a cell at most 11, but it does not matter as long as it is a constant. Assume also that the machine scans the input to the right end of the input and back to the left most cell before it begins its computation.

Consider an input word $xz$. We need to investigate the amount of information the machine can carry across the boundary between $x$ and $z$; That is, the information across the tape-cells $|x|$ and $|x|+1$. By the assumption, the machine can cross the boundary at most 10 times.

Now assume that we cross the boundary and enter $x$ from the right, and let $q_{in}$ be the state that we move to upon entering the cell $|x|$. As the machine is deterministic, and we cross the boundary again in the future from left to right, then there is a unique state $q_{out}$ that we enter upon reaching the cell $|x|+1$ for the next time. That is, $q_{out}$ is a function of $q_{in}$ and $x$. Note that as the machine can change the tape's content, then once we are in $q_{out}$, it could be the case that we have replaced $x$ with some other word $x'$, yet we can still determine the next state $q'_{out}$ as a function of $x'$ and $q'_{in}$, where $q'_{in}$ is the state we enter when we cross the boundary again from right to left when $x'$ is written, and $q'_{out}$ is the state that we next move to when we cross the boundary left to right. The latter scenario repeats at most 10 times. So we have the following outcome:

$ \pi_{x} = (x_1, q^1_{in}, q^1_{out}, x_2, q^2_{in}, q^2_{out}, \ldots, x_{k}, q^{k}_{in}, q^{k}_{out}, x_{k+1})$, where $x_1 = x$, $k\leq 10$, and for all $i$, $q^i_{out}$ and $x_{i+1}$ are both a function of $q^i_{in}$ and $x_i$. Note that the $q_{in}$'s are also determined according to what is written right of the boundary. So the way I think of the outcome $\pi_{x}$ is as a game. You give me $q^i_{in}$, and I, given $x_i$, write $x_{i+1}$ and reply with $q^i_{out}$.

Consider two words $x, y\in \Sigma^*$. We say that $x$ and $y$ are $\pi$-equivalent if they induce the same sequence $(q^1_{out}, q^2_{out}, \ldots)$ of states given that they receive the same $q^i_{in}$'s. Formally, $x$ and $y$ are $\pi$-equivalent if for all $q^i_{in}$, if the histories so far are:

• $(x, q^1_{in}, q^1_{out}, x_2, q^2_{in}, q^2_{out}, \ldots, x_{m}, q^{m}_{in}, q^{m}_{out}, x_{m+1}, q^{m+1}_{in})$

• $(y, q^1_{in}, q^1_{out}, y_2, q^2_{in}, q^2_{out}, \ldots, y_{m}, q^{m}_{in}, q^{m}_{out}, y_{m+1} q^{m+1}_{in})$

Then, both histories induce the same state $q^{m+1}_{out}$, although they may induce different words $x_{m+2}$ and $y_{m+2}$.

Consider two words $x, y \in \Sigma^*$. It is not hard to see if $x$ and $y$ are $\pi$-equivalent, then for all $z\in \Sigma^*$, it holds that $xz$ is accepted iff $yz$ is accepted. Indeed, imagine that you are standing at the boundary between $xz$ or between $yz$, and keep track of the states the machine moves to upon each cross. So you don't see $x$ and $z$, you only see the states. As $x$ and $y$ produce the same sequence of states given the same $q_{in}$'s, and as the $q_{in}'s$ are determined based on the visited states, the value of $z$ , and are not affected if at the beginning we replaced $x$ with $y$, then we get that the machine visits the same sequence of states (although it may modify the tape differently left of the boundary). Note that the fact that we accept only after scanning the input to its right end, implies that we accept $xz$ iff we accept $yz$ (note that here we use the assumption that the machine is a decider, and thus it eventually halts after moving to the right end of the tape's content -- so it cannot be the case that the computation never leaves the portion of the tape where $x$ or $y$ is written). As there are finitely many sequences of states of length at most $k$, it follows that the equivalence relation $\pi$-equivalent has finitely many equivalence classes, and thus we conclude that the language of the machine has finitely-many Myhill-Nerode equivalence classes, and hence is regular.

To sum up, the crux of the proof is that every word $x$ induces a function $f_x$ that given a sequence of incoming states, outputs a sequence of outgoing states. As we are allowed input and output sequences of length at most 5, then there are finitely many such functions.

Edit: Let $L$ be the language of the machine. If you are not satisfied with the Myhill-Nerode approach, then you can easily define an explicit DFA $A = (\Sigma, Q, q_0, \delta, F)$ for $L$, where:

• $Q = \{ f_x\}_{x\in \Sigma^*}$.
• $q_0 = f_\epsilon$.
• For every letter $\sigma$, and state $f_x$, we define $\delta(f_x, \sigma) = f_{x\cdot \sigma}$.
• $F = \{ f_x: x \in L\}$.

The only non-trivial point is to note that for every distinct words $x\neq y \in \Sigma^*$, and letter $\sigma\in \Sigma$, it holds that if $f_x = f_y$, then $f_{x\cdot a} = f_{y\cdot a}$. Also, by what we've argued above, if $f_x = f_y$, then $x\in L$ iff $y\in L$.

Note: I assumed that the machine is deterministic as in these textbooks, a "Turing machine" means deterministic Turing machine, unless explicitly stated otherwise (we can see in the question's body that properties of a computational model are written in parentheses, including the branching mode).

Answer 2

I describe an NFA construction method for a non-deterministic Turing machine. Let's fix an input and fix a run of the Turing machine. Let $M$ be the maximum tape cell index visited by the run. For $1 \le i \le M$, let $1 \le k_i \le K$ be the number of times tape cell $i$ is visited, where $K$ is the maximum visit count.

The head movement of the Turing machine can be represented by a Hamiltonian path of the directed graph $G = (V, E)$, $V = \{ (i, j) \mid 1 \le i \le M, 1 \le j \le k_i \}$, $E = \{ ((i, j_1), (i+1, j_2)), ((i+1, j_2), (i, j_1)) \mid 1 \le i \lt M, 1 \le j_1 \le k_i, 1 \le j_2 \le k_2, j_1 \le j_2 \}$. The condition $j_1 \le j_2$ is to ensure the vertices ordering within a cell matches the order of visits.

The NFA will generate a Hamiltonian path, using only local states. The important thing is that the (undirected version of) graph $G$ has a small (~ $K$) path-width.

Below, the "previous cell" always means the tape cell $i-1$ when the current cell $i$ is processing.

The NFA guesses a visit count $k_i$ and the state of the Turing machine before each visit. Then, NFA guesses a transition (a state, move direction, and cell symbol) after each visit of the current cell. For each visit, the NFA checks the transition is valid for the state and the current symbol on the cell (computed from the transition after the previous visit of the current cell). The NFA remembers the states and the transitions for the next cell.

Then, the NFA guesses a subset of edges between the current and the next cell. The NFA remembered these edges for the next cell. The state after and before the visit of the source and target vertices of an edge must match.

For each vertex of the current cell, compute the in-degree and the out-degree using the previous and current edge subsets. Both degrees must be $1$ except the start and the end vertex. The start vertex is always the first visit of the first cell. The end vertex can be anywhere with a halt transition, but a flag is remembered to ensure there is only one end vertex.

To be a Hamiltonian path, (undirected version of) generated subgraph must be connected. For the connectivity check, a partition of the vertices of the current cell is maintained. The partition represents the connected components of the partially generated graph. All previous vertices must be connected to a current vertex. This is the same technique often used for dynamic programming on a path/tree decomposition.

The NFA reads an input symbol for the first cells. After the input ends (guessed), the NFA starts an epsilon-transition-loop for a non-deterministic number of times. In the loop, the NFA emulates an empty symbol input.

The NFA accepts the input if the "end vertex seen" flag is on, the transitions of the current cell don't contain any right moves, and all the current vertices must be connected by the partition.

The state of the NFA mainly consists of Turing machine states after visits of the previous cell, an edge subset between the previous and current cell, and a connectivity partition of the current vertices. A rough estimate of the state size is $O((2 |Q| K^2)^K)$.