7
$\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?

Improve this question
$\endgroup$
2
  • 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, 2014 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, 2014 at 22:00

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
1
  • 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, 2014 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.

Improve this answer
$\endgroup$
2
  • $\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, 2014 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, 2014 at 0:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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