A Note on Two-dimensional Probabilistic Turing Machines (Algorithms and Theory of Computing)
Tokio Okazaki, Katsushi Inoue, A. S. Ito, Yue Wang · Institutional Repositories DataBase (IRDB) · 1998
Note $.\mathrm{o}\mathrm{n}$ . Two-dimensional Probabilistic Turing Machines岡崎世雄 (山口東京理科大学、 基礎工学部、 電子基礎工学科) 井上克司、 伊藤暁、 王躍 (山口大学、 工学部、 知能情報学科) SummaryThis paper introduces two-dimensional probabilistic Rring machines $(2-\mathrm{P}^{\mathrm{t}\mathrm{m}' \mathrm{S}})$ , and investigates several prop- erties of them.We first investigate a relationship between two-dimensional alternating finite automata (2- $\mathrm{a}\mathrm{f}\mathrm{a}^{)}\mathrm{S})$ and 2-ptm's with exror probability less than $\frac{1}{2}$ and with sublogarithnlic space, and show that there is a set of square tapes accepted by 2-afa, but not recognized by any $o(\log n)\mathrm{s}_{\mathrm{P}^{\mathrm{a}\mathrm{c}\mathrm{e}\mathrm{b}\mathrm{o}\mathrm{u}\mathrm{n}}\mathrm{e}\mathrm{d}}-\mathrm{d}2$ -ptm with error probability less than $\frac{1}{2}$ .This partially solves an open problem in [17].We next investigate a space hierarchy of $2_{-\mathrm{P}^{\mathrm{t}}}\mathrm{m}' \mathrm{s}$ with error probability less than $\frac{1}{2}$ and with sublogarithmic space, and show that if $L(n)$ is space-constructible by a two-dimensional Turing machine, loglog $n