On three-way two-dimensional turing machines
On three-way two-dimensional turing machines
复制标题
三路二维图灵机
DOI：
10.1016/0020-0255(89)90010-8
复制
发表时间：
1989
影响因子：
8.1
通讯作者：
Andrzej Szepietowski
中科院分区：
文献类型：
--
作者：
Andrzej Szepietowski
本文解决了关于三路带界图灵机的封闭性的几个公开问题。结果表明：（1）如果L（m）≥ m ~ 2是可构造的，则非确定三路L（m）带界图灵机所接受的方带集类在可补下是闭的;（2）如果L（m）< logm，则非确定三路L（m）带界图灵机所接受的方带集类在行和列循环闭包下都不是闭的;（3）如果L（m，n）=mg（n）或L（m，n）=g（m）n，则L（m，n）空间对于确定性三路L（m，n）带界图灵机所接受的（一般）带集类在行列连接、行列闭包或行列循环闭包下是封闭的是必要的.
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-wayL(m) tape-bounded Turing machines is closed under complementation ifL(m)⩾m2is constructible, (2) the class of sets of square tapes accepted by nondeterministic three-wayL(m) tape-bounded Turing machines is closed neither under row nor column cyclic closure ifL(m) < logm, (3) ifL(m,n) =mg(n)orL(m,n) =g(m)n, thenL(m,n)⩾mnspace is necessary for the class of sets of (general) tapes accepted by deterministic three-wayL(m,n) tape-bounded Turing machines to be closed under row or column catenation, row or column closure or row or column cyclic closure.