On three-way two-dimensional Turing machines
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.
- Non-closure property of space-bounded two-dimensional alternating Turing machines
- A note on three-way two dimensional alternating Turing machines
- Closure properties of the classes of sets recognized by space-bounded two-dimensional probabilistic Turing machines
- Three-dimensional alternating Turing machines with only universal states
- On three-way two-dimensional multicounter automata
- Three-way automata on rectangular types over a one-letter alphabet
- A hierarchy result for 2-dimensional TM's operating in small space
- Some remarks on two-dimensional finite automata
- Some results concerning 2-D on-line tessellation acceptors and 2-D alternating finite automata
- Simple picture processing based on finite automata and regular grammars
- Non-closure property of space-bounded two-dimensional alternating Turing machines
- Modeling multitape Minsky and Turing machines by three-tape Minsky machines
- Three-way two-dimensional alternating finite automata with rotated inputs
- On three-way two-dimensional multicounter automata
- Universality of Wolfram’s 2, 3 Turing Machine
This page was built for publication: On three-way two-dimensional Turing machines
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1116697)
