Closure properties of the classes of sets recognized by space-bounded two-dimensional probabilistic Turing machines (Q1818780)

The \(L(m,n)\) space-bounded two-dimensional Turing machines are defined as two-dimensional Turing machines which use at most \(L(m,n)\) cells on the storage tape for any input with \(m\) rows and \(n\) columns. The authors consider the probabilistic case of such Turing machines with error probability less than \(1 \over 2\). In the paper the following four cases are presented: 1. \(L(m,n) = f(m)+g(n)\) where \(f(m)=o(\log m)\), \(g(n)\) a monotonic nondecreasing function constructed by some one-dimensional deterministic Turing machine; 2. \(L(m,n) = f(m) \times g(n)\) where \(f(m)=o(\log m/ \log\log m)\), \(g(n)\) is like in the above case; 3.--4. are given by replacing in 1. and 2., respectively, conditions for \(f\) by conditions for \(g\) and conversely. The article contains the following results: The class of sets recognized by \(L(m,n)\) space-bounded two-dimensional probabilistic Turing machines with error probability less than \(1 \over 2\) is not closed under row catenation, row closure and projection for \(L(m,n)\) given by conditions 1. or 2. The class of sets recognized by \(L(m,n)\) space-bounded two-dimensional probabilistic Turing machines with error probability less than \(1 \over 2\) is not closed under column catenation, column closure and projection for \(L(m,n)\) given by conditions 3. or 4. The class of sets recognized by \(L(m,n)\) space-bounded two-dimensional probabilistic Turing machines with error probability less than \(1 \over 2\), which always halt in the accepting or rejecting state for all inputs is closed under union, intersection and complementation for any \(L(m,n)\).