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) | > 4.493 × 1074 | 0+B_0+C_1-HD_0-EG_0-FI_1+D_2+H_0+A_2-B*
|
| MBB(10) | > 10↑↑4.03 | 0+B_1-AC_2-ED_1+E_1+F_0-DG_2-JH_2+I_1-HE_2-A*
|
| MBB(11) | > 10↑↑17.74 | 0-KB_1-IC_1+D_1+E_2-CF_0-AG_0+H_1-GI_2+J_2+B_0-B*
|
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) = D:[x, 0, y] A(2k, y) --(7k + 6)--> A(3k + 3, y + 1) A(2k + 1, y + 1) --(7k + 5)--> A(3k + 1, y) A(2k + 1, 0) --(3k + 3)--> *:[0, k, 0] A:[0, 0, 0] --(3)--> A(2, 0) --(13)--> A(6, 1) --(27)--> A(12, 2) ... --(2753550047052785432549)--> A(1180092877308336613950, 31) --(4130325070579178148831)--> A(1770139315962504920928, 32) --(6195487605868767223254)--> A(2655208973943757381395, 33) ... --(123361440505394191838159894807429323394336791980165278392551786831696080997)--> A(52869188788026082216354240631755424311858625134356547882522194356441177569, 0) --(79303783182039123324531360947633136467787937701534821823783291534661766355)--> *[0, 26434594394013041108177120315877712155929312567178273941261097178220588784, 0] MBB(9) ≥ 449388104698221698839011045369921106650798313642030657001438652029750007257
MBB(10):
Let A(x) = E:[0, 0, x] A(3k) --(28 × 2^k - 5k - 21)--> A(4 × 2^k - 2) A(3k + 1) --(20 × 2^k - 5k - 16)--> *:[0, 4 × 2^k - 3, 0] A(3k + 2) --(56 × 2^k - 5k - 23)--> A(8 × 2^k - 1) Let t3 = 2^5864062014807 Let t4 = 2^((t3 + 4) / 3) A:[0, 0, 0] --(20)--> A(5) --(84)--> A(15) --(850)--> A(126) --(123145302310681)--> A(17592186044414) --(7 × t3 - 29320310074043)--> A(t3 - 1) --(5 × t4 - 5 / 3 × t3 - 38 / 3)--> *:[0, t4 - 3, 0] MBB(10) ≥ 5 × t4 + 16 / 3 × t3 + 281474976712738 / 3 > 10^^4.03
MBB(11):
Let A(x) = I:[x, 0, 0] A(3k) --> A((20 * 4^k + 1)/3) if k ≥ 1 A(3k + 1) --> A((80 * 4^k + 1)/3) if k ≥ 1 A(3k + 2) --> *:[0, (20 * 4^k - 2)/3, 0] if k ≥ 1 A:[0, 0, 0] --(140)--> A(27) --> A((20 * 4^9 + 1) / 3) = A(1747627) --> A((80 * 4^582542 + 1) / 3) ≡ A(4897384) mod 3^15 --> A((80 * 4^1632461 + 1) / 3) ≡ A(2637523) mod 3^14 --> A((80 * 4^879174 + 1) / 3) ≡ A(813591) mod 3^13 --> A((20 * 4^271197 + 1) / 3) ≡ A(72385) mod 3^12 --> A((80 * 4^24128 + 1) / 3) ≡ A(84526) mod 3^11 --> A((80 * 4^28175 + 1) / 3) ≡ A(35479) mod 3^10 --> A((80 * 4^11826 + 1) / 3) ≡ A(14202) mod 3^9 --> A((20 * 4^4734 + 1) / 3) ≡ A(268) mod 3^8 --> A((80 * 4^89 + 1) / 3) ≡ A(2077) mod 3^7 --> A((80 * 4^692 + 1) / 3) ≡ A(394) mod 3^6 --> A((80 * 4^131 + 1) / 3) ≡ A(235) mod 3^5 --> A((80 * 4^78 + 1) / 3) ≡ A(21) mod 3^4 --> A((20 * 4^7 + 1) / 3) ≡ A(12) mod 3^3 --> A((20 * 4^4 + 1) / 3) ≡ A(6) mod 3^2 --> A((20 * 4^2 + 1) / 3) ≡ A(2) mod 3^1 --> *:[0, (20 * 4^0 - 2) / 3, 0] ≡ *:[0, 0, 0] mod 3^0 MBB(11) > 10^^17.74
Cryptids
MBB(8): Space Needle variants
Through the exhaustive search of the MBB(8) domain, all eight register machines have either been decided, or are equivalent to one of the two following potential cryptids: 0+B_1+C_2-AD_1-EH_2+F_1-DG_0-EB_2-C* and 0+B_1-FC_2-GD_0-EF_1+C_2+A_2-EH_1-B*, which may each be interpreted in the following ways:
0+B_1+C_2-AD_1-EH_2+F_1-DG_0-EB_2-C* Let A(x, y) = D:[x, y, 0] A(x, 0) --(2)--> *:[x, 0, 0] A(x, 2k + 1) --(6k + 6y + 9)--> A(x + k + 1, x + k + 2) A(x, 2k + 2) --(6y + 6)--> A(x + k, k) A:[0, 0, 0] --(3)--> A(1, 1) Needle rules: Let C(x + 3) = A(x, x + 1) = D:[x, x + 1, 0]. Let a and b be non-negative integers satisfying x = (2a + 1) * 2^b. C(x) --> C(2x - a - 2b - 1) if a > 0 C(x) --> *:[2x - 2b - 3, 0, 0] if a = 0 START: C(5)
0+B_1-FC_2-GD_0-EF_1+C_2+A_2-EH_1-B* Let A(x, y) = C:[x, 0, y] A(x, 2k) --(6x + 6k + 5)--> A(x + k + 1, x + k + 1) A(x, 2k + 3) --(6k + 7)--> A(x + k, k) A(x, 1) --(3)--> *:[x, 0, 0] A:[0, 0, 0] --(2)--> A(1, 0) Needle rules: Let C(x + 3) = A(x, x) = C:[x, 0, x]. Let a and b be non-negative integers satisfying x = (2a + 1) * 2^b. C(x) --> C(2x - a - 3b - 1) if a > 0 C(x) --> *:[2x - 3b - 1, 0, 0] if a = 0 START: C(5)
They are similar to the BB(6) cryptid Space Needle, which is also the BMO's 6th problem.
MBB(10): Hydra
Hydra was hand coded into a 10-instruction, 3-register register 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)
MBB(12,2): Convergence of 7 under the 5n + 1 map
The 5n + 1 map has also been hand coded into a 12-instruction, 2-register machine: 0+B_0+C_0+D_0+E_1-IF_1+G_0-HE_0-FJ_0+A_1-KL_0+J_0-H* which can be interpreted the following way:[2]
0+B_0+C_0+D_0+E_1-IF_1+G_0-HE_0-FJ_0+A_1-KL_0+J_0-H* Let A(x + 3) = F:[x, 0] Assume x > 0. A(4) --(10)--> *:[0, 0] A(2k) --(5k - 2)--> A(k) A(2k + 1) --(9k)--> A(5k + 3) A:[0, 0] --(5)--> A(7)