Random Access Machines
Our formal model of a computer will use the following instruction set:
| Instruction | Description |
|---|---|
load x |
Put the value $x$ into $R_0$. |
load Rk |
Copy the value of $R_k$ into $R_0$. |
store Rk |
Copy the value of $R_0$ into $R_k$ |
read Rk |
Copy the value at memory location $R_k$ into $R_0$. |
write Rk |
Copy the value of $R_0$ into memory location $R_k$. |
add Rk |
Add $R_0$ and $R_k$, and put the result in $R_0$. |
jump n |
Set PC to $n$. |
jzero n |
Set PC to $n$, if $R_0$ is zero. |
jpos n |
Set the PC to $n$, if $R_0$ is positive. |
Random Access Machines
Random access machines have the following memory components:
- $PC$ - Program Counter
- $R_x$ - Registers
- $M$ - Memory.
Simulating a TM on a RAM
- Write the contents of the tape to $M$ where the language $\Gamma=\{0,1,2,\ldots,k\}$ with 0 being equal to a blank.
- Write the index of the head pointer to $R_0$
There is a full example of this in the lecture.
Simulating a RAM on a 2 Tape TM
The configuration of a RAM consists of:
- Program Counter
- Contents of Registers
- Indexes and contents of all non-empty memory cells.
Therefore for this RAM:
- PC - 14
- $R_0$ - 3
- $R_1$ - 17
- $R_2$ - 5
- $M$ - 2, 0, 1, 2, 0, …
The configuration would be:
\[(14, 3, 17, 5, (0, 2), (2, 1), (3, 2))\]The TM has a simulation tape and a scratch tape. The simulation tape stores the RAM configuration:
- The TM has a set of states corresponding to each program instruction of the RAM.
- The TM tape is updated according to RAM instructions.
There is a full example of simulating a RAM on a 2 tape Turing machine in the lecture video