Geffert extended this theorem to show that there exist unary languages described by this theorem.
Geffert extended this theorem to show that there exist unary languages described by this theorem. The original proof of this theorem used a language defined as the set of inputs that a Turing machine does not accept before visiting a certain number of cells. One corollary of this theorem is that L is a strict subset of the class that contains the quantified Boolean formulas problem. One form of it applies to functions f for which there exists a deterministic Turing machine that halts after visiting a number of cells on its tape equal to f of the size of the input. Those functions are constructible in the sense required by this theorem. Formally, this theorem holds that (*) "SPACE of little-o of f of n" is a strict subset of "SPACE of f of n". For 10 points, name this theorem that proves that a Turing machine with access to asymptotically more space can decide more languages.
Geffert extended this theorem to show that there exist unary languages described by this theorem.
space hierarchy theorem [accept (non-)deterministic space hierarchy theorem; prompt on "hierarchy theorem"]