Random Access Machines

Random access machines implement computable functions. They consist of registers containing natural numbers representing instructions and data:

Instructions are executed, starting with the first register, until a stop instruction is reached. A special instruction pointer register holds the register number of the next instruction to execute. The instruction pointer is incremented by one after every instruction except for jump instructions. Here is one possible instruction set:

Instruction	Description
ADDRa Rb Rc	Ra + Rb→ Rc
SUBRa Rb Rc	Ra - Rb→ Rc
ANDRa Rb Rc	Ra ∧ Rb→ Rc
ORRa Rb Rc	Ra ∨ Rb→ Rc
NOTRa Rb	¬Ra→ Rb
SETRa num	num→ Ra
COPYIRa Rb	RRa→ Rb
JUMPnum	num→ IP
JUMPZRa num	If Ra = 0 Then num→ IP
STOP	Stop