On three-way two-dimensional Turing machines (Q1116697): Difference between revisions
From MaRDI portal
Latest revision as of 13:27, 19 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On three-way two-dimensional Turing machines |
scientific article |
Statements
On three-way two-dimensional Turing machines (English)
0 references
1989
0 references
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.
0 references
closure properties
0 references
three-way tape-bounded Turing machines
0 references
0 references