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 describe the process for enumerating all TMs in Tree Normal Form. This process was first introduced by Allen Brady in his 1964 PhD dissertation and thus it has been called Brady's algorithm.

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 next state may be any previously visited state or the next unvisited state.
    • The write symbol may be any previously used symbol or the next unused symbol.
    • If we are expanding the first transition of the machine, the direction must be Right.
• 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 its undefined transitions. Unfortunately, there is no programmatic way to ensure you are done because that would require 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 that starts in state B instead will have the same exact Σ score and run for exactly one step less. By iterating this process at most $n-1$ times, any $n$-state A0→0RB machine can be transformed into a corresponding A0→1RB machine with the same Σ score and (at most) $n-1$ shorter runtime.

Many early enumerations chose to use the A0→1RB 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 the near-champions for any state permutations that might lead to a few more steps.

Number of TNF TMs

The table below lists known TM counts for TNF, TNF-1RB alongside total counts of all TMs in each 2-symbol domain.

• # Total TMs is the function $N(n,m)=(2m(n+1))^{mn}$ of all TMs with every combination of halting transition.
• # Simple Halt TMs is a slight simplification where the only allowed halt transition is 1RZ. There are $(2mn+1)^{mn}$ Simple Halt TMs.

TNF TM counts vs Total TM counts

	# Total TMs (OEIS A052200)	# Simple Halt TMs	# TNF TMs	# TNF-1RB TMs
BB(2)	20,736	6,561	61	41
BB(3)	16,777,216	4,826,809	5,417	4,057
BB(4)	25,600,000,000	6,975,757,441	858,909	620,261
BB(5)	63,403,380,965,376	16,679,880,978,201	181,385,789	126,891,605
BB(6)	232,218,265,089,212,416	59,604,644,775,390,625		~33,436,000,000

See Also

• Something Something Programming, "Brady's Algorithm for Program Generation" (2022).