Cyclic Tag

Cyclic Tag System

Cyclic Tag is a Turing-complete computational model^[1] 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.

A cyclic tag system has:

• A finite string of bits.
• A code consisting of a list of production rules.
• A head pointing at one of the production rules.

Execution rules:

• The cyclic tag system starts out with string equal to "1", with the head pointing to the first rules.
• At each step of the computation, delete the first symbol of the string and append the production rules to the string if it 1.
• Move the head one rule forward or at the first rule if it is pointing to the last rule.
• The cyclic tag system halts when it reaches the empty string.

Busy Beaver Function

The function BBCT(n) is the largest number of steps that any cyclic tag systems of size n takes before halting.

The size of a cyclic tag system is the sum of the lengths of all the production rules plus the number of production rules (same as for BB_PT).

BBCT(n)	Value	Champion
1	1	empty
2	2	0
3	3	00
4	4	000
5	7	010_
6	8	010_0
7	≥ 13	0110__
8	≥ 28	101_10_
9	≥ 717	1011_00_
10	≥ 209	11_0_0100
11	≥ 2,269	1011_1_00_
12	≥ 6,328	0111__010_0
13	≥ 50,906	0011_010_1_0

See also

• Tiny Tag