Unit-Cost Pointers versus Logarithmic-Cost Addresses

ABSTRACT The LISP Machine (LM) is a high-level model of computation using a linked memory structure. The Hierarchical Memory Model (HMM) has a random access memory but takes into account the cost of memory access. We show that the HMM can be simulated by the LM in real time. On the other hand, for simulating an on-line LM program of time t and space s by the HMM we prove time bounds of O(t log s). These are shown to be tight for data types which are incompressible-- an informationtheoretic notion, allowing for models which handle a variety of data types. 0. Introduction What should be the capabilities of an abstract "computer " for theoretic study? This question is of fundamental importance in complexity theory. The quest for bounds on the complexity of problems calls for a machine model which is both realistic and theoretically accessible. The random access machine [2,6,10] seems to be the machine model in widest use. The selection of the data type that the machine should use--its data items and the primitive functions that may be applied to them--is an important decision, and since the first use of the RAM for complexity analysis, authors have considered this question, attempting to justify or evaluate possible choices [e.g. 6,8,11]