# rmachine

744 downloads

The machine ("RAM") is equal to Turing machines in its computional power. It has theoretically unlimited memory (but is limited in practice by your computer's memory).

This is a simulator for register machines (the complexity theory version). Here's a short introduction.

The machine ("RAM") is equal to turing machines in its computional power. It has theoretically unlimited memory (in practice limited by your computers memory). Memory cells ("registers") can store integers >=0 of any length. Say the 5th register contains the number 42. You'd write it as c(5)=42. c(0) is also called "assembler" and has an important role, as you'll see later.

The RAM also has a program counter b, initally set to 1 and basically representing the next line to be executed.

The structure of a typical program looks like this:

# Comments go here

# More comments

INPUT 4 6 8 9

(Instructions go here)

END

The "INPUT" line should be found right after the comments. The input will be placed in c(1),c(2) etc. In this example, c(1)=4, c(2)=6, c(3)=8, c(4)=9.

Now, with all that, here's the instruction set. The first line is the instruction itself, the 2nd line explains what it does.

--

LOAD i

c(0):=c(i), b:=b+1

--

CLOAD i

c(0):=i, b:=b+1

--

INDLOAD i

c(0):=c(c(i)), b:=b+1

--

STORE i

c(i):=c(0), b:=b+1

--

INDSTORE i

c(c(i)):=c(0), b:=b+1

--

ADD i

c(0):=c(0)+c(i), b:=b+1

--

CADD i

c(0):=c(0)+i, b:=b+1

--

INDADD i

c(0):=c(0)+c(c(i)), b:=b+1

--

SUB i

c(0): = max(c(0) - c(i),0), b:=b+1

--

CSUB i

c(0): = max(c(0) - i,0), b:=b+1

--

INDSUB i

c(0): = max(c(0) - c(c(i)),0), b:=b+1

--

MUL i

c(0):=c(0)*c(i), b:=b+1

--

CMUL i

c(0):=c(0)*i, b:=b+1

--

INDMUL i

c(0):=c(0)*c(c(i)), b:=b+1

--

DIV i

c(0):=c(0)/c(i), b:=b+1

Note: The decimals will be cut off

--

CDIV i

c(0):=c(0)/i, b:=b+1

Note: The decimals will be cut off

--

INDDIV i

c(0):=c(0)/c(c(i)), b:=b+1

Note: The decimals will be cut off

--

GOTO i

b:=i

--

IF X l GOTO i

X can be one of those:

b:=i if (c(0) X l) is true

(More informally, "IF < 5 GOTO 10" would set b=10 if c(0)

Last updated on

**January 24th, 2008**