Linear Time and Memory-Efficient Computation
Kenneth W. Regan · SIAM Journal on Computing · 1996
A realistic model of computation called the block-move (BM) model is developed. The BM regards computation as a sequence of finite transductions in memory, and operations are timed according to a memory cost parameter $\mu $. Unlike previous memory-cost models, the BM provides a rich theory of linear time, and in contrast to what is known for Turing machines (TMs), the BM is proved to be highly robust for linear time. Under a wide range of $\mu $ parameters, many forms of the BM model, ranging from a fixed-wordsize random-access machine (RAM) down to a single finite automaton iterating itself on a single tape, are shown to simulate each other up to constant factors in running time. The BM is proved to enjoy efficient universal simulation, and to have a tight deterministic time hierarchy. Relationships among BM and TM time complexity classes are studied.