Register machine
Register machines, also known as Minsky machines, are a Turing-complete model of computation.
Register machines contain a set of instructions and a set of registers. The instructions are labelled A, B, C, and so on. The registers are numbered 0, 1, 2, and so on. There are 2 types of instructions:
- inc(c, n) adds 1 to the register c then jumps to instruction n.
- dec(c, n, m) jumps to instruction m if register c equals 0, else subtract 1 to the register c then jump to instruction n.
The program halts if it reaches an undefined instruction. Here we label an undefined instruction with *.
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 instructions and r registers when started in instruction A and all registers initialized to 0. MBB(n) = MBB(n,n) (unlimited registers).
| Domain | Halting Time | Champion |
|---|---|---|
| MBB(1) | 1 | 0+*
|
| 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*
|
| MBB(7) | ≥231 | 0+B_0+C_0+D_1-GE_1+F_0-EC_1-A*
|
| MBB(8) | ≥3394 | 0+B_0+C_1-GD_1+E_0-DF_2-HG_2+A_2-D*
|
| MBB(9) | ≥9870 | 0+B_0+C_0+D_1-IE_1+F_0-GI_0-HC_0-E*_0+A
|
MBB(9) is likely unoptimal.
Cryptids
No Cryptids have been found via exhaustive search, but Hydra has been hand coded into a 10-instruction, 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)