On three-way two-dimensional Turing machines (Q1116697)

This paper solves several open problems concerning closure properties of three-way tape-bounded Turing machines. It is shown that: (1) the class of sets of square tapes accepted by nondeterministic three-way L(m) tape- bounded Turing machines is closed under complementation if \(L(m)\geq m^ 2\) is constructible, (2) the class of sets of square tapes accepted by nondeterministic three-way L(m) tape-bounded Turing machines is closed neither under row nor column cyclic closure if \(L(m)<\log m\), (3), if \(L(M,n)=mg(n)\) or \(L(m,n)=g(m)n\), then L(m,n)\(\geq mn\) space is necessary for the class of sets of (general) tapes accepted by deterministic three- way L(m,n) tape-bounded Turing machines to be closed under row or column catenation, row or column closure or row or column cyclic closure.