patternMinor
Can a Multi-Tape Turing Machine have an infinite number of tapes?
Viewed 0 times
caninfinitenumbermultitapestapemachineturinghave
Problem
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?
I'd assume not since this would give an infinite transition function?
Solution
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.
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.
Context
StackExchange Computer Science Q#23936, answer score: 8
Revisions (0)
No revisions yet.