OFFSET
1,2
COMMENTS
This tag system has no halting symbol: the halting condition is reached when the word 1 is produced.
As proved by De Mol (2008), this tag system encodes the Collatz 3x+1 function T(x), where T(x)=x/2 if x is even, (3x+1)/2 if x is odd.
For each row n >= 1, if the tag system is started from the configuration encoding n (a word composed by n ones), and provided the Collatz conjecture is true, the iterations of the system will always reach the word 1 (after A351850(n) steps).
In her original work De Mol uses the alphabet {alpha, c, y}, which is replaced here by {1, 2, 3}.
LINKS
J. C. Lagarias, The 3x+1 Problem: An Overview, arXiv:2111.02635 [math.NT], 2021, p. 17.
J. C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, American Mathematical Society, 2010, p. 19.
Liesbeth De Mol, Tag systems and Collatz-like functions, Theoretical Computer Science, Volume 390, Issue 1, 2008, pp. 92-101.
Wikipedia, Tag system.
EXAMPLE
Written as an irregular triangle, the sequence begins:
1;
11, 23, 1;
111, 123, 323, 3111, 11111, 11123, ..., 2323, 231, 11, 23, 1;
1111, 1123, 2323, 231, 11, 23, 1;
11111, 11123, 12323, 32323, 323111, 3111111, ..., 1;
...
Each row includes (in the same order of appearance) the words encoding the terms in the corresponding row of A070168. E.g., row 4 includes the words 1111, 11, 1, which encode the numbers 4, 2, 1, respectively.
The following computation shows how row 3 is generated. In each step, symbols coming from the production rules (based on the first symbol of the previous word) are appended; the first two symbols of the word are then deleted.
111 (corresponding to the integer 3)
123 (appending 23, from production rule 1 -> 23)
323 (appending 23, from production rule 1 -> 23)
3111 (appending 111, from production rule 3 -> 111)
11111 (appending 111, from production rule 3 -> 111)
...
23 (appending 23, from production rule 1 -> 23)
1 (appending 1, from production rule 2 -> 1)
MATHEMATICA
t[s_]:=StringDrop[s, 2]<>StringReplace[StringTake[s, 1], {"1"->"23", "2"->"1", "3"->"111"}];
nrows=5; Table[NestWhileList[t, StringRepeat["1", n], #!="1"&], {n, nrows}]
PROG
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Paolo Xausa, Feb 22 2022
STATUS
approved