Branching Beaver

The Branching Beaver (BrB(n,m)) is a Busy Beaver Function for Trivalent Turing Machines (TTM).

A Trivalent Turing Machine is a Turing machine with the tape replaced by a 3-regular Bethe lattice. This is a graph where every node has exactly 3 neighbors. Like with traditional TM tapes, this branching tape is infinite and has no cycles. It can be thought of as an infinite binary tree with no root node (every node has 2 children and one parent node) however, due to our coloring described below, all 3 directions will be symmetric.

We 3-color the edges of the graph so that each node is adjacent to one Red, one Green and one Blue edge. Instead of moving Left/Right, the TM moves Red/Green/Blue which means crossing the edge of that color. Thus unlike in traditional TMs moving in the same color twice in a row brings you back to where you started.

BrB(n,m) is the max runtime (number of steps) for all halting n-state, m-symbol TTMs. As with BB we use the convention that BrB(n) = BrB(n,2).

We use a variation of Standard Text Format replacing R/L directions with R/G/B.

Champions

Step Champions

n	BrB(n)	Champion	Reference
1	= 3	1RA1RZ
2	= 10	1RA0GB_1GA1RZ
3	≥ 52	1RB0GB_0GC1RZ_1GC0RA
4	≥ 4636	1RA0GB_1RC1RD_1GA0GC_1RZ0GA

Space Champions

Analogous to the Maximum Space Function for traditional TMs, we will defined the space used by a halting TTM as the number of nodes that it reads (number of nodes visited ignoring the final halting transition move). Let BrB_space(n,m) be the maximum space used for all halting n-state, m-symbol TTMs.

n	BrB_space(n)	Champion	Reference
1	= 2	1RA1RZ
2	= 4	1RA0GB_1GA1RZ (and 10 others)
3	≥ 22	1RB1RZ_0GC0BB_1GA0RA
4	≥ 384	1RB0BB_0RC1RZ_0GA1GD_1RC0RA