Cyclic Tag

From BusyBeaverWiki
(Redirected from BBCT)
Jump to navigation Jump to search

For the tree rewriting system based on Cyclic Tag, see Cyclic Tree Rewriting System.

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 to 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 production rule.
  • At each step of the computation, delete the string's first bit. If a 1 was deleted, append the production rule the head is pointed to.
  • Move the head one rule forward or back to 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 ≥ 1,626,862 1001_1_00
11 ≥ 1,859,166 10_10010_0
12 ≥ 6,328 0111__010_0
13 ≥ 5,217,735 001110_1_0_0
14 ≥ 154,171,565 01011__0_0100
15 ≥ 995,677,080 111010__0_1_00
16 ≥ 4,483,046,325 01__001100100_0

See also

Sources

GitHub repository (with documentation, deciders and holdout lists): https://github.com/AzertyWasTaken/Busy-Beaver/tree/main/Cyclic%20Tag%20System