Register Machine Interpreter

A register machine is a simple programmable machine to describe any function that is computable. You can program them here!

Your code will have 3 second to complete execution. This might not seem like a lot of time, but it should be enough for small inputs even on complex programs.

Usage

Registers can be initialised by writing lines of the form:

Register = Value

Next is the syntax for two types of instructions. Note, that the first state can be called either 'S' or '1'.

State: Register + Next-State
State: Register - Next-State e Next-State

Next state can either be a state mentioned somewhere, or . (full stop) which indicates halt. State names can be any lower or upper case characters or numbers. Register names can be any lower or uppercase letters.

Examples

Square Function

This example calculates f(A) = A^2

A = 6
1: A - 2 e N
2: B + 3
3: K + 1
N: B - N1 e M
N1: C + N2
N2: D + N
# Move D into B
M: D - M1 e O
M1: B + M
O: K - O1 e .
O1: C - O2 e N
O2: A + O1

Division Function

This example calculates N = QD + R.

# Calculates integer division N = QD + R, where N and D are given.
# e.g. for 16/5: 16 = 5 * 3 + 1

# Q contains the result of division (quotient)
Q = 0
# R contains the remainder of division
R = 0
# N contains the numerator
N = 16
# D contains the denominator
D = 5

S: D - M1 e F
M1: D + M2
M2: D - M3 e M5
M3: R + M4
M4: N - M2 e F
M5: Q + M6
M6: R - M7 e M2
M7: D + M6
F: R - . e .

Primality Test

This example tells us if A is prime or not, and if it is not, what is the biggest divisor.

A = 101
P = 1
# A => N = A, H = A / 2
1: A - 2 e T
2: N + 3
3: A - 4 e T
4: N + 5
5: H + 1
# Check that H is > 1
T: H - T1 e .
T1: H - T2 e .
T2: H + T3
T3: H + R
# N => A = N, B = N
R: N - 6 e U
6: A + 7
7: B + R
# B => N = B
U: B - 8 e V
8: N + U
# H => B = H, C = H
V: H - 9 e W
9: B + 10
10: C + V
#  C => H = C
W: C - 11 e X
11: H + W
# A -- B
X: B - 12 e Z
12: A - X e 13
13: B + Z
# Check A
Z: A - 14 e 16
# A has remainder
14: A + V
# Check B
16: B - 17 e 25
# B has remainder
# Clear B
17: B - 17 e 18
18: H - T e .
# Both a and b were zero
25: P - . e .

Implementation

Sorry, error handling isn't very good. If a line doesn't parse correctly, it will tell you that much..

This register machine interpreter is written by Samuel Williams in Ruby.

More information

For more information about register machine programs please see Wikipedia. Actually, this isn't a very relevant article to the specific model used here... oh well ^_-

comments powered by Disqus