On three-way two-dimensional Turing machines
type: Item
instance of: scholarly article
title: On three-way two-dimensional Turing machines
zbMATH Open document ID: 0666.68050
DOI: 10.1016/0020-0255(89)90010-8
author: Andrzej Szepietowski
published in: Information Sciences
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 03D10
zbMATH DE Number: 4090804
zbMATH Keywords: closure properties
zbMATH Keywords: three-way tape-bounded Turing machines
MaRDI profile type: Publication
full work available at URL: 0020-0255(89)90010-8
OpenAlex ID: W2043305634
cites work: Three-way tape-bounded two-dimensional Turing machines
cites work: Closure properties of three-way and four-way tape-bounded two-dimensional Turing machines
cites work: A note on deterministic three-way tape-bounded two-dimensional Turing machines
cites work: Nondeterministic Space is Closed under Complementation
description: scientific article; zbMATH DE number 4090804