Puzzle 2
This 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.
For figure, see postscript file.
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.)