multitape Turing machine

views updated

multitape Turing machine A Turing machine that has a finite number of tapes, each tape having a tape head that can move independently. Such machines have the same computational power as single-tape Turing machines. Consider a multitape Turing machine M. If for no input word of length n does M scan more than L(n) cells on any tape then M is said to be an L(n) tape-bounded Turing machine. If for no input word of length n does M make more than T(n) moves before halting then M is said to be a T(n) time-bounded Turing machine.