A note on three-way two dimensional alternating Turing machines (Q1112612)

The paper is devoted to the investigation of properties of three-way two- dimensional alternating Turing machines (TR2-ATM), i.e., two-dimensional alternating Turing machines (2-ATMs) with input head allowed to move only left, right and down. It is shown that restricting storage tape space below log m for \(m\times m\) input tape TR2-ATMs are less powerful than 2- ATMs. This result complements previously known ones showing that for space greater than or equal to log m TR2-ATMs are equivalent to 2-ATMs on square input tapes. Also six operations on two-dimensional tape are introduced and closure properties are studied. Finally it is shown that log m space is necessary and sufficient for TR2-ATMs to accept the set of all square connected pictures.