A284116 a(n) = largest number of distinct words arising in Post's tag system {00, 1101} applied to a binary word w, over all starting words w of length n, or a(n) = -1 if there is a word w with an unbounded trajectory.

4, 7, 6, 7, 22, 23, 24, 25, 30, 31, 34, 421, 422, 423, 422, 423, 424, 2169, 2170, 2171, 2170, 2171, 2172, 2165, 2166, 2167, 24566, 24567, 24568, 24567, 24568, 24569, 24568, 24569, 24570, 253513, 253514, 342079, 342080, 342083, 342084, 342103, 20858070

Offset: 1

Author

Jeffrey Shallit, Mar 20 2017

Keywords

• nonn

Comments

Post's tag system {00, 1101} maps a word w over {0,1} to w', where if w begins with 0, w' is obtained by appending 00 to w and deleting the first three letters, or if w begins with 1, w' is obtained by appending 1101 to w and deleting the first three letters.

The empty word is included in the count.

It is an important open question to decide if there is any word whose orbit grows without limit. - N. J. A. Sloane, Jul 30 2017, based on an email from Allan C. Wechsler

Comment from Don Reble, Aug 01 2017: For n <= 57, all words reach the empty word or a cycle. - N. J. A. Sloane, Aug 01 2017

From David A. Corneth, Aug 02 2017: (Start)

A word w can be described by the pair (c, d) where c is the length of w and d is the number represented by the binary word w. Then 0 <= d < 2^c.

Appending a word ww of m letters to w is the same as setting d to 2^m * w + ww. Preserving only the rightmost q digits of w is the same as setting w to w mod 2^q.

Lastly, we're only really interested in the 1st, 4th, 7th, ... leftmost digits. The others could without loss of generality be set to 0. This can be done with bitand(x, y), with y in A033138.

Therefore this problem can be formulated as follows: Let w = (c, d).

Then if d < 2^(c - 1), w' = (c - 1, bitand(4*d, floor(2^(c + 1) / 7)))

else (if (d >= 2^(c - 1)), w' = (c + 1, bitand(16*d + 13, floor(2^(c + 3) / 7))).

To find a(n), it would be enough to check values d in A152111 with n binary digits and c = n.

(End)

a(110) >= 43913328040672, from w = (100)^k, k=110. - N. J. A. Sloane, Oct 23 2017, based on Lars Blomberg's work on A291792.

Examples

			Suppose n=1. Then w = 0 ->000 -> w' = empty word, and w = 1 -> 11101 -> w' = 01 -> 0100 -> w'' = 0 -> 000 -> w''' = empty word. So a(1) = 4 by choosing w = 1.
For n = 5 the orbit of the word 10010 begins 10010, 101101, 1011101, ..., 0000110111011101, and the next word in the orbit has already appeared. The orbit consists of 22 distinct words.
From _David A. Corneth_, Aug 02 2017: (Start)
The 5-letter word w = 10100 can be described as (a, b) = (5, 20). This is equivalent to (5, bitand(20, floor(2^7 / 7))) = (5, bitand(20, 18)) = (5, 16).
As 16 >= 2^(5-1), w' = (5 + 1, bitand(16*16 + 13, floor(2^(5 + 3) / 7))) = (6, bitand(279, 36)) = (6, 4). w'' = w = (5, 16) so 10100 ~ 10000 ends in a period. (End)
Words w that achieve a(1) through a(7) are 1, 10, 100, 0001, 10010, 100000, 0001000. - _N. J. A. Sloane_, Aug 17 2017
		

References

• John Stillwell, Elements of Mathematics: From Euclid to Goedel, Princeton, 2016. See page 100, Post's tag system.

Links

• Peter R. J. Asveld, On a Post's System of Tag. Bulletin of the EATCS 36 (1988), 96-102.
• Liesbeth De Mol, Tracing unsolvability. A historical, mathematical and philosophical analysis with a special focus on tag systems, Ph.D. Thesis, Universiteit Gent, 2007.
• Liesbeth De Mol, Tag systems and Collatz-like functions Theoret. Comput. Sci. 390 (2008), no. 1, 92-101.
• Liesbeth De Mol, On the complex behavior of simple tag systems—an experimental approach, Theoret. Comput. Sci. 412 (2011), no. 1-2, 97-112.
• Emil L. Post, Formal Reductions of the General Combinatorial Decision Problem, Amer. J. Math. 65, 197-215, 1943. See page 204.
• Don Reble, Python program for A289670.
• Shigeru Watanabe, Periodicity of Post's normal process of tag, in Jerome Fox, ed., Proceedings of Symposium on Mathematical Theory of Automata, New York, April 1962, Polytechnic Press, Polytechnic Institute of Brooklyn, 1963, pp. 83-99. [Annotated scanned copy]

Crossrefs

Cf. A033138, A152111, A284119, A284121, A289670, A289671, A289672, A289673, A289674, A289675, A289676, A289677.

Cf. also A290436-A290441, A290741, A290742, A291792, A291793, A291794, A291795, A291796.

For the 3-shift tag systems {00,1101}, {00, 1011}, {00, 1110}, {00, 0111} see A284116, A291067, A291068, A291069 respectively (as well as the cross-referenced entries mentioned there).

Programs

Mathematica

Table[nmax = 0;
 For[i = 0, i < 2^n, i++, lst = {};
  w = IntegerString[i, 2, n];
  While[! MemberQ[lst, w],
   AppendTo[lst, w];
   If[w == "", Break[]];
   If[StringTake[w, 1] == "0", w = StringDrop[w <> "00", 3],
    w = StringDrop[w <> "1101", 3]]];
nmax = Max[nmax, Length[lst]]]; nmax, {n, 1, 12}] (* Robert Price, Sep 26 2019 *)
(* Or, using the (c,d) procedure: *)
 Table[nmax = 0;
 For[i = 0, i < 2^n, i++,
  c = n; d = i; lst = {};
  While[! MemberQ[lst, {c, d}],
   AppendTo[lst, {c, d}];
   If[c == 0,  Break[]];
   If[ d < 2^(c - 1),
    d = BitAnd[4*d, 2^(c - 1) - 1]; c--,
    d = BitAnd[16*d + 13, 2^(c + 1) - 1]; c++]];
nmax = Max[nmax, Length[lst]]]; nmax, {n, 1, 12}] (* Robert Price, Sep 26 2019 *)

Extensions

a(19)-a(43) from Lars Blomberg, Apr 09 2017

Edited by N. J. A. Sloane, Jul 29 2017 and Oct 23 2017 (adding escape clause in case an infinite trajectory exists)