On the difference between Turing machine time and random-access machine time

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 μ₁(a):=a to μ _log(a):=[log₂ a]. We show that up to factors of log t in the total running time t, BMs under μ₁ are equivalent to multitape Turing machines, and BMs under μ_log are equivalent to log-cost RAMs. We also prove that for any well-behaved μ, the BM classes DμTIME[t(n)] form a tight deterministic time hierarchy. Whether there is any hierarchy at all when μ rather than t varies is tied to long-standing open problems of determinism vs. nondeterminism