BF busy beaver
- This is still a work in progress. It may be changed in the future.
The goal: given a program length, find the brainfuck program of that length that calls the . command the greatest (finite) number of times.
The tape is considered infinite to the right, starting at the leftmost cell, with cells holding arbitrary non-negative integers. Going left while on the leftmost cell gives undefined behavior, as does decrementing a cell containing 0.
1-9
Exhaustive list of busy beavers 1-9:
1 . 1 2 .. 2 3 ... 3 4 .... 4 5 ..... 5 6 ...... 6 7 ....... 7 8 ........ 8 9 ......... 9 9 +++[-...] 9
Proof: In order for a program to call the . command more times than the number of instructions, it must contain a loop that is entered, calls the . command some number of times, and exits. <, [, ], and - are obviously not useful first instructions. At least initially, . is also not a useful first instruction, as a program beginning with . being better than the ... program of the same length would mean that the same program without the . must also be better than the corresponding ... program. This leaves + and > as the only first instructions that can be useful. Also, the part before the loop must contain a + somewhere. The inside of the loop must contain the . command and some way of exiting the loop. This gives the following possibilities for a program of length 9:
*[******]
The first instruction here would have to be a +. Assuming the loop doesn't contain another loop:
The loop must loop at least twice in order to output at least 9 times. If it loops twice, it must contain 5 .s; the remaining command can't possibly be anything that would make it loop twice. If it loops three times, it must contain 3 .s. The remaining 3 commands are powerless to cause
**[*****]
subproof goes here
***[****]
subproof goes here
****[***]
subproof goes here
*****[**]
subproof goes here