3
$\begingroup$

It is a well-known result that Turing machines and random access machines (RAMs) can simulate each other with a polynomial slowdown.

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 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 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?

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – Marzio De Biasi Jun 23 '16 at 15:17
  • $\begingroup$ 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). $\endgroup$ – Antonio E. Porreca Jun 23 '16 at 16:34
  • $\begingroup$ 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) $\endgroup$ – Marzio De Biasi Jun 24 '16 at 6:53
2
$\begingroup$

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.

For simulations between RAM and Turing machines see Theorems 2.5 and 2.6, pp. 26--27. It also contains pointers to historic references.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Antonio E. Porreca Jun 24 '16 at 9:08
1
$\begingroup$

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, 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.