A Note on the ε-Move of On-Line Multitape Turing Machines

オンライン多テープチューリング機械のε-動作に関する一考察

A Note on the ε-Move of On-Line Multitape Turing Machines

Creators Inoue Katsushi

Creators Takanami Itsuo

Let f (n) be a time function. By k-DTM (f (n)) (k-NTM (f (n))), we denote the class of languages accepted by deterministic (nondeterministic) on-line k-tape Turing machines which, given an input of length n, operate in such a way that the input heads stay on the same input position at most f (n) steps. This paper shows that if lim [f (n)/(log n)^r]=0 for some positive constant r, then (1) [numerical formula] and [numerical formula], and (2) [numerical formula] and [numerical formula] are not closed under concatenation, Kleene closure, length-preserving homomorphism, or reversal.

[ISSN]0372-7661

[NCID]AN00244228