LINEAR-TIME AND MEMORY-EFFICIENT COMPUTATION

A realistic model of computation called the block-move (BM) model is d eveloped. The BM regards computation as a sequence of finite transduct ions in memory, and operations are timed according to a memory cost pa rameter mu. Unlike previous memory-cost models, the BM provides a rich theory of linear time, and in contrast to what is known for Turing ma chines (TMs), the BM is proved to be highly robust for linear time. Un der 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 fi nite automaton iterating itself on a single tape, are shown to simulat e each other up to constant factors in running time. The BM is proved to enjoy efficient universal simulation, and to have a tight determini stic time hierarchy. Relationships among BM and TM time complexity cla sses are studied.