Trying to make sense of the operations in a particular Random Access Machine (RAM)

Question

[I couldn't find the right tag for this post]

Following is the description of some random access machine

We use the algorithmic model of the random access machine, sometimes ab- breviated to RAM. It operates on entries that are 0, 1 strings, representing abstract objects (like vertices of a graph) or rational numbers. An instruc- tion can read several (but a fixed number of) entries simultaneously, perform arithmetic operations on them, and store the answers in array positions pre- scribed by the instruction2. The array positions that should be read and written, are given in locations prescribed by the instruction. We give a more precise description. The random access machine has a finite set of variables $z_0, . . . , z_k$ and one array, $f$ say, of length depending on the input. Each array entry is a $0, 1$ string. They can be interpreted as rationals, in some binary encoding, but can also have a different meaning. Initially, $z_0, . . . , z_k$ are set to $0$, and $f$ contains the input. Each instruction is a finite sequence of resettings of one the following types, for $i, j, h ∈ \{1, . . . , k\}$:

(4.1)

$z_i := f (z_j )$;

$f (z_j ) := z_i$;

$z_i := z_j + z_h$;

$z_i := z_j − z_h$;

$z_i := z_j z_h$;

$z_i := z_j /z_h$;

$z_i := z_i + 1$;

$z_i := 1$ if $z_j > 0$ and $z_i := 0$ otherwise.

These include the elementary arithmetic operations: addition, subtraction, multiplication, division, comparison. (One may derive other arithmetic op- erations from this like rounding and taking logarithm or square root, by performing $O(σ + | log ε|)$ elementary arithmetic operations, where σ is the size of the rational number and $ε$ is the required precision.) The instructions are numbered $0, 1, . > . . , t$, and $z1$ is the number of the instruction to be executed. $If z1 > t$ we stop and return the contents of the array $f$ as output.

I know nothing about random access machines and in particular I don't understand what the operations $z_i := f (z_j )$; $f (z_j ) := z_i$; are. Does it mean we take the element at the $z_j$-th index of the array $f$? How are these two operations used in practice in an algorithm?

Answer 1

There exists a wide variety of RAM models that are, to some extent, equivalent. Here, it seems that the operation $f(z_i)=z_j$ means settings the value of the cell at index $z_i$ in the array $f$ to the value of $z_j$ and conversely $z_i=f(z_i)$ means loading the value of the cell $z_i$ in the array $f$ into the variable $z_i$.

I am not sure I understand your question about how to use this in practice? Here the model is quite simplistic but it does look like an assembly language. Maybe you want to look into compilation to understand how to turn a high level language into such a low level language?

To develop on my remark about assembly (if you are used to assembly) you can consider that the $z_1 \dots z_k$ represent the registers while the array $f$ models the RAM memory and $z_1$ can be used to jump to any point in the program.