User:RobinCodes/Testing page - Revision history

RobinCodes: Blanked page

2025-12-14T14:56:58Z

Blanked page

Show changes

RobinCodes: Finalized version

2025-11-25T18:16:55Z

Finalized version

Show changes

RobinCodes: /* Known Values */ Updated table

2025-11-25T17:44:46Z

Known Values: Updated table

← Older revision		Revision as of 17:44, 25 November 2025
Line 92:		Line 92:
	{\| class="wikitable"		{\| class="wikitable"
	\|+ Small CCTB values		\|+ Small CCTB values
			\|CCTB
			\|Value / Lower bound
			\|Discoverer
	\|-		\|-
	\| CTBB(2)=5		\| 2
	\| ~~style="background: orange;"~~ \|CTBB(3)<u>></u>38		\|CTBB(2)=5
	\| ~~style="background: orange;"~~ \|CTBB(4)<u>></u>232		\|Jack
	\| ~~style="background: orange;"~~ \|CTBB(5)<u>></u><math>7\times10^{25}</math>		\|-
	\| ~~style="background: orange;"~~ \| CTBB(6)<u>></u>2↑↑↑131		\|3
	\| ~~style="background: orange;"~~ \| CTBB(7)<u>></u>6↑↑↑14919		\|CTBB(3)<u>></u>38
			\|aparker
			\|-
			\|4
			\|CTBB(4)<u>></u>232
			\|Moja
			\|-
			\|5
			\|CTBB(5)<u>></u><math>7\times10^{25}</math>
			\|Moja & Racheline
			\|-
			\|6
			\|CTBB(6)<u>></u>2↑↑↑131
			\|Moja & Racheline
			\|-
			\|7
			\|CTBB(7)<u>></u>6↑↑↑14919
			\|Moja
	\|}		\|}
	'''<u>CTBB(1)=1</u>'''<sup>[https://discord.com/channels/960643023006490684/1438694294042181742/1438736169318744135 <nowiki>[1]</nowiki>]</sup>		'''<u>CTBB(1)=1</u>'''<sup>[https://discord.com/channels/960643023006490684/1438694294042181742/1438736169318744135 <nowiki>[1]</nowiki>]</sup>

RobinCodes: Added references and table of known values and lower bounds

2025-11-25T17:36:47Z

Added references and table of known values and lower bounds

← Older revision		Revision as of 17:36, 25 November 2025
Line 90:		Line 90:

	== Known Values ==		== Known Values ==
	'''<u>CTBB(1)=1</u>'''		{\| class="wikitable"
			\|+ Small CCTB values
			\|-
			\| CTBB(2)=5
			\| style="background: orange;" \|CTBB(3)<u>></u>38
			\| style="background: orange;" \|CTBB(4)<u>></u>232
			\| style="background: orange;" \|CTBB(5)<u>></u><math>7\times10^{25}</math>
			\| style="background: orange;" \| CTBB(6)<u>></u>2↑↑↑131
			\| style="background: orange;" \| CTBB(7)<u>></u>6↑↑↑14919
			\|}
			'''<u>CTBB(1)=1</u>'''<sup>[https://discord.com/channels/960643023006490684/1438694294042181742/1438736169318744135 <nowiki>[1]</nowiki>]</sup>

	<div class="toccolours mw-collapsible mw-collapsed">'''Details'''<div class="mw-collapsible-content">		<div class="toccolours mw-collapsible mw-collapsed">'''Details'''<div class="mw-collapsible-content">
Line 117:		Line 127:
	</div></div>		</div></div>

	On November 16th, 2025, Jack (the creator of CTBB(n)) found the champion for CTBB(2):		On November 16th, 2025, Jack (the creator of CTBB(n)) found the champion for CTBB(2)<sup>[https://discord.com/channels/960643023006490684/960643023530762341/1440163057463726233 <nowiki>[2]</nowiki>]</sup>:

	<div class="toccolours mw-collapsible mw-collapsed">'''CTBB(2) Champion'''<div class="mw-collapsible-content">		<div class="toccolours mw-collapsible mw-collapsed">'''CTBB(2) Champion'''<div class="mw-collapsible-content">
Line 143:		Line 153:


	<u>The current lower bound on CTBB(3) is 38</u>.		<u>The current lower bound on CTBB(3) is 38</u>.<sup>[https://discord.com/channels/960643023006490684/1438694294042181742/1440193579006951517 <nowiki>[3]</nowiki>]</sup>
	<div class="toccolours mw-collapsible mw-collapsed">'''CTBB(3) Champion'''<div class="mw-collapsible-content">		<div class="toccolours mw-collapsible mw-collapsed">'''CTBB(3) Champion'''<div class="mw-collapsible-content">
	Given by the following pair found by aparker314159:		Given by the following pair found by aparker314159:
Line 155:		Line 165:
	</div></div>		</div></div>

	On the 23rd of November, 2025, Discord user Moja found that CTBB(6)>8^20053. Then,		On the 23rd of November, 2025, Discord user Moja found that CTBB(6)>8^20053<sup>[https://discord.com/channels/960643023006490684/1438694294042181742/1442207004105113713 <nowiki>[4]</nowiki>]</sup>. Then,

	on November 24th, 2025, Discord user Moja found yet another bound for CTBB(6) that “smashed” the previous one. This also implied that their previously discussed bound for CTBB(7) was nowhere close to its actual value.		on November 24th, 2025, Discord user Moja found yet another bound for CTBB(6) that “smashed” the previous one. This also implied that their previously discussed bound for CTBB(7) was nowhere close to its actual value.


	'''CTBB(6)>3↑↑(3^36865)''' (where the double-arrow represents tetration).		'''CTBB(6)>3↑↑(3^36865)'''<sup>[https://discord.com/channels/960643023006490684/1438694294042181742/1442728437117616128 <nowiki>[5]</nowiki>]</sup> (where the double-arrow represents tetration).
	<div class="toccolours mw-collapsible mw-collapsed">'''CTBB(6) Champion'''<div class="mw-collapsible-content">		<div class="toccolours mw-collapsible mw-collapsed">'''CTBB(6) Champion'''<div class="mw-collapsible-content">

RobinCodes: Added Collapsibles, changed some formatting

2025-11-25T16:56:19Z

Added Collapsibles, changed some formatting

← Older revision		Revision as of 16:56, 25 November 2025
Line 1:		Line 1:
	== ~~What is~~ Cyclic Tag? ==		== Cyclic Tag ==
	Cyclic Tag is a Turing-complete computational model where a binary string evolves under a set of rules applied in cyclic order. There are various halting conditions that one may choose. They are explicitly stated further below.		Cyclic Tag is a Turing-complete computational model<sup>[[wikipedia:Tag_system#Cyclic_tag_systems\|[1]]]</sup> where a binary string evolves under a set of rules applied in cyclic order. There are various halting conditions that one may choose. They are explicitly stated further below.

	== Rooted Ordered Tree Variant ==		== Rooted Ordered Tree Variant ==
Line 14:		Line 14:
	* For each node, the children are arranged in a left-to-right order.		* For each node, the children are arranged in a left-to-right order.

	== Introduction to Δ and P ==		=== Introduction to Δ and P ===
	Define an ordered pair [Δ,Ρ] where Δ is an initial finite non-empty Dyck String & P are production rules P=(R₁,R₂,…,Rₖ), each in the form “X→Y” where X and Y are finite non-empty Dyck Strings. Y has the ability to be the symbol D. When Y is instead D, this means: in Δ, delete X.		Define an ordered pair [Δ,Ρ] where Δ is an initial finite non-empty Dyck String & P are production rules P=(R₁,R₂,…,Rₖ), each in the form “X→Y” where X and Y are finite non-empty Dyck Strings. Y has the ability to be the symbol D. When Y is instead D, this means: in Δ, delete X.

Line 89:		Line 89:
	We can also correctly say that CTBB(n)>f(n) where f(n) is any computable function (where > represents eventual domination).		We can also correctly say that CTBB(n)>f(n) where f(n) is any computable function (where > represents eventual domination).

	== CTBB(1) ==		== Known Values ==
			'''<u>CTBB(1)=1</u>'''

			<div class="toccolours mw-collapsible mw-collapsed">'''Details'''<div class="mw-collapsible-content">
	We are only allowed:		We are only allowed:

Line 114:		Line 115:

	max(S’)=1.		max(S’)=1.
			</div></div>

	~~== Known Values ==~~
	On November 16th, 2025, Jack (the creator of CTBB(n)) found the champion for CTBB(2):		On November 16th, 2025, Jack (the creator of CTBB(n)) found the champion for CTBB(2):

			<div class="toccolours mw-collapsible mw-collapsed">'''CTBB(2) Champion'''<div class="mw-collapsible-content">

	Δ: (()) (Initial String)		Δ: (()) (Initial String)
Line 135:		Line 137:

	∅ (apply rule 1)		∅ (apply rule 1)
			</div></div>


Line 141:		Line 143:


	<u>The current lower bound on CTBB(3) is 38</u>~~, given~~ by the following pair found by aparker314159:		<u>The current lower bound on CTBB(3) is 38</u>.
			<div class="toccolours mw-collapsible mw-collapsed">'''CTBB(3) Champion'''<div class="mw-collapsible-content">
			Given by the following pair found by aparker314159:

	<pre>		<pre>
Line 149:		Line 153:
	Rule 2: [] => [][]		Rule 2: [] => [][]
	</pre>		</pre>
			</div></div>

			On the 23rd of November, 2025, Discord user Moja found that CTBB(6)>8^20053. Then,

	~~On the 23rd of~~ November, 2025, Discord user Moja found ~~a “breakthrough pair”:~~		on November 24th, 2025, Discord user Moja found yet another bound for CTBB(6) that “smashed” the previous one. This also implied that their previously discussed bound for CTBB(7) was nowhere close to its actual value.


	'''CTBB(6)>8^~~20053~~'''~~, by~~ the ~~following pair:~~		'''CTBB(6)>3↑↑(3^36865)''' (where the double-arrow represents tetration).
			<div class="toccolours mw-collapsible mw-collapsed">'''CTBB(6) Champion'''<div class="mw-collapsible-content">


	~~Δ: (()())(()())~~


	P:

	~~(()())~~ -~~> (()())(())(~~)

	~~(()())~~ -~~> (()())(())()~~

	~~(()())~~ -> ~~(()())(())()~~

	~~(()) -> (())()()()()~~

	~~(()) -> (())()()()()~~

	~~() -> D~~


	On November 24th, 2025, Discord user Moja found yet another bound for CTBB(6) that “smashed” the previous one. This also implied that their previously discussed bound for CTBB(7) was nowhere close to its actual value.


	'''CTBB(6)~~>3↑↑(3^36865)~~''' ~~(where the double~~-~~arrow represents tetration), using the following pair:~~

			Using the following pair:

	Δ: (()())(()())		Δ: (()())(()())
Line 197:		Line 180:

	() -> D		() -> D
			</div></div>

	== Total Number of Pairs ==		== Total Number of Pairs ==
	The number of pairs [Δ,Ρ] grows rather quick. For CTBB(n), there are C(1)+C(2)+…+C(n) total Δ’s (where C(n)=n-th Catalan Number). The first few values are:		The number of pairs [Δ,Ρ] grows rather quick. For CTBB(n), there are C(1)+C(2)+…+C(n) total Δ’s (where C(n)=n-th Catalan Number). The first few values are:
Line 211:		Line 196:
	CTBB(10) has 23713 possible Δ.		CTBB(10) has 23713 possible Δ.

	== Let’s Dive Deeper… ==		=== Let’s Dive Deeper… ===
	Number of possible X: Sum of 1st,2nd,…,n-th Catalan Numbers		Number of possible X: Sum of 1st,2nd,…,n-th Catalan Numbers

RobinCodes: Began updating

2025-11-25T16:35:06Z

Began updating

@@ Line 141: / Line 141: @@
-<u>The current lower bound on CTBB(3) is 38</u>, given by the following machine found by aparker314159:
+<u>The current lower bound on CTBB(3) is 38</u>, given by the following pair found by aparker314159:
 <pre>
@@ Line 150: / Line 150: @@
 </pre>
 == Total Number of Pairs ==
 The number of pairs [Δ,Ρ] grows rather quick. For CTBB(n), there are C(1)+C(2)+…+C(n) total Δ’s (where C(n)=n-th Catalan Number). The first few values are:

RobinCodes: Initial commit + added changes to Cyclic Tag page

2025-11-20T21:26:44Z

Initial commit + added changes to Cyclic Tag page

← Older revision		Revision as of 21:26, 20 November 2025
Line 3:		Line 3:

	== Rooted Ordered Tree Variant ==		== Rooted Ordered Tree Variant ==
	This variant of Cyclic Tag operates upon a Dyck String instead of a binary string. A Dyck String is a string of parentheses “(“ and “)” of length 2n, that consists of an equal number of symbols such that for all prefixes, “(“ occurs at least as many times as the other “)”. In shorter terms, a Dyck String is a balanced parenthetical string of length 2n.		This variant of Cyclic Tag operates upon a Dyck String instead of a binary string. A Dyck String is a string of parentheses “(“ and “)” of length 2n, that consists of an equal number of symbols such that for all prefixes, “(“ occurs at least as many times as the other “)”. In shorter terms, a Dyck String is a balanced parenthetical string of length 2n. There does not exist a Dyck String (in this format) with an odd length (hence the 2n).

	~~There does not exist a Dyck String (in this format) with an odd length (hence the 2n).~~		=== Rooted Ordered Trees and Dyck Strings ===

	== Rooted Ordered Trees and Dyck Strings ==
	Dyck Strings (pronounced as: DEEK) encode finite rooted ordered trees through a well-known bijection that maps the structure of a tree to a balanced sequence of parentheses. The most common method involves a depth-first traversal of the tree. A rooted ordered tree is a tree with these key features:		Dyck Strings (pronounced as: DEEK) encode finite rooted ordered trees through a well-known bijection that maps the structure of a tree to a balanced sequence of parentheses. The most common method involves a depth-first traversal of the tree. A rooted ordered tree is a tree with these key features:

Line 15:		Line 13:

	* For each node, the children are arranged in a left-to-right order.		* For each node, the children are arranged in a left-to-right order.

	~~== Examples of Valid Dyck Strings ==~~

	* (())()()()(())

	* ()()()

	* (((()))()())

	* (())

	* ((()))(())()

	~~…etc…~~

	~~All parentheses are “balanced”.~~

	== Introduction to Δ and P ==		== Introduction to Δ and P ==
	Define an ordered pair [Δ,Ρ] where Δ is an initial finite non-empty Dyck String & P are production rules P=(R₁,R₂,…,Rₖ), each in the form “X→Y” where X and Y are finite non-empty Dyck Strings. Y has the ability to be the symbol D. When Y is instead D, this means: in Δ, delete X.		Define an ordered pair [Δ,Ρ] where Δ is an initial finite non-empty Dyck String & P are production rules P=(R₁,R₂,…,Rₖ), each in the form “X→Y” where X and Y are finite non-empty Dyck Strings. Y has the ability to be the symbol D. When Y is instead D, this means: in Δ, delete X.

	== ~~“Solving”~~ a Given Δ and P ==		=== Solving a Given Δ and P: ===
	We follow these steps:		We follow these steps:

Line 56:		Line 38:
	'''''NOTE:''''' Duplicate rules in the same P are allowed.		'''''NOTE:''''' Duplicate rules in the same P are allowed.

	== Halting Conditions ==		=== Halting Conditions ===
	Some given pairs [Δ,P] never halt. However, some do! Here are two halting conditions we can define:		Some given pairs [Δ,P] never halt. However, some do! Here are two halting conditions we can define:

Line 81:		Line 63:
	…		…

	~~…etc…~~		This example doesn't halt as ((…()…)) will keep expanding indefinitely.

	…

	This example ~~DOES NOT~~ halt as ((…()…)) will keep expanding indefinitely.

	== Correlation to BB(n) ==		== Correlation to BB(n) ==
Line 95:		Line 73:

	== Function ==		== Function ==
	The “Cyclic Tree Busy Beaver” function CTBB(n) is ~~THEREFORE~~ defined as follows:		The “Cyclic Tree Busy Beaver” function CTBB(n) is therefore defined as follows:


Line 106:		Line 84:
	'''(4)''' CTBB(n) outputs max(S’).		'''(4)''' CTBB(n) outputs max(S’).

	== ~~Final Ideas~~ ==		==== Notes ====
	Because Tag Systems in this fashion are Turing-Complete, we can expect CTBB(n) to be on par with the classic BB(n).		Because Tag Systems in this fashion are Turing-Complete, we can expect CTBB(n) to be on par with the classic BB(n).

	We can also correctly say that CTBB(n)>f(n) where f(n) is any computable function (where > represents eventual domination).		We can also correctly say that CTBB(n)>f(n) where f(n) is any computable function (where > represents eventual domination).

	== ~~Calculating Values (~~CTBB(1)) ==		== CTBB(1) ==


Line 137:		Line 115:
	max(S’)=1.		max(S’)=1.

	== ~~CTBB(1) and Beyond~~ ==		== Known Values ==
	On November 16th, 2025, Jack (the creator of CTBB(n)) found the champion for CTBB(2):		On November 16th, 2025, Jack (the creator of CTBB(n)) found the champion for CTBB(2):

Line 159:		Line 137:


	This gives CTBB(2)=5. All 432 total pairs [Δ,Ρ] were brute-forced.
			This gives '''<u>CTBB(2)=5</u>'''. All 432 total pairs [Δ,Ρ] were brute-forced.


	The current lower bound on CTBB(3) is 38, given by the following machine found by aparker314159:		<u>The current lower bound on CTBB(3) is 38</u>, given by the following machine found by aparker314159:

	<pre>		<pre>
Line 183:		Line 162:
	…		…

	~~speeding forward…~~		CTBB(10) has 23713 possible Δ.

	…

	CTBB(10) has 23713 possible Δ,

	== Let’s Dive Deeper… ==		== Let’s Dive Deeper… ==
Line 203:		Line 178:

	'''[(Sum of 1st,2nd,…,n-th Catalan Numbers)×((Sum of 1st,2nd,…,n-th Catalan Numbers)+1)]ⁿ'''		'''[(Sum of 1st,2nd,…,n-th Catalan Numbers)×((Sum of 1st,2nd,…,n-th Catalan Numbers)+1)]ⁿ'''



Line 210:		Line 184:
	'''Pair(n)=(Sum of 1st,2nd,…,n-th Catalan Numbers)×[(Sum of 1st,2nd,…,n-th Catalan Numbers)×((Sum of 1st,2nd,…,n-th Catalan Numbers)+1)]ⁿ'''		'''Pair(n)=(Sum of 1st,2nd,…,n-th Catalan Numbers)×[(Sum of 1st,2nd,…,n-th Catalan Numbers)×((Sum of 1st,2nd,…,n-th Catalan Numbers)+1)]ⁿ'''

	== Values of the Pair Function ==		=== Values of the Pair Function ===
	Pair(1)=2 (as shown earlier)		Pair(1)=2 (as shown earlier)

Line 221:		Line 195:
	Pair(5)≈7.97×10¹⁷		Pair(5)≈7.97×10¹⁷

	== Turing-Completeness of Tag Systems ~~(In~~ General) ==		== Turing-Completeness of Tag Systems in General ==
	Cocke and Minsky's construction of a Universal Turing Machine within a tag system can be found ~~by clicking this link~~ [https://dl.acm.org/doi/pdf/10.1145/321203.321206 ~~HERE~~]		Cocke and Minsky's construction of a Universal Turing Machine within a tag system can be found [https://dl.acm.org/doi/pdf/10.1145/321203.321206 here].

	It is worth mentioning that this variant of cyclic tag does not involve appending, only rewriting.		It is worth mentioning that this variant of cyclic tag does not involve appending, only rewriting.

RobinCodes: Initial commit

2025-11-20T21:13:35Z

Initial commit

New page

== What is Cyclic Tag? ==
Cyclic Tag is a Turing-complete computational model where a binary string evolves under a set of rules applied in cyclic order. There are various halting conditions that one may choose. They are explicitly stated further below.

== Rooted Ordered Tree Variant ==
This variant of Cyclic Tag operates upon a Dyck String instead of a binary string. A Dyck String is a string of parentheses “(“ and “)” of length 2n, that consists of an equal number of symbols such that for all prefixes, “(“ occurs at least as many times as the other “)”. In shorter terms, a Dyck String is a balanced parenthetical string of length 2n.

There does not exist a Dyck String (in this format) with an odd length (hence the 2n).

== Rooted Ordered Trees and Dyck Strings ==
Dyck Strings (pronounced as: DEEK) encode finite rooted ordered trees through a well-known bijection that maps the structure of a tree to a balanced sequence of parentheses. The most common method involves a depth-first traversal of the tree. A rooted ordered tree is a tree with these key features:

* One vertex is distinguished as the root,

* All edges are directed away from the root (conceptually, though not always drawn with arrows),

* For each node, the children are arranged in a left-to-right order.

== Examples of Valid Dyck Strings ==

* (())()()()(())

* ()()()

* (((()))()())

* (())

* ((()))(())()

…etc…

All parentheses are “balanced”.

== Introduction to Δ and P ==
Define an ordered pair [Δ,Ρ] where Δ is an initial finite non-empty Dyck String & P are production rules P=(R₁,R₂,…,Rₖ), each in the form “X→Y” where X and Y are finite non-empty Dyck Strings. Y has the ability to be the symbol D. When Y is instead D, this means: in Δ, delete X.

== “Solving” a Given Δ and P ==
We follow these steps:

'''(1)''' Begin with R₁,

'''(2)''' Scan Δ from left to right,

'''(3)''' Find the leftmost instance of X in Δ (according to said R)

'''(4)''' Rewrite X as Y and leave the rest of Δ unchanged (or delete X if Y is the symbol D)

'''(5)''' Move to the next R in cyclic order (1, 2,…,n,1,2,…)

'''(6)''' If a rule doesn’t apply, simply skip it and move to the immediate next one in P,

'''(7)''' Repeat from (2) on the altered Δ each time.

'''''NOTE:''''' Duplicate rules in the same P are allowed.

== Halting Conditions ==
Some given pairs [Δ,P] never halt. However, some do! Here are two halting conditions we can define:

'''Halt if:'''

Δ becomes “∅” (empty), or if there does not exist a rule in P that can transform Δ any further, meaning that Δ is what we can call “stuck”.

== Example Run-Through ==
(Initial Dyck String) Δ: ()()(())

(Production Rules) P: R₁=()→(()), R₂=(())()→D

()()(()) initial String Δ,

(())()(()) as per R₁, (()) replaces (),

(()) as per R₂, (())() is deleted,

((())) as per R₁, (()) replaces (),

'''SKIP R₂, IT DOES NOT APPLY,'''

…

…etc…

…

This example DOES NOT halt as ((…()…)) will keep expanding indefinitely.

== Correlation to BB(n) ==
From here, we can define a function analogous to the Busy Beaver function by taking the maximal finite halting times for all pairs. Here’s how we can do it:

Let |x| denote the length of x.

A pair [Δ,P] of “size n” consists of n rules, where for each Rᵢ ∈ P, |X|≤2n and |Y|≤2n ('''NOTE''': the lengths of X and Y for each Rᵢ do NOT have to be the same, but they must be ≤2n). We also assume that |Δ|≤2n. We say that skipping a rule counts as a step, and a “step” is defined as a singular rule application.

== Function ==
The “Cyclic Tree Busy Beaver” function CTBB(n) is THEREFORE defined as follows:

'''(1)''' Run all pairs [Δ,P] of size n,

'''(2)''' Let S be the set of all pairs S=(P₁,P₂,…,Pₘ) that halted, and filter out (discard) all pairs that do not,

'''(3)''' Let S’ be the set of all steps for every pair in S to halt,

'''(4)''' CTBB(n) outputs max(S’).

== Final Ideas ==
Because Tag Systems in this fashion are Turing-Complete, we can expect CTBB(n) to be on par with the classic BB(n).

We can also correctly say that CTBB(n)>*f(n) where f(n) is any computable function (where >* represents eventual domination).

== Calculating Values (CTBB(1)) ==

We are only allowed:

* 1 rule

* For each rule part (X,Y) can only contain at most 2 symbols (because 2(1)=2)

* The initial string Δ also only contains at most 2 symbols

There is only one possible Dyck string with at most 2 symbols, it is: (). Here are all possible P (rulesets) and Δ given these constraints:

Δ: (), single rule: ()→()

Δ: (), single rule: ()→D

'''Remember''': Δ must be non-empty. It’s easy to tell that for each step, the first ruleset results in an infinite loop. The second one halts after 1 step (it immediately deletes () ).

S is the set of all halting pairs (only the second one) and S’ is the halting times for said pair(s) (only 1).

max(S’)=1.

== CTBB(1) and Beyond ==
On November 16th, 2025, Jack (the creator of CTBB(n)) found the champion for CTBB(2):

Δ: (()) (Initial String)

P: R₁=()()→D, R₂=()→()()

(()) (Δ)

Skip rule 1 (skipping counts as a step)

(()()) (apply rule 2)

() (apply rule 1)

()() (apply rule 2)

∅ (apply rule 1)

This gives CTBB(2)=5. All 432 total pairs [Δ,Ρ] were brute-forced.

The current lower bound on CTBB(3) is 38, given by the following machine found by aparker314159:

<pre>
Δ: [][[]]
Rule 0: [[]] => [[[]]]
Rule 1: [][][] => D
Rule 2: [] => [][]
</pre>

== Total Number of Pairs ==
The number of pairs [Δ,Ρ] grows rather quick. For CTBB(n), there are C(1)+C(2)+…+C(n) total Δ’s (where C(n)=n-th Catalan Number). The first few values are:

CTBB(1) has 1 possible Δ,

CTBB(2) has 3 possible Δ,

CTBB(3) has 8 possible Δ,

…

speeding forward…

…

CTBB(10) has 23713 possible Δ,

== Let’s Dive Deeper… ==
Number of possible X: Sum of 1st,2nd,…,n-th Catalan Numbers

Number of possible Y: ((Sum of 1st,2nd,…,n-th Catalan Numbers)+1) (the “+1” represents the optional “D” symbol)

Each R in P is technically an ordered pair [x,y] so we multiply the counts together:

'''(Sum of 1st,2nd,…,n-th Catalan Numbers)×((Sum of 1st,2nd,…,n-th Catalan Numbers)+1)'''

There are n rules, so we exponentiate this by n:

'''[(Sum of 1st,2nd,…,n-th Catalan Numbers)×((Sum of 1st,2nd,…,n-th Catalan Numbers)+1)]ⁿ'''

We have our initial Dyck string Δ of length at most 2n (as mentioned earlier). This is also equal to the sum of the 1st,2nd,…,n-th Catalan numbers. This forms another pair [Δ,Ρ] by multiplying our Catalan sum with our formula from before:

'''Pair(n)=(Sum of 1st,2nd,…,n-th Catalan Numbers)×[(Sum of 1st,2nd,…,n-th Catalan Numbers)×((Sum of 1st,2nd,…,n-th Catalan Numbers)+1)]ⁿ'''

== Values of the Pair Function ==
Pair(1)=2 (as shown earlier)

Pair(2)=432

Pair(3)=2985984

Pair(4)≈1.44×10¹²

Pair(5)≈7.97×10¹⁷

== Turing-Completeness of Tag Systems (In General) ==
Cocke and Minsky's construction of a Universal Turing Machine within a tag system can be found by clicking this link [https://dl.acm.org/doi/pdf/10.1145/321203.321206 HERE]

It is worth mentioning that this variant of cyclic tag does not involve appending, only rewriting.