# Characterisation of P in terms of register machines

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?

• 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) Commented Jun 23, 2016 at 15:17
• 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). Commented Jun 23, 2016 at 16:34
• 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) Commented Jun 24, 2016 at 6:53