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