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 |
Unconfirmed
these ones are NOT proven to be the busy beavers. these are candidates.
| Length | Program | Time |
|---|---|---|
| 5 | +A+B+B-A1-B3 | 16 |
| 6 | -A4+A-B1+B+B-A0 | 37 |
| 7 | +A+A-B5+B-A3+A-B0 | 215 |
| 8 | +A-B7+A+B+B+B-A3-B0 | 394 |
Proof
I ran all of the programs for 1000 steps with some C++ code and if they did not halt in 1000 steps we pass them to AProVE using selenium and some terrible python code.