Memoirs of the Faculty of Engineering, Yamaguchi University
Back to Top
Permalink : https://petit.lib.yamaguchi-u.ac.jp/14357
Memoirs of the Faculty of Engineering, Yamaguchi University Volume 31 Issue 1
published_at 1980
A Note on the ε-Move of On-Line Multitape Turing Machines
オンライン多テープチューリング機械のε-動作に関する一考察
Inoue Katsushi
Takanami Itsuo
About This Article
Descriptions
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.
Other Article
PP. 51 - 60
Deterioration in the Mechanical Strength of Commercial Carbon Steels Exposed in Various Environments
PP. 61 - 70
PP. 163 - 169