Two-dimensional alternative Turing machines (Q794169)

A two-dimensional alternating Turing machine (2-ATM) M is a natural extension of an alternating Turing machine to two dimensions. It has a read-only rectangular input tape with special boundary symbols, one semi- infinite storage tape, a finite control, an input tape head and a storage tape head. A step of M consists of reading one symbol from each tape, writing a symbol on the storage tape, moving the input and storage heads in specified directions and entering a new state in accordance with the transition rules. Similarly, a three-way two-dimensional alternating Turing machine (TR2-ATM) can be defined. Acceptance of input tape x by 2- ATM (TR2-ATM) is introduced in a natural way. \[ T(M)=\{x| M\quad accepts\quad x\}. \] The authors investigate a relationship between the accepting powers of space bounded 2-ATM's (TR2-ATM's) and space bounded TM's (TRTM's) and show that, for some space bounded classes, 2-ATM's (TR2-ATM's) are more powerful than TM's (TRTM's). Next, they introduce leaf-size for 2-ATM (TR2-ATM) on a given input as the number of leaves of an accepting computation tree with fewest leaves and provide a spectrum of complexity classes based on leaf-size bounded computations. Finally, they investigate recognizability of connected patterns by 2-ATM's (TR2- ATM's) and formulate some open problems.