@inproceedings{df7c68e89dc7463ea32beb92788e715d,
title = "On the difference between Turing machine time and random-access machine time",
abstract = "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 musub 1/(a):=a to musub log/(a):=[log2 a]. We show that up to factors of log t in the total running time t, BMs under musub 1/ are equivalent to multitape Turing machines, and BMs under musub 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.",
keywords = "Computational complexity, finite automata, models, random-access machines, simulation, theory of computation, Turing machines",
author = "Regan, \{K. W.\}",
note = "Publisher Copyright: {\textcopyright} 1993 IEEE.; 5th International Conference on Computing and Information, ICCI 1993 ; Conference date: 27-05-1993 Through 29-05-1993",
year = "1993",
doi = "10.1109/ICCI.1993.315406",
language = "English",
series = "Proceedings - ICCI 1993: 5th International Conference on Computing and Information",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "36--40",
editor = "Koczkodaj, \{Waldemar W.\} and Osman Abou-Rabia and Chang, \{Carl K.\}",
booktitle = "Proceedings - ICCI 1993",
address = "United States",
}