A Turing machine space hierarchy.
Stanislav Žák · Czech digital mathematics library · 1979
A Turing Machine Space Hierarchy STANISLAV ŽÁK This paper introduces a new, finer space complexity measure of computations on Turing machines.The complexity of a computation on a Turing machine now takes into account also the capacity of the finite control.It is proved that a slight enlarging (by an additive constant) of the complexity bound increases the computing power.The proofs are based on a new principle of diagonalization.The results are similar for deterministic and nondeterministic off-line Turing machines, auxiliary pushdown automata, auxiliary counter automata and also for their versions with an oracle.