Synchronized alternating turing machines on four-dimensional input tapes
Makoto Sakamoto, Tomoya Matsukawa, Ryoju Katamune, Hiroshi Furutani, Michio Kono, Satoshi Ikeda, Takao Ito, Yasuo Uchida, Tsunehiro Yoshinaga · WSEAS Transactions on Computers archive · 2010
Synchronized alternating machine is an alternating machine with a special subset of internal states called synchronizing states. This paper introduces a four-dimensional synchronized alternating Turing machine (4-SATM), and investigates fundamental properties of 4-SATM's. The main topics of this paper are: (1) a relationship between the accepting powers of 4-SATM's and four-dimensional alternating Turing machines with small space bounds, (2) a relationship between the accepting powers of seven-way and eight-way 4-SATM's, (3) a relationship between the accepting powers of 4-SATM's and four-dimensional nondeterministic Turing machines. In this paper, we let each sidelength of each input tape of these automata be equivalent in order to increase the theoretical interest.