A note on three-way two-dimensional probabilistic turing machines
This paper introduces a three-way two-dimensional probabilistic Turing machine (tr2-ptm), and investigates several properties of the machine. The tr2-ptm is a two-dimensional probabilistic Turing machine (2-ptm) whose input head can only move left, right. or down, but not up. Let 2-ptm(s) (resp, tr2-ptm(s)) denote a 2-ptm (resp. tr2-ptm) whose input tape is restricted to square ones, and let 2-PTMs(S(n)) (resp. TR2-PTMs(S(n))) denote the class of sets recognized by S(n) space-bounded 2-ptm(s)'s (resp. tr2-ptm(s)'s) with error probability less than 1/2, where S(n) : N --> N is a function of one variable n (= the side-length of input tapes). Let TR2-PTM(L(m, n)) denote the class of sets recognized by L(m, n) space-bounded tr2-ptm's with error probability less than 2, where L(m, n) : N-2 --> N is a function of two variables m (= the number of rows of input tapes) and n (= the number of columns of input tapes). The main results of this paper are: (1) 2-NFA(s)-TR2-PTMs(S(n)) not equal phi for any S(n) = o(log n), where 2-NFA(s) denotes the class of sets of square tapes accepted by two-dimensional nondeterministic finite automata, (2) TR2-PTMs(S(n)) subset of(plus attached) 2-PTMs(S(n)) for any S(n)= o(log n), and (3) for any function g(n) = o(log n) (resp. g(n) = o(log n/ log log n)) and any monotonic nondecreasing function f(m) which can be constructed by some one-dimensional deterministic Turing machine, TR2-PTM (f(m) + g(n)) (resp. TR2-PTM(f(m) x g(n))) is not closed under column catenation, column closure, and projection. Additionally, we show that two-dimensional nondeterministic finite automata are equivalent to two-dimensional probabilistic finite automata with one-sided error in accepting power.
three-way two-dimensional probabilistic turing machine closure property space-bounded computation