Problem Detail: 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?
Asked By : Ozal
Answered By : A.Schulz
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/23936
