A TURING MACHINE TIME HIERARCHY
Czechoslovakia · 1983
The time separation results concerning classes of languages over a single-1etteK 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) s UTIME(kt), where UTIME( t) is the class of languages jf 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 1 translational diagonalization and of an unpadding technique. Key wards. Turing machine, universal machine, time complexity, complexity hierarchy, nondeter- minism, unpadding, single-letter alphabet, diagonalization. CR category. F.1.3.