Cyclic Tag

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 in S 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).

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.

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,…,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 HERE

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