<p>I was finally able to find a reference (not necessarily the oldest one) for the efficient simulation of Turing machines by means of RAMs without indirect addressing (nor binary shift):</p>

<blockquote>
  <p>Takumi Kasai, <a href="https://www.jstage.jst.go.jp/article/kyotoms1969/13/2/13_2_469/_pdf" rel="nofollow">Computational complexity of multitape Turing machines and random access machines</a>, Publications of the Research Institute for Mathematical Sciences 13, 469–496, Kyoto University, 1977.</p>
</blockquote>

<p>This random access machine model is called a RAMR in this paper. A multistack machine is simulated by keeping a pair of integers for each stack, which allows a fast implementation of the usual stack operations. A multitape Turing machine can thus be simulated by a RAMR in quadratic time (under the logarithmic cost model). Furthermore, this result applies to any Turing machine runtime, not just polynomial time.</p>

CC BY-SA 3.0
2016-06-24T09:19:55.707Z
2016-06-24T09:19:55.707Z
Antonio E. Porreca
<p>The classic reference for these kind of results is the survey by Peter van Emde Boas, "Machine Models and Simulations", the first chapter of <a href="https://books.google.ca/books?id=-X39_rA3VSQC" rel="nofollow">Handbook of Theoretical Computer Science, Vol. A</a>.</p>

<p>For simulations between RAM and Turing machines see <a href="https://books.google.ca/books?id=-X39_rA3VSQC&amp;pg=PA26" rel="nofollow">Theorems 2.5 and 2.6, pp. 26--27</a>. It also contains pointers to historic references. </p>

CC BY-SA 3.0
2016-06-24T09:08:47.950Z
Thanks, but after having looked at the sources cited by Theorem 2.5 it looks like all results require a non-constant number of registers and indirect addressing.
Antonio E. Porreca
CC BY-SA 3.0
2016-06-23T17:20:31.677Z
2016-06-23T17:20:31.677Z
Kaveh
<p>It is a well-known result that Turing machines and random access machines (RAMs) can <a href="http://dx.doi.org/10.1016/S0022-0000(73)80029-7" rel="nofollow">simulate each other with a polynomial slowdown</a>.</p>

<p>It is relatively straightforward to prove that indirect addressing and binary shift (or, equivalently, division by two) are actually redundant when working in polynomial time, i.e., that polynomial-time Turing machines are equivalent to polynomial-time <a href="http://goodmath.blogspot.it/2006/05/minsky-machine.html" rel="nofollow">Minsky-like register machines</a> with a constant number of registers, augmented with constant-time addition and subtraction instruction (rather than just increment and decrement).</p>

<p>This can be showed by encoding the sequence of symbols on the tape of the Turing machine as a single large integer stored in one of the registers; the individual symbols can be accessed by performing multiplications and divisions (implemented via repeated doubling).</p>

<p>(Incidentally, register machines without constant-time addition and subtraction are <a href="http://dx.doi.org/10.1007/BF01694011" rel="nofollow">provably slower</a> than Turing machines on certain problems.)</p>

<p>I have the feeling that this result must have been published a long time ago, but I seem unable to find it in the literature. Does anyone know a reference (possibly the first published one) for it?</p>

CC BY-SA 3.0
2016-06-23T15:17:37.263Z
After a few Google searches :-) 1) Holger Petersen, Efficient Computation by Three Counter Machines, 2015 ; 2) Paragraph "Tractability is also robust" in the book "Algorithmics:The Spirit of Computing" by David Harel,Yishai A. Feldmanm, 1987  (there is also a paragraph about Turing machines vs Counter programs)
Marzio De Biasi
CC BY-SA 3.0
2016-06-23T16:34:12.287Z
Thanks, but 1) the results by Petersen are polynomial-time with respect to the value of the input (rather than its length in binary notation) and 2) the results mentioned by Harel require multiplying and dividing by 10 (decimal shifts) as atomic operations: I was probably unclear about that, but the register machine I would like to use does not have those operations (I updated the question to make that explicit).
Antonio E. Porreca
CC BY-SA 3.0
2016-06-24T06:53:47.777Z
In 2) I had in mind the statement: "... Careful inspection shows
that if both models involved in such a reduction deal with numbers (or whatever representation of them the model supports) in a nonunary fashion, then all these reductions take polynomial time ..." ... but perhaps there is no reference with only +/- in constant time (but as you said it is straightforward to build "constant time" modulo operation if they are available)
Marzio De Biasi
<cc.complexity-theory><reference-request><turing-machines><ho.history-overview><machine-models>
Characterisation of P in terms of register machines
Antonio E. Porreca
# Characterisation of P in terms of register machines

