A note on multihead on-line turing machines

A note on multihead on-line turing machines

Creators Sakurayama Shunichi

Creators Inoue Katsushi

Creators Takanami Itsuo

Creators Taniguchi Hiroshi

Creators Matsuno Hiroshi

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.

[ISSN]0386-3433

[NCID]AA0086073X