A337537 - OEIS

%I #11 Jan 08 2021 20:19:52

%S 7,7,7,7,7,308,7,308,308,112,308,308,140,308,140,3429251,140,308,140,

%T 802613,3429251,140,140,3429251,802613,3429251,3429251,3429251,

%U 3429251,3429251,140,140,802613,3429251,802613,802613,140,802613,140,802613,802613,3429251

%N Period of orbit of Post's tag system ({0,1},{(0,0101100),(1,11000111100000)},10,(1+0^9)^n).

%C In general a tag as defined by Emil Leon Post, is given by a 4-tuple (Sigma,AF,n,w0), where Sigma is some (nonempty) set of symbols called the alphabet, AF is the associated function (sometimes also called set of production rules) AF: Sigma -> Sigma*, n is the deletion number and w0 the initial string.

%C From the starting sequence we obtain a new string in each step by adjoining the string associated to the prefix symbol of the string, where after the prefix n symbols are removed from the string.

%C The decision problem is: will the tag end up in an empty string, a(n) = 0 or not, a(n) <> 0?

%C This tag system was proposed by Liesbeth De Mol (p. 329).

%C a(n) == 0 (mod 7). Proof: for each cycle four times the number of associations (productions) 0 -> 0101100 must equal three times the number of associations (productions) 1 -> 11000111100000 applied within a cycle.

%H Liesbeth De Mol, <a href="http://www.clps.ugent.be/sites/default/files/publications/dissertation.pdf">Tracing unsolvability. A historical, mathematical and philosophical analysis with a special focus on tag systems</a>, Ph.D. Thesis, Universiteit Gent (2007). See page 329.

%H Emil L. Post, <a href="http://www.lib.ysu.am/articles_art/63062f3ed126193beb426becc0fbbe33.pdf">Formal reductions of the general combinatorial decision problem.</a>, American Journal of Mathematics, Vol. 65, No. 2 (Apr., 1943), pp. 197-215.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TagSystem.html">Tag System</a>

%Y Cf. A284119, A291793, A292091, A336287, A336327.

%K nonn

%O 1,1

%A _A.H.M. Smeets_, Aug 31 2020