(Asked by: username_0 on 2016-06-23)

It is a well-known result that Turing machines and random access machines (RAMs) can [simulate each other with a polynomial slowdown](http://dx.doi.org/10.1016/S0022-0000(73)80029-7).

It is relatively straightforward to prove that indirect addressing and binary shift (or, equivalently, division by two) are actually redundant when working in polynomial time, i.e., that polynomial-time Turing machines are equivalent to polynomial-time [Minsky-like register machines](http://goodmath.blogspot.it/2006/05/minsky-machine.html) with a constant number of registers, augmented with constant-time addition and subtraction instruction (rather than just increment and decrement).

This can be showed by encoding the sequence of symbols on the tape of the Turing machine as a single large integer stored in one of the registers; the individual symbols can be accessed by performing multiplications and divisions (implemented via repeated doubling).

(Incidentally, register machines without constant-time addition and subtraction are [provably slower](http://dx.doi.org/10.1007/BF01694011) than Turing machines on certain problems.)

I have the feeling that this result must have been published a long time ago, but I seem unable to find it in the literature. Does anyone know a reference (possibly the first published one) for it?

**Tags:** cc.complexity-theory, reference-request, turing-machines, ho.history-overview, machine-models
> **Comments:**
> **username_1**: After a few Google searches :-) 1) Holger Petersen, Efficient Computation by Three Counter Machines, 2015 ; 2) Paragraph "Tractability is also robust" in the book "Algorithmics:The Spirit of Computing" by David Harel,Yishai A. Feldmanm, 1987  (there is also a paragraph about Turing machines vs Counter programs)  
> **username_0**: Thanks, but 1) the results by Petersen are polynomial-time with respect to the value of the input (rather than its length in binary notation) and 2) the results mentioned by Harel require multiplying and dividing by 10 (decimal shifts) as atomic operations: I was probably unclear about that, but the register machine I would like to use does not have those operations (I updated the question to make that explicit).  
> **username_1**: In 2) I had in mind the statement: "... Careful inspection shows that if both models involved in such a reduction deal with numbers (or whatever representation of them the model supports) in a nonunary fashion, then all these reductions take polynomial time ..." ... but perhaps there is no reference with only +/- in constant time (but as you said it is straightforward to build "constant time" modulo operation if they are available)  

---

## 2 answers

### Answer by username_0 on 2016-06-24. Score: 1 | Accepted answer

I was finally able to find a reference (not necessarily the oldest one) for the efficient simulation of Turing machines by means of RAMs without indirect addressing (nor binary shift):

> Takumi Kasai, [Computational complexity of multitape Turing machines and random access machines](https://www.jstage.jst.go.jp/article/kyotoms1969/13/2/13_2_469/_pdf), Publications of the Research Institute for Mathematical Sciences 13, 469–496, Kyoto University, 1977.

This random access machine model is called a RAMR in this paper. A multistack machine is simulated by keeping a pair of integers for each stack, which allows a fast implementation of the usual stack operations. A multitape Turing machine can thus be simulated by a RAMR in quadratic time (under the logarithmic cost model). Furthermore, this result applies to any Turing machine runtime, not just polynomial time.


---

### Answer by username_2 on 2016-06-23. Score: 2

The classic reference for these kind of results is the survey by Peter van Emde Boas, "Machine Models and Simulations", the first chapter of [Handbook of Theoretical Computer Science, Vol. A](https://books.google.ca/books?id=-X39_rA3VSQC).

For simulations between RAM and Turing machines see [Theorems 2.5 and 2.6, pp. 26--27](https://books.google.ca/books?id=-X39_rA3VSQC&pg=PA26). It also contains pointers to historic references.

> **Comments:**
> **username_0**: Thanks, but after having looked at the sources cited by Theorem 2.5 it looks like all results require a non-constant number of registers and indirect addressing.  

---

