Branching Beaver - Revision history

Sligocki: /* Champions */ Add multi-symbol champions.

2026-06-14T22:48:26Z

Champions: Add multi-symbol champions.

← Older revision		Revision as of 22:48, 14 June 2026
Line 13:		Line 13:
	{\| class="wikitable"		{\| class="wikitable"
	\|+		\|+
	!n		!Domain
	!~~BrB(n)~~		!Max Steps
	!Champion		!Champion
	!Reference		!Reference
	\|-		\|-
	\| 1		\| BrB(1)
	\| style="text-align: right;" \| = 3		\| style="text-align: right;" \| = 3
	\| <code>1RA1RZ</code>		\| <code>1RA1RZ</code>
	\|		\|
	\|-		\|-
	\| 2		\| BrB(2)
	\| style="text-align: right;" \| = 10		\| style="text-align: right;" \| = 10
	\| <code>1RA0GB_1GA1RZ</code>		\| <code>1RA0GB_1GA1RZ</code>
	\|		\|
	\|-		\|-
	\| 3		\| BrB(3)
	\| style="text-align: right;" \| ≥ 52		\| style="text-align: right;" \| ≥ 52
	\| <code>1RB0GB_0GC1RZ_1GC0RA</code>		\| <code>1RB0GB_0GC1RZ_1GC0RA</code>
	\|		\|
	\|-		\|-
	\| 4		\| BrB(4)
	\| style="text-align: right;" \| ≥ 4636		\| style="text-align: right;" \| ≥ 4636
	\| <code>1RA0GB_1RC1RD_1GA0GC_1RZ0GA</code>		\| <code>1RA0GB_1RC1RD_1GA0GC_1RZ0GA</code>
	\|		\|
			\|-
			\| BrB(2,3)
			\| style="text-align: right;" \| ≥ 68
			\| <code>1RA2GA0BB_1BA2BA1RZ</code>
			<code>1RA2GA0BB_2BA1RZ1BA</code>
			\|
			\|-
			\| BrB(2,4)
			\| style="text-align: right;" \| ≥ 332,372
			\| <code>1RB2RB1GB1RZ_2GB3GA3RA1RA</code>
			\|
	\|}		\|}

Line 44:		Line 55:
	{\| class="wikitable"		{\| class="wikitable"
	\|+		\|+
	!n		!Domain
	!~~BrB_space(n)~~		!Max Space
	!Champion		!Champion
	!Reference		!Reference
	\|-		\|-
	\| 1		\| BrB_space(1)
	\| style="text-align: right;" \| = 2		\| style="text-align: right;" \| = 2
	\| <code>1RA1RZ</code>		\| <code>1RA1RZ</code>
	\|		\|
	\|-		\|-
	\| 2		\| BrB_space(2)
	\| style="text-align: right;" \| = 4		\| style="text-align: right;" \| = 4
	\| <code>1RA0GB_1GA1RZ</code> (and 10 others)		\| <code>1RA0GB_1GA1RZ</code> (and 10 others)
	\|		\|
	\|-		\|-
	\| 3		\| BrB_space(3)
	\| style="text-align: right;" \| ≥ 22		\| style="text-align: right;" \| ≥ 22
	\| <code>1RB1RZ_0GC0BB_1GA0RA</code>		\| <code>1RB1RZ_0GC0BB_1GA0RA</code>
	\|		\|
	\|-		\|-
	\| 4		\| BrB_space(4)
	\| style="text-align: right;" \| ≥ 384		\| style="text-align: right;" \| ≥ 384
	\| <code>1RB0BB_0RC1RZ_0GA1GD_1RC0RA</code>		\| <code>1RB0BB_0RC1RZ_0GA1GD_1RC0RA</code>
	\|		\|
			\|-
			\| BrB_space(2,3)
			\| style="text-align: right;" \| ≥ 20
			\| <code>1RA2GA0BB_1BA2BA1RZ</code>
			<code>1RA2GA0BB_2BA1RZ1BA</code>
			\|
			\|-
			\| BrB_space(2,4)
			\| style="text-align: right;" \| ≥ 5996
			\| <code>1RB2GA3BA0RA_1GB2BB1RA1RZ</code>
			\|
	\|}		\|}

	[[Category:Functions]]		[[Category:Functions]]

Polygon: Added Category:Functions

2026-06-14T08:32:08Z

Added Category:Functions

← Older revision		Revision as of 08:32, 14 June 2026
Line 69:		Line 69:
	\|		\|
	\|}		\|}

			[[Category:Functions]]

Sligocki: Created page with "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 wikipedia: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 childre..."

2026-06-14T06:23:51Z

Created page with "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 wikipedia: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 childre..."

New page

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 [[wikipedia:Bethe lattice|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 ===
{| class="wikitable"
|+
!n
!BrB(n)
!Champion
!Reference
|-
| 1
| style="text-align: right;" | = 3
| <code>1RA1RZ</code>
|
|-
| 2
| style="text-align: right;" | = 10
| <code>1RA0GB_1GA1RZ</code>
|
|-
| 3
| style="text-align: right;" | ≥ 52
| <code>1RB0GB_0GC1RZ_1GC0RA</code>
|
|-
| 4
| style="text-align: right;" | ≥ 4636
| <code>1RA0GB_1RC1RD_1GA0GC_1RZ0GA</code>
|
|}

=== 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.

{| class="wikitable"
|+
!n
!BrB_space(n)
!Champion
!Reference
|-
| 1
| style="text-align: right;" | = 2
| <code>1RA1RZ</code>
|
|-
| 2
| style="text-align: right;" | = 4
| <code>1RA0GB_1GA1RZ</code> (and 10 others)
|
|-
| 3
| style="text-align: right;" | ≥ 22
| <code>1RB1RZ_0GC0BB_1GA0RA</code>
|
|-
| 4
| style="text-align: right;" | ≥ 384
| <code>1RB0BB_0RC1RZ_0GA1GD_1RC0RA</code>
|
|}