What constitutes one operation/cycle/move in the RAM model?

Question

I saw a RAM model diagram that displayed an input tape, output tape, the program (read-only), the instruction pointer, and the memory registers. However, when I look at questions of time complexity, it is relevant how much time the program needs to spend on one action. Say you want to read one integer symbol from the read tape, add it to an integer from a memory register, and then squish the result into the write tape cell, and then move the read head one to the right and the write head one to the left. How much time or how many moves did I just waste?

Answer 1

Complexity is usually defined using Turing machine model to avoid the issue of the amount of resources taken during a complicated operation like adding integers.

You can use different notation of complexity of a RAM machine and that depends on what you are trying to do. If you want to be able to compare it with standard complexity classes which are defined using Turing machines then you should assign to each operation an amount of resource usage that a Turing machine would require to simulate that operation. The answer also depends on what kind of operations your RAM machine supports.

The standard RAM model consists of a finite control where a program is stored, one or more accumulator registers $Acc$, an instruction counter, and an infinite collection of memory registers $R[0], R[1],\ldots$. The instruction can be divided to four categories:

• flow-control: unconditional jump, Accept, Reject, Halt, conditional jumps (the "conditions" are simple like $Acc = 0?$);

• input/output: read, write;

• data-transfer between accumulator and memory: load, save;
• arithmetic: $Acc := 0$, add $R[i]$ to $Acc$;

Two more common costs are uniform and logarithmic. The two are related quadraticaly for the instruction set above (i.e. to convert the uniform to logarithmic you need to square the running time). Logarithmic means taking cost to be logarithm (i.e. the number of bits) of the inputs to the operation whereas uniform means that all operations are considered to take unit time.