Technology reports of the Yamaguchi University

Back to Top

Technology reports of the Yamaguchi University Volume 3 Issue 2
published_at 1983-12

A note on multihead on-line turing machines

A note on multihead on-line turing machines
Sakurayama Shunichi
Inoue Katsushi
Takanami Itsuo
Taniguchi Hiroshi
fulltext
501 KB
KJ00004351050.pdf
Descriptions
This paper introduces a tape-bounded multihead on-line Turing machine which can be considered as a multihead version of a tape-bounded 1-head on-line Turing machine. We first investigate hierarchies based on the number of input heads. We then investigate the difference between the accepting powers of tape-bounded nondeterministic multihead on-line Turing machines and deterministic ones. Finally, closure properties of the classes of languages accepted by tape-bounded multihead on-line Turing machines are investigated.