On tape versus core an application of space efficient perfect hash functions to the invariance of space
Cees F. Slot, Peter van Emde Boas · 1984
In Complexity Theory the use of informal estimates can be justified by appealing to the Invariance thesis which states that all standard models of computing devices are sufficiently equivalent. This thesis would require, among others, that a RAM can be simulated by a Turingmachine with constant factor overhead in space. Such a simulation is hard to obtain if the traditional spacemeasure for RAM-space is used. The simulation uses a new method for condensing space, based on perfect hashing.