Minsky machine busy beaver
Jump to navigation
Jump to search
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 |
Proof
I ran all of the programs for 1000 steps and if they did not halt in 1000 stpes we pass them to AProVE using selenium and some terrible python code.
this time as C code and not a TRS.