  Below is a translation from my Russian paper. I added references, unavailable
to me in Moscow. Similar results have been also given in [Schnorr Stumpf 75]
(see also [Lynch 75]). Earlier relevant work (classical theorems like
Compression, Speed-up, etc.) was done in [Tseitin 56, Rabin 59, Hartmanis
Stearns 65, Blum 67, Trakhtenbrot 67, Meyer Fischer 72].
  I translated only the part with the statement of the results. Instead of the
proof part I appended a later (1979, unpublished) proof sketch of a slightly
tighter version. The improvement is based on the results of [Meyer Winklmann
78, Sipser 78]. Meyer and Winklmann extended earlier versions to machines with
a separate input and working tape, thus allowing complexities smaller than the
input length (down to its log). Sipser showed the space-bounded Halting Problem
to require only additive constant overhead. The proof in the appendix below
employs both advances to extend the original proofs to machines with a fixed
alphabet and a separate input and working space. The extension has no (even
logarithmic) restrictions on complexity and no overhead (beyond an additive
constant). The sketch is very brief and a more detailed exposition is expected
later: [Seiferas Meyer].
