I want to prove that if we have a model, $A$, with unbound number of tapes, then $A$ is stronger then Turing Machine model. Can you help me with example of such a language that $M$ will fail but $A$ will give an output? thanks.

  • $\begingroup$ I've tried to answer the question I think you're asking, but note that "$M(L)$ will fail but $A(L)$ will give an output" doesn't make a lot of sense. We write "$M(L)$ for the action of a machine $M$ on input $L$ but that input is a string, not a language. $\endgroup$ – David Richerby May 6 '17 at 17:50
  • $\begingroup$ You are write. It confusing for me, I will fix it. Thanks! $\endgroup$ – Moshe9362 May 6 '17 at 18:00

It is a standard proof that Turing machines with any finite number of tapes are equivalent to single-tape Turing machines, since you can code any fixed number of tapes on a single tape.

If you allow a Turing machine to have an infinite number of tapes, then you can decide any language $L$. To do this, first copy the input $x_1\dots x_\ell$ so that the $i$th tape contains the symbol $x_i$ in its first cell. Now move all the tape heads back to position $1$ and enter some special state $q_\mathrm{decide}$. Recall that the transition function decides what to do based on the state the machine is in at the moment, and what is under each of the infinitely many heads. So just define it to accept from state $q_{\mathrm{decide}}$ if there is some $k$ such that it sees $w_1, \dots, w_k$ under the first $k$ heads and $w_1\dots w_k\in L$, and every other head sees the blank character; otherwise, it rejects.

Note that there is a philosophical problems with write down the transition function if $L$ is undecidable, but the function certainly exists.


Your Answer

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

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