Brainfuck

This article covers the Busy Brain Beaver function BBB(n) counting the maximum number of steps taken by non-interactive right-unbounded Brainfuck programs of length n.

Definition

A non-interactive Brainfuck program has six instructions: move the head left and right, increment and decrement the highlighted cell, and start and end loops. A right-unbounded Brainfuck program only moves to the right of the starting cell, but has access to an unbounded number of cells. Every single instruction takes a single step, including loop tests.

Summary

The following diagram summarizes known values and problems relative to BBB.

Known Values

Lower bounds for small n are established here on a variant of Brainfuck with unbounded cell values, and are identical up to 255.

We include lower bounds for selected n from this golfing challenge.

Tables of Values

Interp(BF,[!])

Interp(BF²)

Erdős–Lagarias conjecture

Interp(BF,[:])

Period 32 Laver table

Interp(Tag(2))

Metainterp(BF)

Interp(BCL)