11
$\begingroup$

Suppose that a $k$-tape read-only Turing machine receives its input on each $k$ tapes. It cannot write on the tapes, but it can move on them in both ways, even move off from the input. So for example, it can simulate counter machines, which implies that it can recognize any recursive language if $k\ge 3$. If $k=1$, then it can be simulated by a two-way DFA, thus can recognize only regular languages. But what happens for $k=2$?

Can two-tape read-only Turing machines recognize any recursive language?

Note that two-counter machines exhibit an intermediate behaviour, but this doesn't seem to answer my question. Nor does the answer to this question, though the proof might not be much different.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ How does such a machine simulate a counter machine? $\endgroup$ – Andrej Bauer Nov 22 '18 at 13:22
  • 2
    $\begingroup$ @AndrejBauer: it can simulate a 2 counters machine if both tapes initially contain at least a marker. E.g. the first tape $\#\langle input \rangle$ second tape $\#$. A $+1$ in the counter machine is simulated moving the head to the right, a $-1$ is simulated moving the head to the left; the "zero" test can be done checking if the head is on the marker. $\endgroup$ – Marzio De Biasi Nov 22 '18 at 13:49
  • $\begingroup$ @domotorp, Do you mean "Can two-tape read-only Turing machines recognize every recursive language?" $\endgroup$ – Neal Young Nov 22 '18 at 20:27
  • 1
    $\begingroup$ @Neal Yes. $~~~~~~$ $\endgroup$ – domotorp Nov 22 '18 at 20:30
  • 1
    $\begingroup$ Note that it is also (very) difficult to prove that your model when restricted to unary inputs is equivalent to the power of two counters automata; see my other (unsolved) old question on cstheory: Conjecture about two counters automata. Clearly the conjecture is false in your model because it implicitly stores the original input as a "constant". At that time I also asked a few researchers about it (and also sent an email to Ibarra, but never got a solution :-) $\endgroup$ – Marzio De Biasi Nov 23 '18 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.