3次元オルタネーティングチューリング機械の葉数に基づく階層性

In [3], we introduced three-dimensional alternating Turing machines (3 - ATM's). In this paper, we continue the investigations about 3 - ATM's, and mainly investigate a simple, natural complexity measure for space bounded 3 - ATM's, called "leaf-size" [1]. A3 - ATM M has a read-only three-dimensional input tape and one semi-infinite storage tape. We let the input tapes, through-out this paper, be restricted to cubic ones. Let L(m) : N → N be a function with one variable m. We denote an L(m) space-bounded 3 - ATM by 3 - ATM(L(m)). Let Z(m) : N → N be a function with one variable m. For each finite tree t, let LEAF(t) denote the leaf-size of t (i.e., the number of leaves of t). We say that a 3 - ATM M is Z(m) leaf-size bounded if, for each m and for each cubic input x of side-length m, each computation tree t of M on x is such that LEAF(t) ≤ Z(m). By 3 - ATM(L(m), Z(m)), we denote a simultaneously L(m) space bounded and Z(m) leaf-size bounded 3 - ATM, and by L[3 - ATM(L(m), Z(m))], we denote the class of sets accepted by 3 - ATM(L(m), Z(m))'s. Further, a function L : N → N is three-dimensionally space constructible if there is a deterministic three-dimensional Turing machine M such that (1) for each m ≥ 1 and for each cubic input of side-length m, M uses at most L(m) cells of the storage tape, (2) for each m ≥ 1, there exists some cubic input of side-length m on which M halts after its read-write head has marked off exactly L(m) cells of the storage tape, and (3) for each m ≥ 1, when given any cubic input of side-length m, M never halts without marking off exactly L(m) cells of the storage tape.