6
$\begingroup$

So if k is the number of tapes, is a multi-tape Turing machine allowed to have k = ∞ tapes.

I'd assume not since this would give an infinite transition function?

$\endgroup$
  • 2
    $\begingroup$ You should read Yuval Filmus' answer. The issue is not the finiteness of the machine but the finiteness of machine descriptions and computations descriptions (if I understand correctly). Your question should be clarified. Are you asking whether infinite number of tapes is always meaningful independently of other constraints, or whether it can be meaningful provided some other constraints are met? $\endgroup$ – babou Apr 24 '14 at 8:44
  • $\begingroup$ Well both, and all, views are interesting. My question was more of a starter for discussion. The responses have absolutely aided in my understanding of Computational Theory. $\endgroup$ – Ozal Apr 24 '14 at 22:00
8
$\begingroup$

You need a finite number of tapes. The proofs that show the equivalence between multi-tape TM and one-band TM rely on the fact that the number of tapes is bounded.

Notice that it especially the number of heads should be bounded. Sure, you can use a 2d TM, however, there is still only one head in this model. If you would allow an infinite number of heads, then the configuration of a TM would be infinite. This will cause a lot of problems and would give a quite different model of computation.

$\endgroup$
  • 1
    $\begingroup$ Non sequitur. The fact that one proof of A requires a property P does mean that there is no proof of A that relies on some other property. Actually the answer to the question hinges on whether it asks whether infinite number of tapes is always meaningful independently of other constraints, or whether it can be meaningful provided some other constraints are met. The question is unclear in this respect. $\endgroup$ – babou Apr 24 '14 at 8:41
4
$\begingroup$

You can have infinitely many tapes. Suppose that your transition function is of the following form:

  • Each state $s$ is associated with a head number function $h(s,x)$.

  • When at state $s$, if the symbol under head $h(s,x)$ is $\alpha$ then change the symbol to $\beta(s,\alpha)$, move the tape $n(s,\alpha)$ steps to the right, update the variable $x$ by the amount $c(s,\alpha)$, and switch to state $t(s,\alpha)$.

The variable $x$ is potentially unbounded, so we access an unbounded number of tapes.

This can be implemented in C and so results in a computable model. One-tape Turing machines can be simulated, so this model is Turing-complete.

You can think of many other models of this sort. For example, and finite number of tapes can be consulted at a time, any finite number of tapes can be modified, any number of heads moved, and so on. We can use several variables rather than just $x$, we can allow more indirect reference, and so on. We can even allow $d$-dimensional tapes. Use your imagination.

One could object (following other answerers and commenters) that the correct formulation of a Turing machine with infinitely many tapes allows referencing all of them at the same time; our model can support that to some extent, for example operations of the following sort:

  • Write $\alpha$ on all tapes.

  • Make a certain transition only if all but finitely many symbols under all heads are $\alpha$.

And so on. As long as the description of the machine is finite and the operations reasonable, the machine can be simulated by a program in C or by a Turing machine. What is not allowed is a machine with an infinitary description, but as far as I'm concerned "infinitary description" is an oxymoron.

$\endgroup$
  • $\begingroup$ Interesting example. I suppose such constructs come handy when reducing problems (or when?). Infinity is subtle. Is there a simple explanation of how you reduce to finite the two apparently infinitiary operations examples that you give? $\endgroup$ – babou Apr 23 '14 at 10:12
  • $\begingroup$ Whenever you are trying to read a particular cell, go over all the history of the computation so far, and find out the latest value written in that cell. A similar idea should work for my other examples. $\endgroup$ – Yuval Filmus Apr 24 '14 at 0:43

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.