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.
Analysis
MBB(7):
Let A(x) = A:[x, 0] A(2x) -> 9x+20 -> A(3x+4) A(2x+1) -> 9x+27 -> halt A(0) -> 20 -> A(4) -> 38 -> A(10) -> 65 -> A(19) -> 108 -> halt
MBB(8):
Let S(z) = F:[0, 2z+1, z] S(2k) -> 44k+19 -> S(5k+2) S(2k+1) -> 4k+2 -> halt A:[0, 0, 0] -> 44 -> S(4) -> 107 -> S(12) -> 283 -> S(32) -> 723 -> S(82) -> 1823 -> S(207) -> 414 -> halt
MBB(9):
Let A(x) = I:[0,x] B(x) = I:[1,x] A(3x) -> 31x+14 -> B(4x+1) A(3x+1) -> 31x+22 -> halt A(3x+2) -> 31x+33 -> A(4x+5) B(3x) -> 31x+13 -> halt B(3x+1) -> 31x+24 -> A(4x+4) B(3x+2) -> 31x+36 -> B(4x+4) A:[0,0] -> 10 -> A(2) -> 33 -> A(5) -> 64 -> A(9) -> 107 -> B(13) -> 148 -> A(20) -> 219 -> A(29) -> 312 -> A(41) -> 436 -> A(57) -> 603 -> B(77) -> 811 -> B(104) -> 1090 -> B(140) -> 1462 -> B(188) -> 1958 -> B(252) -> 2616 -> halt
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)