User:RobinCodes/Testing page: Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
← Older edit
VisualWikitext
RobinCodes (talk | contribs)
398 edits
Finalized version
RobinCodes (talk | contribs)
398 edits
Blanked page
 
Line 1: Line 1:
== Cyclic Tag ==
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 ==
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.
=== 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,'''
…
This example doesn't 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’).
==== Notes ====
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).
== Known Values ==
{| class="wikitable"
|+ Small CCTB values
|CCTB
|Value / Lower bound
|Discoverer
|Date
|Source
|-
| 2
|CTBB(2)=5
|Jack
|16 Nov 2025
|[https://discord.com/channels/960643023006490684/960643023530762341/1440163057463726233 Link]
|-
|3
|CTBB(3)<u>></u>38
|aparker
|18 Nov 2025
|[https://discord.com/channels/960643023006490684/1438694294042181742/1440193579006951517 Link]
|-
|4
|CTBB(4)<u>></u>420
|Moja
|25 Nov 2025
|[https://discord.com/channels/960643023006490684/1438694294042181742/1442826989101650032 Link]
|-
|5
|CTBB(5)<u>></u><math>7\times10^{25}</math>
|Moja & Racheline
|24 Nov 2025
|[https://discord.com/channels/960643023006490684/1438694294042181742/1442451330915635311 Link]
|-
|6
|CTBB(6)<u>></u>2↑↑↑131
|Moja & Racheline
|25 Nov 2025
|[https://discord.com/channels/960643023006490684/1438694294042181742/1442847677883875479 Link]
|-
|7
|CTBB(7)<u>></u>6↑↑↑14919
|Moja
|25 Nov 2025
|[https://discord.com/channels/960643023006490684/1438694294042181742/1442745206620557373 Link]
|}
== Collection of Champions ==
<div class="toccolours mw-collapsible mw-collapsed">'''Collection of Champions'''<div class="mw-collapsible-content">
<div class="toccolours mw-collapsible mw-collapsed">'''CCTB(1)'''<div class="mw-collapsible-content">
The following was given by Jack:
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.
</div></div>
<div class="toccolours mw-collapsible mw-collapsed">'''CTBB(2)'''<div class="mw-collapsible-content">
The domain was solved by Jack.
Δ: (()) (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)
All 432 pairs were brute-forced.
</div></div>
<div class="toccolours mw-collapsible mw-collapsed">'''CTBB(3) Champion'''<div class="mw-collapsible-content">
Pair found by aparker314159:
<pre>
Δ: [][[]]
Rule 0: [[]] => [[[]]]
Rule 1: [][][] => D
Rule 2: [] => [][]
</pre>
</div></div><div class="toccolours mw-collapsible mw-collapsed">'''CTBB(4) Champion'''<div class="mw-collapsible-content">
Pair found by Moja:
D="()()()()"
P:
'()' -> '(())'
'()()' -> '(()())()'
'(((())))' -> '()()'
'()()()' -> <nowiki>''</nowiki>
</div></div><div class="toccolours mw-collapsible mw-collapsed">'''CTBB(5) Champion'''<div class="mw-collapsible-content">
Pair found by Moja and Racheline:
Δ=()()((())())
P:
"((())()) -> ((())())()
((())()) -> ((())())()
()() -> ()()(())()
() -> (())
((((())))) -> D
</div></div><div class="toccolours mw-collapsible mw-collapsed">'''CTBB(6) Champion'''<div class="mw-collapsible-content">
Pair found by Moja and Racheline:
Δ: ((()))((()))
P:
((())) -> ((()))(()())
(()()) -> (()())(())
(()) -> (())(()()())
(()()()) -> (()()())()()
()()() -> D
() -> D
</div></div><div class="toccolours mw-collapsible mw-collapsed">'''CTBB(7) Champion'''<div class="mw-collapsible-content">
Pair found by Moja:
D="(()())(()()())"
P:
'(()()())' -> '(()()())(()())'
'(()()())' -> '(()()())(()())'
'(()())' -> '(()())((()))'
'((()))' -> '((()))(())()'
'(())()' -> '(())()()()()'
'(())()' -> '(())()()()()'
'()' -> <nowiki>''</nowiki>
</div></div>
</div></div>
== 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 Δ,
…
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 [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.

Latest revision as of 14:56, 14 December 2025

Retrieved from "https://wiki.bbchallenge.org/w/index.php?title=User:RobinCodes/Testing_page&oldid=5583"