Tree Normal Form

Tree Normal Form (TNF) is the unique standard Turing machine transition table representation for a class of functionally equivalent TMs (for the purposes of the Busy Beaver problem). TNF is also often used to to describe the process first described by Allen Brady which enumerates all TMs in TNF.

Background

Radó's original definition of a Busy Beaver TM allows any choice of (write symbol, move direction, next state) for every (current state, read symbol) combination. For n-states, m-symbols that leads to $N(n,m)=(2m(n+1))^{mn}$ distinct TMs (Note: there are $n+1$ next states for the n run states and 1 halt state). But for the purposes of searching for Busy Beavers, these contain a lot of redundant TMs. Some notable redundancies are:

1. Permutations: Any permutation of non-start states, non-blank symbols or directions leads to a functionally equivalent TM.
2. Unused transitions: If the TM (when started on a blank tape) does not actually use all transitions, then the behavior of this TM is identical for all choices of those transitions.
3. Halting transitions: Any of the 2m choices for halting transitions lead to the same runtime (and any of $2(m-1)$ lead to same sigma score).
4. Number of halting transitions: Any TM without any halting transitions can (obviously) never halt, so they can be ignored for the purposes of solving the Busy Beaver problem.

In order to (significantly) reduce the search space, TNF requires that the TM satisfy the following:

1. Canonical permutation: All states (and symbols) are used in order when run on a blank tape. The first move direction is Right.
2. Undefined transitions: All unused transitions are marked as blank/undefined ---.
3. Unique halting transition: All halting transitions are of the form 1RZ.
4. Require halting transition: TMs must have at least one undefined (---) or halting (1RZ) transition.

TNF Enumeration

TNF enumeration is a process for enumerating all TMs in TNF by recursively expanding a "family tree" of machines:

• Start with a completely undefined TM of the desired size, this is the root node. Ex ------_------ for BB(2).
• For each unexplored node, run that TM on a blank tape until it reaches an undefined transition (or you give up searching).
• If you reach an undefined transition, then create children nodes from this node for all choices of transitions.
  • One option for transition is always the single halting transition 1RZ.
  • If there is at least one more undefined transition (besides this one being filled in now) then we also allow all combinations of transitions with the following restrictions:
    • The first direction must be Right,
    • The next state may be any previously visited state or the next unvisited one,
    • The write symbol may be any previously used symbol or the next unused one.
• Repeat this on every leaf node (which contains at least one undefined transition).

This enumeration is complete if every leaf node is either a halting TM or an infinite TM that never reaches it's undefined transitions. Unfortunately, there is no programatic way to ensure you are done because that would involve solving the halting problem. Instead it is often helpful to think of TNF enumeration as an iterated process in which the tree is expanded as much as possible early on, but then iteratively refined over time as new leafs are proven to reach undefined transitions.

TNF-1RB

One common additional restriction is that the initial transition is A0→1RB. This is mainly done to exclude A0→0RB TMs. For any TM starting from A0→0RB, the TM starts in state B will have the same exact sigma score and run for exactly one step longer. Many early enumerations used this restriction because they were specifically searching for Σ. It can also be used when searching for the step champion, but requires some post-processing to check for any state permutations that might lead to a few more steps.

Number of TNF TMs

	Total TMs	TNF TMs	TNF-1RB TMs
BB(2)	20,736		41
BB(3)	16,777,216		4,057
BB(4)	25,600,000,000		620,261
BB(5)	63,403,380,965,376		126,891,605
BB(6)	232,218,265,089,212,416		~33,436,000,000