<p>Suppose that a <span class="math-container">$k$</span>-tape <a href="https://en.wikipedia.org/wiki/Read-only_Turing_machine" rel="noreferrer">read-only Turing machine</a> receives its input on each <span class="math-container">$k$</span> 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 <a href="https://en.wikipedia.org/wiki/Counter_machine" rel="noreferrer">counter machines</a>, which implies that it can recognize any recursive language if <span class="math-container">$k\ge 3$</span>.
If <span class="math-container">$k=1$</span>, then it can be simulated by a two-way DFA, thus can recognize only regular languages. But what happens for <span class="math-container">$k=2$</span>?</p>

<blockquote>
  <p>Can two-tape read-only Turing machines recognize any recursive language?</p>
</blockquote>

<p>Note that two-counter machines exhibit an <a href="https://en.wikipedia.org/wiki/Counter_machine#Two-counter_machines_are_Turing_equivalent_(with_a_caveat)" rel="noreferrer">intermediate behaviour</a>, but this doesn't seem to answer my question.
Nor does the answer to <a href="https://cstheory.stackexchange.com/questions/19551/can-a-two-counters-machine-decide-n2">this question</a>, though the proof might not be much different.</p>

CC BY-SA 4.0
2018-11-22T13:22:58.213Z
How does such a machine simulate a counter machine?
Andrej Bauer
CC BY-SA 4.0
2018-11-22T13:49:35.200Z
@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.
Marzio De Biasi
CC BY-SA 4.0
2018-11-22T20:27:16.597Z
@domotorp, Do you mean "Can two-tape read-only Turing machines recognize **every** recursive language?"
Neal Young
CC BY-SA 4.0
2018-11-22T20:30:26.430Z
@Neal Yes. $~~~~~~$
domotorp
CC BY-SA 4.0
2018-11-23T21:08:30.030Z
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](https://cstheory.stackexchange.com/q/21525/3247). 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 :-)
Marzio De Biasi
CC BY-SA 4.0
2018-11-23T21:57:13.943Z
I like this model, because it shows that Turing-machines are just as powerful without writing; for students, this is quite stunning.
domotorp
<cc.complexity-theory><computability><counter-automata>
Can two-tape read-only Turing machines recognize any recursive language?
domotorp
# Can two-tape read-only Turing machines recognize any recursive language?

(Asked by: username_0 on 2018-11-22)

Suppose that a $k$-tape [read-only Turing machine](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Counter_machine), 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](https://en.wikipedia.org/wiki/Counter_machine#Two-counter_machines_are_Turing_equivalent_(with_a_caveat)), but this doesn't seem to answer my question.
Nor does the answer to [this question](https://cstheory.stackexchange.com/questions/19551/can-a-two-counters-machine-decide-n2), though the proof might not be much different.

**Tags:** cc.complexity-theory, computability, counter-automata

> **Comments:**
> **username_1**: How does such a machine simulate a counter machine?  
> **username_2**: @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.  
> **username_3**: @username_0, Do you mean "Can two-tape read-only Turing machines recognize **every** recursive language?"  
> **username_0**: @Neal Yes. $~~~~~~$  
> **username_2**: 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](https://cstheory.stackexchange.com/q/21525/3247). 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 :-)  
> **username_0**: I like this model, because it shows that Turing-machines are just as powerful without writing; for students, this is quite stunning.  

---

## 0 answers

