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.
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.
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
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 .
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 .
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.
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 ^_-