<p>There exists a wide variety of RAM models that are, to some extent, equivalent. Here, it seems that the operation <span class="math-container">$f(z_i)=z_j$</span> means settings the value of the cell at index <span class="math-container">$z_i$</span> in the array <span class="math-container">$f$</span> to the value of <span class="math-container">$z_j$</span> and conversely <span class="math-container">$z_i=f(z_i)$</span> means loading the value of the cell <span class="math-container">$z_i$</span> in the array <span class="math-container">$f$</span> into the variable <span class="math-container">$z_i$</span>.</p>
<p>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?</p>
<p>To develop on my remark about assembly (if you are used to assembly) you can consider that the <span class="math-container">$z_1 \dots z_k$</span> represent the registers while the array <span class="math-container">$f$</span> models the RAM memory and <span class="math-container">$z_1$</span> can be used to jump to any point in the program.</p>

CC BY-SA 4.0
2022-12-21T08:10:39.547Z
I think this answers my question, thank you very much. I just thought that $z_1,\ldots, z_k$  beeing the registers is kind of weird since $z_i=f(z_j)$ means that $z_i$ is the register but $z_j$ is the **index** of the register in the RAM. Don't you think it is weird too? Also I thought a program returns some result and in this case it returns the full RAM, which gets me a bit confused.
roi_saumon
CC BY-SA 4.0
2022-12-22T08:43:38.860Z
If you consider a standard programming language, when you have variables $a,b,c$ and an array $f$, you do write stuff like $f[a] = b$ and $a=f]b]$. Here it might feel weird because you have parenthesis instead of brackets but otherwise it can be read as a standard program.
Louis
CC BY-SA 4.0
2022-12-20T16:55:47.760Z
2022-12-20T16:55:47.760Z
Louis
<p><strong>[I couldn't find the right tag for this post]</strong></p>
<p>Following is the description of some random access machine</p>
<blockquote>
<p>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
<span class="math-container">$z_0, . . . , z_k$</span> and one array, <span class="math-container">$f$</span> say, of length depending on the
input. Each array entry is a <span class="math-container">$0, 1$</span> string. They can be interpreted as
rationals, in some binary encoding, but can also have a different
meaning. Initially, <span class="math-container">$z_0, . . . , z_k$</span> are set to <span class="math-container">$0$</span>, and <span class="math-container">$f$</span> contains the
input. Each instruction is a finite sequence of resettings of one the
following types, for <span class="math-container">$i, j, h ∈ \{1, . . . , k\}$</span>:</p>
<p>(4.1)</p>
<p><span class="math-container">$z_i := f (z_j )$</span>;</p>
<p><span class="math-container">$f (z_j ) := z_i$</span>;</p>
<p><span class="math-container">$z_i := z_j + z_h$</span>;</p>
<p><span class="math-container">$z_i := z_j − z_h$</span>;</p>
<p><span class="math-container">$z_i := z_j z_h$</span>;</p>
<p><span class="math-container">$z_i := z_j /z_h$</span>;</p>
<p><span class="math-container">$z_i := z_i + 1$</span>;</p>
<p><span class="math-container">$z_i := 1$</span> if <span class="math-container">$z_j &gt; 0$</span> and <span class="math-container">$z_i := 0$</span> otherwise.</p>
<p>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 <span class="math-container">$O(σ + | log ε|)$</span> elementary
arithmetic operations, where σ is the size of the rational number and
<span class="math-container">$ε$</span> is the required precision.) The instructions are numbered <span class="math-container">$0, 1, .
&gt; . . , t$</span>, and <span class="math-container">$z1$</span> is the number of the instruction to be executed.
<span class="math-container">$If z1 &gt; t$</span> we stop and return the contents of the array <span class="math-container">$f$</span> as
output.</p>
</blockquote>
<p>I know nothing about random access machines and in particular I don't understand what the operations <span class="math-container">$z_i := f (z_j )$</span>; <span class="math-container">$f (z_j ) := z_i$</span>; are. Does it mean we take the element at the <span class="math-container">$z_j$</span>-th index of the array <span class="math-container">$f$</span>? How are these two operations used in practice in an algorithm?</p>

CC BY-SA 4.0
2022-12-20T18:49:47.807Z
We require you to provide proper attribution for the source of all copied material: https://cstheory.stackexchange.com/help/referencing.  Please [edit] your post accordingly.
D.W.
CC BY-SA 4.0
2022-12-20T18:51:13.340Z
What research have you done?  What sources have you consulted?  Have you read https://en.wikipedia.org/wiki/Random-access_machine?  Have you consulted the references listed there?
D.W.
<turing-machines>
Trying to make sense of the operations in a particular Random Access Machine (RAM)
roi_saumon
# Trying to make sense of the operations in a particular Random Access Machine (RAM)

(Asked by: username_0 on 2022-12-20)

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

**Tags:** turing-machines
> **Comments:**
> **username_1**: We require you to provide proper attribution for the source of all copied material: https://cstheory.stackexchange.com/help/referencing.  Please [edit] your post accordingly.  
> **username_1**: What research have you done?  What sources have you consulted?  Have you read https://en.wikipedia.org/wiki/Random-access_machine?  Have you consulted the references listed there?  

---

## 1 answers

### Answer by username_2 on 2022-12-20. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_0**: I think this answers my question, thank you very much. I just thought that $z_1,\ldots, z_k$  beeing the registers is kind of weird since $z_i=f(z_j)$ means that $z_i$ is the register but $z_j$ is the **index** of the register in the RAM. Don't you think it is weird too? Also I thought a program returns some result and in this case it returns the full RAM, which gets me a bit confused.  
> **username_2**: If you consider a standard programming language, when you have variables $a,b,c$ and an array $f$, you do write stuff like $f[a] = b$ and $a=f]b]$. Here it might feel weird because you have parenthesis instead of brackets but otherwise it can be read as a standard program.  

---

