<?xml version="1.0"?>
<feed xmlns="http://www.w3.org/2005/Atom" xml:lang="en">
	<id>https://wiki.bbchallenge.org/w/api.php?action=feedcontributions&amp;feedformat=atom&amp;user=Teoet6</id>
	<title>BusyBeaverWiki - User contributions [en]</title>
	<link rel="self" type="application/atom+xml" href="https://wiki.bbchallenge.org/w/api.php?action=feedcontributions&amp;feedformat=atom&amp;user=Teoet6"/>
	<link rel="alternate" type="text/html" href="https://wiki.bbchallenge.org/wiki/Special:Contributions/Teoet6"/>
	<updated>2026-11-18T19:04:51Z</updated>
	<subtitle>User contributions</subtitle>
	<generator>MediaWiki 1.43.5</generator>
	<entry>
		<id>https://wiki.bbchallenge.org/w/index.php?title=Cyclic_Tag&amp;diff=10619</id>
		<title>Cyclic Tag</title>
		<link rel="alternate" type="text/html" href="https://wiki.bbchallenge.org/w/index.php?title=Cyclic_Tag&amp;diff=10619"/>
		<updated>2026-11-13T00:50:58Z</updated>

		<summary type="html">&lt;p&gt;Teoet6: Remove ≥ from n=9 as the final holdouts were decided to be non-halting.&lt;/p&gt;
