Tree Normal Form - Revision history

Polygon: /* Background */ Added link to permutation

2025-10-09T18:34:06Z

Background: Added link to permutation

← Older revision		Revision as of 18:34, 9 October 2025
Line 4:		Line 4:
	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 <math>N(n,m) = (2m(n+1))^{mn}</math> distinct TMs (Note: there are <math>n+1</math> 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:		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 <math>N(n,m) = (2m(n+1))^{mn}</math> distinct TMs (Note: there are <math>n+1</math> 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:

	# Permutations: Any permutation of non-start states, non-blank symbols or directions leads to a functionally equivalent TM.		# [[Permutation\|Permutations]]: Any permutation of non-start states, non-blank symbols or directions leads to a functionally equivalent TM.
	# 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.		# 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.
	# Halting transitions: Any of the 2m choices for halting transitions lead to the same runtime (and any of <math>2(m-1)</math> lead to same sigma score).		# Halting transitions: Any of the 2m choices for halting transitions lead to the same runtime (and any of <math>2(m-1)</math> lead to same sigma score).

Polygon: Prepare Category move of BB-domains

2025-08-10T23:40:42Z

Prepare Category move of BB-domains

← Older revision		Revision as of 23:40, 10 August 2025
Line 36:		Line 36:

	== Number of TNF TMs ==		== 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 [[:Category:BB ~~Domain~~\|domain]].		The table below lists known TM counts for TNF, TNF-1RB alongside total counts of all TMs in each 2-symbol [[:Category:BB Domains\|domain]].

	* # Total TMs is the function <math>N(n,m) = (2m(n+1))^{mn}</math> of all TMs with every combination of halting transition.		* # Total TMs is the function <math>N(n,m) = (2m(n+1))^{mn}</math> of all TMs with every combination of halting transition.

Sligocki: /* Number of TNF TMs */ link

2025-02-13T18:46:32Z

Number of TNF TMs: link

← Older revision		Revision as of 18:46, 13 February 2025
Line 36:		Line 36:

	== Number of TNF TMs ==		== 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.		The table below lists known TM counts for TNF, TNF-1RB alongside total counts of all TMs in each 2-symbol [[:Category:BB Domain\|domain]].

	* # Total TMs is the function <math>N(n,m) = (2m(n+1))^{mn}</math> of all TMs with every combination of halting transition.		* # Total TMs is the function <math>N(n,m) = (2m(n+1))^{mn}</math> of all TMs with every combination of halting transition.

XnoobSpeakable: fix typo

2025-02-06T17:16:52Z

fix typo

← Older revision		Revision as of 17:16, 6 February 2025
Line 1:		Line 1:
	'''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 a process for enumerating all TMs in Tree Normal Form. This process was first introduced by Allen Brady in his 1964 PhD dissertation<ref>Allen Brady. 1964. PhD dissertation. "[https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/zk51vk21c Solutions of restricted cases of the halting problem applied to the determination of particular values of a non-computable function]"</ref> and thus it has been called '''Brady's algorithm'''.		'''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<ref>Allen Brady. 1964. PhD dissertation. "[https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/zk51vk21c Solutions of restricted cases of the halting problem applied to the determination of particular values of a non-computable function]"</ref> and thus it has been called '''Brady's algorithm'''.

	== Background ==		== Background ==

Sligocki at 03:23, 16 November 2024

2024-11-16T03:23:10Z

← Older revision		Revision as of 03:23, 16 November 2024
Line 79:		Line 79:
	\|~33,436,000,000		\|~33,436,000,000
	\|}		\|}

			== See Also ==

			* Something Something Programming, "[https://nickdrozd.github.io/2022/01/14/bradys-algorithm.html Brady's Algorithm for Program Generation]" (2022).

	== References ==		== References ==
	<references />		<references />

Sligocki: Bring in some data from (mostly redundant) new "Brady's algorithm" article. Also added "# Simple Halt TMs" column to table and various small edits.

2024-11-15T15:30:28Z

Bring in some data from (mostly redundant) new "Brady's algorithm" article. Also added "# Simple Halt TMs" column to table and various small edits.

← Older revision		Revision as of 15:30, 15 November 2024
Line 1:		Line 1:
	'''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 first ~~described~~ by Allen Brady ~~which enumerates all TMs~~ in ~~TNF~~.		'''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 a process for enumerating all TMs in Tree Normal Form. This process was first introduced by Allen Brady in his 1964 PhD dissertation<ref>Allen Brady. 1964. PhD dissertation. "[https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/zk51vk21c Solutions of restricted cases of the halting problem applied to the determination of particular values of a non-computable function]"</ref> and thus it has been called '''Brady's algorithm'''.

	== Background ==		== Background ==
