Refinement of Space Hierarchy
If space is measured as the number of cells used regardless of alphabet size, then SPACE(f(n)) = SPACE(O(f(n))) because one can achieve any linear compression by switching to a larger alphabet. However, by measuring space in bits, a much sharper separation is achievable for deterministic space. Instead of being defined up to a multiplicative constant, space is now defined up to an additive constant. However, because any constant amount of external space can be saved by storing the contents into the internal state, we still have SPACE(f(n)) = SPACE(f(n)+O(1)).
Assume that f is space-constructible. SPACE is deterministic.
- For a wide variety of sequential computational models, including for Turing machines, SPACE(f(n)-ω(log(f(n)+n))) ⊊ SPACE(f(n)). This holds even if SPACE(f(n)-ω(log(f(n)+n))) is defined using a different computational model than SPACE(f(n)) because the different models can simulate each other with O(log(f(n)+n)) space overhead.
- For certain computational models, including Turing machines with a fixed number of tapes (with one head per tape) and fixed alphabet size and with delimiters for the visited segment on each tape, SPACE(f(n)-ω(1)) ⊊ SPACE(f(n)).
The proof is similar to the proof of the space hierarchy theorem, but with two complications: The universal Turing machine has to be space-efficient, and the reversal has to be space-efficient. One can generally construct universal Turing machines with O(log(space)) space overhead, and under appropriate assumptions, just O(1) space overhead (which may depend on the machine being simulated). For the reversal, the key issue is how to detect if the simulated machine rejects by entering an infinite (space-constrained) loop. Simply counting the number of steps taken would increase space consumption by about f(n). At the cost of a potentially exponential time increase, loops can be detected space-efficiently as follows:
Modify the machine to erase everything and to go to a specific configuration A on success. Use depth-first search to determine whether A is reachable in the space bound from the starting configuration. The search starts at A and goes over configurations that lead to A. Because of determinism, this can be done in place and without going into a loop. Also (but this is not necessary for the proof), to determine whether the machine exceeds the space bound (as opposed to looping within the space bound), we can iterate over all configurations about to exceed the space bound and check (again using depth-first search) whether the initial configuration leads to any of them.
Read more about this topic: Space Hierarchy Theorem
Famous quotes containing the words refinement of, refinement, space and/or hierarchy:
“You know that your toddler needed love and approval but he often seemed not to care whether he got it or not and never seemed to know how to earn it. Your pre-school child is positively asking you to tell him what does and does not earn approval, so he is ready to learn any social refinement of being human which you will teach him....He knows now that he wants your love and he has learned how to ask for it.”
—Penelope Leach (20th century)
“Perhaps our own woods and fields,—in the best wooded towns, where we need not quarrel about the huckleberries,—with the primitive swamps scattered here and there in their midst, but not prevailing over them, are the perfection of parks and groves, gardens, arbors, paths, vistas, and landscapes. They are the natural consequence of what art and refinement we as a people have.... Or, I would rather say, such were our groves twenty years ago.”
—Henry David Thoreau (1817–1862)
“Sir Walter Raleigh might well be studied, if only for the excellence of his style, for he is remarkable in the midst of so many masters. There is a natural emphasis in his style, like a man’s tread, and a breathing space between the sentences, which the best of modern writing does not furnish. His chapters are like English parks, or say rather like a Western forest, where the larger growth keeps down the underwood, and one may ride on horseback through the openings.”
—Henry David Thoreau (1817–1862)
“In a hierarchy every employee tends to rise to his level of incompetence.”
—Laurence J. Peter (1919–1990)