Computational Complexity of Multitape Turing Machines and Random Access Machines
Takumi Kasai · Publications of the Research Institute for Mathematical Sciences · 1977
In recent years there has been an increasing interest in analyzing the computational complexity of programs. The multitape Turing machine has become the standard model used for evaluating time and storage complexity, even though such machines are not much like any existing computers. Some authors, however, implement their algorithms not on Turing machines but on random access machines. In 1972 Cook introduced a formal model of a random access machine. This model is closer to real computer, for real computers calculate the address of desired storage cell within a short time before fetching its content.