BF busy beaver

From Esolang
Jump to: navigation, search
This is a work in progress, obviously; I'm saving here so I don't lose anything.

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