Busy Brain Beaver

Question

Write a brainfuck program of no more than 256 characters that takes as many steps as possible, but does not loop infinitely. The program may not take any input.

More specifically:

• Assume an infinite number of cells to the right.
• A < when at the leftmost cell does nothing.
• A - when cell value is zero sets cell to 255.
• The instructions +-<>. all count as one step when executed.
• When a [ or ] is encountered, it counts as one step. However, if the condition is true and control flow jumps, the corresponding ] or [ does not again count as a step.
• The solution that takes the most steps wins.
• If there is some kind of pattern in your solution, giving a function for how many steps a similar program of length n would take is appreciated but not mandatory.
• To count instructions, you can use this modified interpreter:

Example:

++[-]

The encountered instructions are ++[-]-], and the program ran for 7 steps.

Answer 1

Here's a 41-character program that eventually halts, leaving more than 10↑(10↑28) contiguous cells set equal to 1 (so the number of instructions executed is very much greater than that):

>+>+>+>+[->[>]+[->[>]+[->[>]+[<]+<]+<]+<]

If I'm not mistaken, that's a correct translation of the following program in the BF-variant language that uses a single bit for each memory cell (i.e., cell content 0..1 instead of 0..255, so '+' acts to simply flip the bit-value):

>+>+>+>+[+>[>]+[+>[>]+[+>[>]+[<]+<]+<]+<]

The exact value (the number of adjacent 1-bits) produced by the latter program is

3 * (2 ↑ 118842243771396506390315925503 - 1) + 1.

---

The above program initializes & computes a function that grows like 2↑↑x (in Knuth up-arrow notation). Similar conversion of a variant-BF program that initializes & computes a function that grows like 2↑²³x provides the following 256-character program:

>+>+>+>+>+>+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+

which eventually halts, leaving more than 2↑²³6 adjacent cells set equal to 1 (so the number of steps is enormously more than that).

NB-1: 2↑²³6 is an "inconceivably large" number; e.g., even 2↑⁴6 = 2↑↑↑↑6 already surpasses the first term (3↑↑↑↑3) in the sequence used to compute Graham's number.

NB-2: I think it's likely that 256 characters is enough for a BF program to initialize & compute a function with output much larger than Graham's number — if I find time, maybe I'll try to write one.

NB-3: In case anyone is interested in the origin of the above programs, here are some programming resources for "Brainf*ck F", with various programs written in Python. ("Brainf*ck F", or just "F", is what I called a Turing-complete variant of the Smallf*ck esolanguage.) I just now uploaded these files, which have been offline for several years, and for now the linked webpage is just a "file cabinet" -- see the file Busy_Beavers.txt for a detailed discussion relevant to the above programs.

Answer 2

Here is a nice 39 character one:

-[>-[>-[-[>+<-]<[>+<-]<[>+<-]>>>]<-]<-]

It basically makes a 3 space wide 'sled' that it moves right and decrements by one. Completed in 31,919,535,558 instructions, with the innermost loop executing 256^3 times. I still have plenty of room to extend this pretty far at a rate of 14 characters to another order of magnitude to the run time.

Works on any interpreter with unbounded memory, or with wrapping memory.

I leave it a an exercise to the reader to determine when the improved by 2 loops version will finish:

-[>-[>-[>-[>-[-[>+<-]<[>+<-]<[>+<-]<[>+<-]<[>+<-]>>>>>]<-]<-]<-]<-]

It has now run overnight, and it is over 3,000,000,000 steps. Still has not gotten through a single iteration of the outer loop. Has barely made it through 15% of the second loop.

Answer 3

This programs works in infinte number of cells. Two values are initialized in the begining with ascii values 255. The first value at the first rotation of main loop is splited to 255 cell and they are initialized with 255 each, at the second rotation of main loop the each value in 255 cells again splits up to 255*255 cells, in the same way for 255 rotation of main loop the total cells initialized will be 255^255 . The second value determines how much times the main loop is to be repeated.

>->>-[<<[<]>[[[>]>>>[>]-[<]<<<[<]>-]>]>[>>[>]>+<<[<]<-]>>[>]>-]

Answer 4

This program is almost same as my previous program , difference is that the value determining the outer loop remains fixed in a particular cell so both number of cells initialized and total steps at the end of the program can be increased

->>-<<[>>[>]<[[>>[>]-[<]<-]>>[[<+>-]>]<<[<]<]>>[[<+>-]>]<<[<]<-]

cells initialized at the end of program 255^255

-[>-[>->>[-]-<<[>>[>]<[[>>[>]-[<]<-]>>[[<+>-]>]<<[<]<]>>[[<+>-]>]<<[<]<-]<-]<-]

cells initialized at the end of program 255^255^3

I further modified it to run for even more number of steps.

->>>->>-<<<<<[>>>[>]<[[>>[>]<[[>>[>]-[<]<-]>>[[<+>-]>]<<[<]<]>>[[<+>-]>]<<[<]<-]<[>>>[[<+>-]>]<<[<]]<]>>>>[[<<+>>-]>]<-<<[<]<<-]

it initializes 255^255 cells during first rotation of main 255^(255^255*255) cells during second rotation of main loop 255^{255^(255^255*255)*255} cells during third rotation of main loop in this way loop repeats 255 times