8
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ What does "finite automaton equivalent to $T$ really means? Considering, for example, that $T$ can either accept, reject, or get stuck in an infonite loop. Should we interpret this as $there exists an NFA $N$ that accepts the same language $T$ recognizes$? $\endgroup$
    – nir shahar
    Jan 25, 2022 at 9:58
  • $\begingroup$ @nirshahar Thanks. We can assume that $T$ is a decider, i.e. does not loop. $\endgroup$
    – Emolga
    Jan 25, 2022 at 10:07
  • $\begingroup$ Whoops sorry about the syntax of my comment, I wrote it from my phone and didn't realize it messed up :o $\endgroup$
    – nir shahar
    Jan 25, 2022 at 10:08
  • $\begingroup$ I am even more confused. It is easy to copy the finite contents of the tape with a few visits, and then make a single computational step at the new position. In that way every cell is visited at most (say) five times and the computation marches on, each time further away on the tape. So without further restrictions/assumptions I fail to see how we can build an NFA. $\endgroup$ Jan 25, 2022 at 19:41
  • $\begingroup$ @HendrikJan Since the state of a given Turing machine can only carry information less than some fixed amount, each visit can only can only copy less than a fixed amount of cells. So, if the content of the tape is long enough, any constant number of visits will not be able to copy all of them to a new position. $\endgroup$
    – John L.
    Jan 25, 2022 at 22:02

1 Answer 1

0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ "The state of the NFA mainly consists of states after visits of the previous cell, etc."? Do you mean "The state of the NFA mainly consists of the internal state of the given Turing machine and a tape symbol, etc."? Please come to this chat room discussion on pchthm's answer. $\endgroup$
    – John L.
    Jan 27, 2022 at 17:23
  • $\begingroup$ This answer could have been clearer, for me at least, had it assumed $T$ is deterministic. $\endgroup$
    – John L.
    Jun 27, 2022 at 10:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.