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

Domain	Max Steps	Champion	Reference
BrB(1)	= 3	1RA1RZ
BrB(2)	= 10	1RA0GB_1GA1RZ
BrB(3)	≥ 52	1RB0GB_0GC1RZ_1GC0RA
BrB(4)	≥ 4636	1RA0GB_1RC1RD_1GA0GC_1RZ0GA
BrB(2,3)	≥ 68	1RA2GA0BB_1BA2BA1RZ 1RA2GA0BB_2BA1RZ1BA
BrB(2,4)	≥ 332,372	1RB2RB1GB1RZ_2GB3GA3RA1RA

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.

Domain	Max Space	Champion	Reference
BrB_space(1)	= 2	1RA1RZ
BrB_space(2)	= 4	1RA0GB_1GA1RZ (and 10 others)
BrB_space(3)	≥ 22	1RB1RZ_0GC0BB_1GA0RA
BrB_space(4)	≥ 384	1RB0BB_0RC1RZ_0GA1GD_1RC0RA
BrB_space(2,3)	≥ 20	1RA2GA0BB_1BA2BA1RZ 1RA2GA0BB_2BA1RZ1BA
BrB_space(2,4)	≥ 5996	1RB2GA3BA0RA_1GB2BB1RA1RZ