A Note on the ε-Move of On-Line Multitape Turing Machines
Memoirs of the Faculty of Engineering, Yamaguchi University Volume 31 Issue 1
Page 83-87
published_at 1980
Title
オンライン多テープチューリング機械のε-動作に関する一考察
A Note on the ε-Move of On-Line Multitape Turing Machines
Creators
Inoue Katsushi
Creators
Takanami Itsuo
Source Identifiers
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.
Languages
jpn
Resource Type
departmental bulletin paper
Publishers
山口大学工学部
Date Issued
1980
File Version
Version of Record
Access Rights
open access
Relations
[ISSN]0372-7661
[NCID]AN00244228
Schools
工学部