On Complexity of Nondeterministic Turing Machines Computations.
Michal P. Chytil · Mathematical Foundations of Computer Science · 1975
A relation of three complexity measures for nondeterministic one-tape, one-head Turing machines is established in this paper. Namely, the fact that for every arithmetic function f such that (∀ n) (f(n) ≥ n) the class of languages recognized with the tape bound f coincides with the classes of languages recognized with the crossing and reversal bound f, respectively, is proved. This result is used to show that CS-languages can be characterized as a projection of a class of languages recognized by deterministic Turing machines.