Minsky machine busy beaver

Definition

+X means increment the X register (and counts as a step)

-Yn means if the Y register is nonzero, Decrement it and jump to n (zero-indexed). (counts as a step regardless of whether the register was 0)

All the below tables are for 2 registers A and B. also, if there are multiple programs with the same time we only list one.

Confirmed

Length	Program	Time
1	+A	1
2	+A -A1	3
3	+A +B -A1	5
4	+A +B -A1-B2	10
5	+A +B +B -A1-B3	16
6	-A4+A -B1+B +B -A0	37

The ones for three registers are the same.

Proof

For 1-5 instructions

I ran all of the programs for 1000 steps and if they did not halt in 1000 steps we pass them to AProVE using selenium and some terrible python code.

this time as C code and not a TRS.

For 6-7 with 3 registers

I built a simple decider, i call it DIVERGE. here is the psuedocode.

run the minsky machine for 200 steps. keep a history of state-A-B-C tuples.
Return the time it took to halt if it halted.

look at the last tuple

now, search all tuples with the same state and all registers less than or equal.

then, check if the block of states from the last to the new tuples position is the same as the one ending at 
the new tuples position with the same length.
If so return UNHALT.

if all tuples exhausted, return UNSURE.

Example:

+C +A +B -B1
 0  1  2  3

History:
         
A 0011122233
B 0001001001
C 0111111111
S 0123123123
      __„‾‾”
        ↑  ↑
    Other  Last

(2,1,1) <= (3,1,1)
"123" == "123"
UNHALT