Puzzle 2

The second puzzle is a decision problem for finite automata with 2-heads. A 2-head finite automaton (THFA) consists of a finite control, an input tape, and two heads that can read but not write on the tape and move only left to right. The machine is started in its initial state with both heads on the leftmost square of the tape. Each transition is of the form $(q,u,v,p)$ where $q$ and $p$ are states and $u$ and $v$ are strings. If $(q,u,v,p)$ is a transition of $M$, then $M$ can, when in state $q$, read $u$ with its first head and $v$ with its second head and enter state $p$, as shown in the figure. $M$ accepts an input string by moving both heads together off the right end of the tape while entering a designated final state.

A THFA is said to be deterministic if there is only one choice of move from any configuration. Is the emptiness problem for deterministic THFA decidable (i.e., can we check whether a deterministic THFA $M$ accepts at least one input)? (Note: The problem is undecidable for non-deterministic THFA.)

Solution sketch

This problem is undecidable. Let us first see why the emptiness for the nondeterminisitic version of this automaton is undecidable. It is easy to reduce Post's Correspondence Problem (PCP) to the emptiness problem for these automata.

The automaton corresponding to an instance of PCP has just one state $q$, which is deemed accepting. The automaton has a transition of the form $(q,u_i,v_i,q)$ for each pair of strings $(u_i,v_i)$ in the PCP instance. For convenience let us call such a transition $t_i$. If the automaton has gone through the transition sequence $t_{i_1},t_{i_2},\ldots,t_{i_k}$ then the first head has read the string $u_{i_1}u_{i_2}\ldots u_{i_k}$ and the second head has read the string $v_{i_1} v_{i_2} \ldots v_{i_k}$. It is easy to see that a sequence of transitions $t_{i_1},t_{i_2},\ldots,t_{i_k}$ leads to acceptance iff the sequence $i_1 i_2 \cdots i_k$ is a solution to the PCP instance.

But note that the above automaton is nondeterministic. Even though it has only one state, more than one transition may be enabled in some configurations. There might be more than one $(u_i,v_i)$ pair that can be read from the current head position. We will now show that this nondeterminism can be got rid off. This will be done by ``marking'' the string to indicate how to parse it in terms of the $u_i$'s and $v_i$'s.

Formally, if the strings of the PCP come from the alphabet $\Sigma$ then we construct an automaton that works over the alphabet $\Sigma \times \{s,m,e\} \times \{s,m,e\}$. Here $s$ stands for start, $m$ for middle and $e$ for end. If $(a_1a_2 \ldots a_k,b_1b_2 \ldots b_l)$ is a pair specified by the PCP then there are transitions labelled $(q, (a_1,s,x_1)$ $\cdots$ $(a_{k{-1}},m,x_{k{-1}})$ $(a_k,e,x_k)$ , $(b_1,y_1,s)$ $\cdots$ $(b_{l{-1}},y_{k{-1}},m)$ $(b_l,y_l,e)$ $,q)$ for each choice of $x_i, y_i$ from $\{s,m,e\}$.

The input can be thought of as consisting of three rows. The first row consists of a string over the alphabet $\Sigma$ while the second row specifies (correctly or incorrectly) how to break it up into $u_i$'s and the third row specifies how to break it up into $v_i$'s. For any given configuration there is at most one transition enabled corresponding to a pair $(u_i,v_i)$ if such a pair is correctly marked in the input from the current head positions. Thus the automaton is indeed deterministic. Its language consists of precisely the solutions to the PCP problem with the second and third row indicating how to break it up into $u_i$'s and $v_i$'s respectively. An interested reader can fill in the details as well as ``correct'' the above solution to work even when the pairs specified by the PCP contain strings of length $1$ or less.

P Madhusudan, IMSc, Chennai
madhu@imsc.ernet.in