On the difference between Turing machine time and random-access machine time
Kenneth W. Regan · 2002
Introduces a model of computation called the block move (BM) model. The BM extends the block transfer (BT) model of Aggarwal, Chandra, and Snir (1987), who studied time complexity under various memory access cost functions ranging from /spl musub 1/(a):=a to /spl musub log/(a):=[log/sub 2/ a]. We show that up to factors of log t in the total running time t, BMs under /spl musub 1/ are equivalent to multitape Turing machines, and BMs under /spl musub log/ are equivalent to log-cost RAMs. We also prove that for any well-behaved /spl mu/, the BM classes D/spl mu/TIME[t(n)] form a tight deterministic time hierarchy. Whether there is any hierarchy at all when /spl mu/ rather than t varies is tied to long-standing open problems of determinism vs. nondeterminism.>