Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Turing Machine with multiple tapes can be encoded such that its computational power is equivalent to Turing Machine with single tape. My question is if we have unbounded number of tapes, just like the length of a tape, would it change the computational power of a Turing Machine.

My intuition: No, since we could always encode the symbols on the tapes "diagnonally" just like the method we use to prove rational numbers are countable. For the sake of convenience we could even assume that each tape is a one-way tape. More precisely if we write this as a matrix with unbounded dimension, $(a_{i,j}), i,j\geq 0$, and the encoded symbols on the new tape are $(a_{k,0},a_{k-1,1},\dots,a_{1,k-1} ,a_{0,k})$ for each $k\in N$.

What do you think of the argument?

share|cite|improve this question
I think when you are simulating one machine by another, you have to write code, taking advantage of known macros. The idea is good, there is a good deal of detail missing. – André Nicolas Oct 4 '12 at 22:17
@AndréNicolas: The problem here is when simulating the machine with finite tapes,say $k$ for example, we could encode $(\alpha_1, \dots, \alpha_k)$ to a new symbol in the one-tape machine and there are only finitely many new encoded symbols. However in the argument above, there might be infinitely many symbols. – Jing Zhang Oct 4 '12 at 23:07
up vote 2 down vote accepted

This depends on exactly what you take "Turing machine with an unbounded number of tapes" to be.

If you just require the machine to have a finite number of states but allow each transition to depend on the values read at all the infinitely many tapes simultaneously, then you do get a lot of extra computational power. The transition table becomes infinite even for finitely many states, so you can encode, say, an entire HALT-oracle there.

On the other hand, if the transitions out of each machine state depends only on a finite set of tapes, then there are only finitely many tapes that can ever be read by any state. Then each particular machine of that kind effectively is still a finitely-many-tapes machine.

So if you want to make meaningful use of the unboundedly many tapes without needing infinite space to describe the machine itself, then you need to have some read/write head that can move not only left and right on a single tape, but can also move "up" and "down" between tapes under control of the transition table. And then it begins to look to me not so much as a machine with many tapes, but as one with a single two-dimensional "tape". (Yes, there are still some differences, but they are minor).

In any case, no matter what we call the latter construction, it clearly does not increase the computational power, because it can be simulated by something we already know is equivalent in power to an ordinary Turing machine -- such as a RAM.

share|cite|improve this answer
What was in my mind was that 2-dimensional "tape". So you are saying the machine with a header capable of moving up and down (unboundedly) is as powerful as the ordinary Turing Machine? – Jing Zhang Oct 4 '12 at 23:16
@JingZhang: Yes. Obviously it can do everything an ordinary Turing machine can (just never move up or down). Conversely, I can easily imagine how to write a program that simulates it, in a language that I already know can be simulated by an ordinary Turing machine. – Henning Makholm Oct 4 '12 at 23:20

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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