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) | ≥ 3,394 | 0+B_0+C_1-GD_1+E_0-DF_2-HG_2+A_2-D*
|
| MBB(9) | ≥ 674,505,781,904,690,510,274,053 | 0+B_1-FC_2+D_0-EF_1+D_0+G_0+H_1-AI_2-E*
|
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, y) = F:[0, x, y] A(2k, y + 1) --(11k + 10)--> A(3k + 3, y) A(2k, 0) --(5k + 4)--> *:[3k + 2, 0, 0] A(2k + 1, y) --(11k + 13)--> A(3k + 3, y + 1) A:[0, 0, 0] —(6)—> A(1, 1) —(13)—> A(3, 2) —(24)—> A(6, 3) ... —(1.498.382.217)—> A(408.649.695, 12) —(2.247.573.330)—> A(612.974.544, 13) —(3.371.360.002)—> A(919.461.819, 12) ... —(122.132.734.172.042.726.140.513)—> A(33.308.927.501.466.198.038.322, 1) —(183.199.101.258.064.089.210.781)—> A(49.963.391.252.199.297.057.486, 0) —(124.908.478.130.498.242.643.719)—> *:[74.945.086.878.298.945.586.231, 0, 0] (674.505.781.904.690.510.274.053 steps total or whatever)
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)