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]

Start: F:[0, 9, 4] = S(4)
S(2k) = S(5k+2)
S(2k+1) = Halt

S(4) -> S(12) -> S(32) -> S(82) -> S(207) -> 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)