Technology reports of the Yamaguchi University

Back to Top

Technology reports of the Yamaguchi University Volume 5 Issue 3
published_at 1994-12

Space hierarchies of three-dimensional turing machines

Space hierarchies of three-dimensional turing machines
Sakamoto Makoto
Inoue Katsushi
fulltext
801 KB
KJ00004351165.pdf
Descriptions
We investigate space complexity hierarchies of three-dimensional Turing machines whose input tapes are restricted to cubic ones, and show that there exists an infinite hierarchy among the classes of sets accepted by space-bounded three-dimensional deterministic or nondeterministic Turing machines with cubic inputs.