&lt;hr /&gt;
&lt;div&gt;&#039;&#039;For the tree rewriting system based on Cyclic Tag, see [[Cyclic Tree Rewriting System|Cyclic Tree Rewriting System.]]&#039;&#039;&lt;br /&gt;
&lt;br /&gt;
== Cyclic Tag System ==&lt;br /&gt;
Cyclic Tag is a [[Turing-complete]] computational model&amp;lt;sup&amp;gt;[[wikipedia:Tag_system#Cyclic_tag_systems|[1]]]&amp;lt;/sup&amp;gt; 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. &lt;br /&gt;
&lt;br /&gt;
=== A cyclic tag system has: ===&lt;br /&gt;
&lt;br /&gt;
* A finite &#039;&#039;&#039;string&#039;&#039;&#039; of &#039;&#039;&#039;bits&#039;&#039;&#039;.&lt;br /&gt;
* A &#039;&#039;&#039;code&#039;&#039;&#039; consisting of a list of &#039;&#039;&#039;production rules&#039;&#039;&#039;.&lt;br /&gt;
* A &#039;&#039;&#039;head&#039;&#039;&#039; pointing at one of the production rules.&lt;br /&gt;
&lt;br /&gt;
=== Execution rules: ===&lt;br /&gt;
&lt;br /&gt;
* The cyclic tag system starts out with &#039;&#039;&#039;string&#039;&#039;&#039; equal to &amp;quot;1&amp;quot;, with the &#039;&#039;&#039;head&#039;&#039;&#039; pointing to the &#039;&#039;&#039;first rules&#039;&#039;&#039;.&lt;br /&gt;
* At each step of the computation, &#039;&#039;&#039;delete&#039;&#039;&#039; the &#039;&#039;&#039;first symbol&#039;&#039;&#039; of the &#039;&#039;&#039;string&#039;&#039;&#039; and append the &#039;&#039;&#039;production rules&#039;&#039;&#039; to the &#039;&#039;&#039;string&#039;&#039;&#039; if it 1.&lt;br /&gt;
* &#039;&#039;&#039;Move&#039;&#039;&#039; the &#039;&#039;&#039;head&#039;&#039;&#039; one rule forward or at the first rule if it is pointing to the last rule.&lt;br /&gt;
* The cyclic tag system halts when it reaches the empty string.&lt;br /&gt;
&lt;br /&gt;
== Busy Beaver Function ==&lt;br /&gt;
The function &#039;&#039;BBCT(n)&#039;&#039; is the largest number of steps that any cyclic tag systems of size &#039;&#039;n&#039;&#039; takes before halting.&lt;br /&gt;
&lt;br /&gt;
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 [[Post Tag System|BB_PT]]).&lt;br /&gt;
{| class=&amp;quot;wikitable&amp;quot;&lt;br /&gt;
|+&lt;br /&gt;
!BBCT(n)&lt;br /&gt;
!Value&lt;br /&gt;
!Champion&lt;br /&gt;
|-&lt;br /&gt;
|1&lt;br /&gt;
|1&lt;br /&gt;
|&amp;lt;code&amp;gt;empty&amp;lt;/code&amp;gt;&lt;br /&gt;
|-&lt;br /&gt;
|2&lt;br /&gt;
|2&lt;br /&gt;
|&amp;lt;code&amp;gt;0&amp;lt;/code&amp;gt;&lt;br /&gt;
|-&lt;br /&gt;
|3&lt;br /&gt;
|3&lt;br /&gt;
|&amp;lt;code&amp;gt;00&amp;lt;/code&amp;gt;&lt;br /&gt;
|-&lt;br /&gt;
|4&lt;br /&gt;
|4&lt;br /&gt;
|&amp;lt;code&amp;gt;000&amp;lt;/code&amp;gt;&lt;br /&gt;
|-&lt;br /&gt;
|5&lt;br /&gt;
|7&lt;br /&gt;
|&amp;lt;code&amp;gt;010_&amp;lt;/code&amp;gt;&lt;br /&gt;
|-&lt;br /&gt;
|6&lt;br /&gt;
|8&lt;br /&gt;
|&amp;lt;code&amp;gt;010_0&amp;lt;/code&amp;gt;&lt;br /&gt;
|-&lt;br /&gt;
|7&lt;br /&gt;
|13&lt;br /&gt;
|&amp;lt;code&amp;gt;0110__&amp;lt;/code&amp;gt;&lt;br /&gt;
|-&lt;br /&gt;
|8&lt;br /&gt;
|28&lt;br /&gt;
|&amp;lt;code&amp;gt;101_10_&amp;lt;/code&amp;gt;&lt;br /&gt;
|-&lt;br /&gt;
|9&lt;br /&gt;
|717&lt;br /&gt;
|&amp;lt;code&amp;gt;1011_00_&amp;lt;/code&amp;gt;&lt;br /&gt;
|-&lt;br /&gt;
|10&lt;br /&gt;
|≥ 1,626,862&lt;br /&gt;
|&amp;lt;code&amp;gt;1001_1_00&amp;lt;/code&amp;gt;&lt;br /&gt;
|-&lt;br /&gt;
|11&lt;br /&gt;
|≥ 1,859,166&lt;br /&gt;
|&amp;lt;code&amp;gt;10_10010_0&amp;lt;/code&amp;gt;&lt;br /&gt;
|-&lt;br /&gt;
|12&lt;br /&gt;
|≥ 6,328&lt;br /&gt;
|&amp;lt;code&amp;gt;0111__010_0&amp;lt;/code&amp;gt;&lt;br /&gt;
|-&lt;br /&gt;
|13&lt;br /&gt;
|≥ 5,217,735&lt;br /&gt;
|&amp;lt;code&amp;gt;001110_1_0_0&amp;lt;/code&amp;gt;&lt;br /&gt;
|-&lt;br /&gt;
|14&lt;br /&gt;
|≥ 154,171,565&lt;br /&gt;
|&amp;lt;code&amp;gt;01011__0_0100&amp;lt;/code&amp;gt;&lt;br /&gt;
|-&lt;br /&gt;
|15&lt;br /&gt;
|≥ 995,677,080&lt;br /&gt;
|&amp;lt;code&amp;gt;111010__0_1_00&amp;lt;/code&amp;gt;&lt;br /&gt;
|}&lt;br /&gt;
&lt;br /&gt;
==See also==&lt;br /&gt;
* [[Tiny Tag]]&lt;br /&gt;
&lt;br /&gt;
== Sources ==&lt;br /&gt;
GitHub repository (with documentation, deciders and holdout lists): https://github.com/AzertyWasTaken/Busy-Beaver/tree/main/Cyclic%20Tag%20System&lt;br /&gt;
[[Category:functions]]&lt;/div&gt;</summary>
		<author><name>Teoet6</name></author>
	</entry>
</feed>