Line 24:		Line 24:
	** One option for transition is always the single halting transition <code>1RZ</code>.		** One option for transition is always the single halting transition <code>1RZ</code>.
	** 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:		** 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 ~~one,~~		*** 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 ~~one~~.		*** 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.		*** 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).		*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 ~~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.		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 ==		== TNF-1RB ==
	One common additional restriction is that the initial transition is <code>A0→1RB</code>. This is mainly done to exclude <code>A0→0RB</code> TMs. For any TM starting from <code>A0→0RB</code>, the TM that starts in state B instead will have the same exact ~~sigma~~ score and run for exactly one step less. By iterating this process at most <math>n - 1</math> times, any <math>n</math>-state <code>A0→0RB</code> machine can be transformed into ~~an equivalent~~ <code>A0→1RB</code> machine.		One common additional restriction is that the initial transition is <code>A0→1RB</code>. This is mainly done to exclude <code>A0→0RB</code> TMs. For any TM starting from <code>A0→0RB</code>, 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 <math>n - 1</math> times, any <math>n</math>-state <code>A0→0RB</code> machine can be transformed into a corresponding <code>A0→1RB</code> machine with the same Σ score and (at most) <math>n-1</math> shorter runtime.

	Many early enumerations chose to use the <code>A0→1RB</code> 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.		Many early enumerations chose to use the <code>A0→1RB</code> 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 ==		== 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 <math>N(n,m) = (2m(n+1))^{mn}</math> of all TMs with every combination of halting transition.
			* # Simple Halt TMs is a slight simplification where the only allowed halt transition is <code>1RZ</code>. There are <math>(2mn + 1)^{mn}</math> Simple Halt TMs.

	{\| class="wikitable" style="text-align: right;"		{\| class="wikitable" style="text-align: right;"
	\|+		\|+TNF TM counts vs Total TM counts
	!		!
	!Total TMs ([~~https~~:~~//oeis.org/~~A052200 OEIS A052200])		!# Total TMs ([[oeis:A052200\|OEIS A052200]])
	!TNF TMs		!# Simple Halt TMs
	!TNF-1RB TMs		!# TNF TMs
			!# TNF-1RB TMs
	\|-		\|-
	\|[[BB(2)]]		\|[[BB(2)]]
	\|20,736		\|20,736
			\|6,561
	\|61		\|61
	\|41		\|41
Line 50:		Line 57:
	\|[[BB(3)]]		\|[[BB(3)]]
	\|16,777,216		\|16,777,216
			\|4,826,809
	\|5,417		\|5,417
	\|4,057		\|4,057
Line 55:		Line 63:
	\|[[BB(4)]]		\|[[BB(4)]]
	\|25,600,000,000		\|25,600,000,000
			\|6,975,757,441
	\|858,909		\|858,909
	\|620,261		\|620,261
Line 60:		Line 69:
	\|[[BB(5)]]		\|[[BB(5)]]
	\|63,403,380,965,376		\|63,403,380,965,376
			\|16,679,880,978,201
	\|181,385,789		\|181,385,789
	\|126,891,605		\|126,891,605
Line 65:		Line 75:
	\|[[BB(6)]]		\|[[BB(6)]]
	\|232,218,265,089,212,416		\|232,218,265,089,212,416
			\|59,604,644,775,390,625
	\|		\|
	\|~33,436,000,000		\|~33,436,000,000
	\|}		\|}

			== References ==
			<references />

DF376 at 09:37, 13 August 2024

2024-08-13T09:37:32Z

← Older revision		Revision as of 09:37, 13 August 2024
Line 1:		Line 1:
	'''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.		'''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 first described by Allen Brady which enumerates all TMs in TNF.

	== Background ==		== Background ==

Int-y1 at 06:02, 29 July 2024

2024-07-29T06:02:30Z

← Older revision		Revision as of 06:02, 29 July 2024
Line 39:		Line 39:
	\|+		\|+
	!		!
	!Total TMs		!Total TMs ([https://oeis.org/A052200 OEIS A052200])
	!TNF TMs		!TNF TMs
	!TNF-1RB TMs		!TNF-1RB TMs

Sligocki: /* Number of TNF TMs */ Add TNF counts from Lazy Beaver enumeration.

2024-07-15T18:50:35Z

Number of TNF TMs: Add TNF counts from Lazy Beaver enumeration.

← Older revision		Revision as of 18:50, 15 July 2024
Line 45:		Line 45:
	\|[[BB(2)]]		\|[[BB(2)]]
	\|20,736		\|20,736
	\|		\|61
	\|41		\|41
	\|-		\|-
	\|[[BB(3)]]		\|[[BB(3)]]
	\|16,777,216		\|16,777,216
	\|		\|5,417
	\|4,057		\|4,057
	\|-		\|-
	\|[[BB(4)]]		\|[[BB(4)]]
	\|25,600,000,000		\|25,600,000,000
	\|		\|858,909
	\|620,261		\|620,261
	\|-		\|-
	\|[[BB(5)]]		\|[[BB(5)]]
	\|63,403,380,965,376		\|63,403,380,965,376
	\|		\|181,385,789
	\|126,891,605		\|126,891,605
	\|-		\|-

Mei: /* TNF-1RB */ Expand on the equivalence between 1RB and 0RB machines

2024-07-13T15:42:02Z

TNF-1RB: Expand on the equivalence between 1RB and 0RB machines

← Older revision		Revision as of 15:42, 13 July 2024
Line 31:		Line 31:

	== TNF-1RB ==		== TNF-1RB ==
	One common additional restriction is that the initial transition is <code>A0→1RB</code>. This is mainly done to exclude <code>A0→0RB</code> TMs. For any TM starting from <code>A0→0RB</code>, 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.		One common additional restriction is that the initial transition is <code>A0→1RB</code>. This is mainly done to exclude <code>A0→0RB</code> TMs. For any TM starting from <code>A0→0RB</code>, the TM that starts in state B instead will have the same exact sigma score and run for exactly one step less. By iterating this process at most <math>n - 1</math> times, any <math>n</math>-state <code>A0→0RB</code> machine can be transformed into an equivalent <code>A0→1RB</code> machine.

			Many early enumerations chose to use the <code>A0→1RB</code> 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 ==		== Number of TNF TMs ==