A note on two-dimensional probabilistic Turing machines
This paper introduces two-dimensional probabilistic Turing machines (2-ptm's), and investigates several properties of them. We first investigate a relationship between two-dimensional alternating finite automata (2-afa's) and 2-ptm's with error probability less than 1/2 and with sublogarithmic space, and show that there is a set of square tapes accepted by 2-afa, but not recognized by any o(log n) space-bounded 2-ptm with error probability less than a. This partially solves an open problem in Okazaki et al. (Inform. Sci., to appear). We next investigate a space hierarchy of 2-ptm's with error probability less than 1/2 and with sublogarithmic space, and show that if L(n) is space-constructible by a two-dimensional Turing machine, log log n < L(n) less than or equal to log n and L'(n) = o o(L(n)), then, there is a set of square tapes accepted by a strongly L(n) space-bounded two-dimensional deterministic Turing machine, but not recognized by any L'(nj space-bounded 2-ptm with error probability less than 1/2. (C) 1999 Elsevier Science Inc. All rights reserved.
two-dimensional probabilistic turing machine two-dimensional alternating turing machine space complexity