User:JackM4828/Unary 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.

Cyclic Tag Difference

Traditional Cyclic Tag rules are binary mappings. Unary Cylic Tag rules are unary “payloads”, meaning that the rule is tied to the value read. Also, in Unary Cyclic Tag, Unary Cyclic Tag has one rule per cycle whilst Cyclic Tag has two implicit rules per cycle.

Introduction

A “Unary Rule Cyclic Tag System” is defined under a 4-tuple [B,Ω,P,i] as follows:

(1) B is our alphabet. In this case, it is the set of all arbitrary, finite, non-empty binary strings,

(2) Ω ∈ B is an initial string,

(3) P are production rules X₁,X₂,…,Xₖ where Xₘ ∈ B (with duplicate rules allowed),

(4) i ∈ (1,2,…,k) is an instruction pointer (initially set to 1),

Lastly, a pair denoted [Δ,P] is considered a “program”. To “solve” a program, we must follow these instructions:

Instructions

• Identify the leftmost bit in Ω (let it be F),

• Let Rᵢ be the current rule,

• Delete F. If F was 1 (before deletion), append Rᵢ to the end. If F was 0, append nothing,

• Go to: next rule (i ← (i mod k)+1),

Halting Condition

A program halts iff Ω = ∅.

Function

Let |L| be the length of L. Let Ubb(n) (Unary Busy Beaver) be defined as the max finite number of rule applications required until halting occurs for a program of “size n” (a size n program consists of: |P| = n rules, (|Xₘ|,|Δ|) ≤ n bits).

NOTE: each rule Xₘ can be of different lengths (keeping in mind |Xₘ|≤n).

Current Champion/Very Weak Lower Bounds

Ubb(1)=2 (via: Δ=1, P=[0]) Ubb(2)≥8 (via: Δ=10, P=[1,00]) Ubb(3)≥32 (via: Δ=111, P=[000,101,10]) … Ubb(10)>>130000 (where “>>” represents “way greater than”)