Register machine
Register machines, also known as Minsky machines, are a Turing-complete model of computation.
Register machines contain a set of instructions and at least 2 registers.
Each instruction in a program has a number, starting with 1.
There are 2 types of instructions:
- inc(c, n) add 1 to the register c then jumps to instruction n.
- dec(c, n, m) jumps to instruction m if register c equal 0 else subtract 1 to the register c then jump to instruction n.
The program halt if it reaches an undefined instruction. Here we represent it with the letter H.
Register Busy Beaver
The Register Busy Beaver function, denoted MBB(n,r), returns the maximum number of instructions executed by a register machine with n states and r registers when started in state A and all registered initialized to 0. MBB(n) = MBB(n,n) (unlimited registers).
| Domain | Halting Time | Champion |
|---|---|---|
| MBB(1) | 1 | 0+Z
|
| MBB(2) | 3 | 0+B_0-B*
|
| MBB(3) | 5 | 0+B_0+C_0-C*
|
| MBB(4) | 10 | 0+B_1+C_0-BD_1-C*
|
| MBB(5) | 24 | 0-DB_0+C_1-ED_1+A_1-B*
|
| MBB(6) | 49* | 0+B_1-FC_1+D_0-CE_0+A_1-A*
|
Entries in the Halting Time column marked with * are only proved to be a lower bound, not the actual value of MBB(n).
Cryptids
No Cryptids have been found via exhaustive search, but Hydra has been hand coded into a 10-state, 3-register Minsky machine: 0-BF_1+C_1+D_0-EH_1+A_2+G_2+I_2-I*_0+J_1-IA which can be interpreted the following way:[1]
Let S(h,w) = A:[h-3,0,w] Start: A:[0,0,0] = S(3,0) S(2k,0) = A:[2k-3,0,0] -> Halt S(2k,w+1) = A:[2k-3,0,w+1] -> A:[3k-3,0,w] = S(3k,w) S(2k+1,w) = A:[2k-2,0,w] -> A:[3k-2,0,w+2] = S(3k+1,w+2)