A Turing machine time hierarchy

AbstractThe time separation results concerning classes of languages over a single-letter alphabet accepted by multi-tape nondeterministic Turing machines, well-known from Seiferas, Fischer and Meyer (1978), are supplemented. Moreover, via a universal machine a modified time complexity measure UTIME of Turing machines computations which is sensitive to multiplication by constants (i.e., UTIME(t) ⊊ UTIME(kt), where UTIME(t) is the class of languages of complexity not larger than t) is introduced. On the level of this measure, the results concerning languages over one- and two-letter alphabets are refined. The proof tools are versions of a translational diagonalization and of an unpadding technique