The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A337537 Period of orbit of Post's tag system ({0,1},{(0,0101100),(1,11000111100000)},10,(1+0^9)^n). 0
 7, 7, 7, 7, 7, 308, 7, 308, 308, 112, 308, 308, 140, 308, 140, 3429251, 140, 308, 140, 802613, 3429251, 140, 140, 3429251, 802613, 3429251, 3429251, 3429251, 3429251, 3429251, 140, 140, 802613, 3429251, 802613, 802613, 140, 802613, 140, 802613, 802613, 3429251 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,1 COMMENTS 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. 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. The decision problem is: will the tag end up in an empty string, a(n) = 0 or not, a(n) <> 0? This tag system was proposed by Liesbeth De Mol (p. 329). 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. LINKS Liesbeth De Mol, Tracing unsolvability. A historical, mathematical and philosophical analysis with a special focus on tag systems, Ph.D. Thesis, Universiteit Gent (2007). See page 329. Emil L. Post, Formal reductions of the general combinatorial decision problem., American Journal of Mathematics, Vol. 65, No. 2 (Apr., 1943), pp. 197-215. Eric Weisstein's World of Mathematics, Tag System CROSSREFS Cf. A284119, A291793, A292091, A336287, A336327. Sequence in context: A158812 A285049 A265834 * A003880 A084503 A168292 Adjacent sequences:  A337534 A337535 A337536 * A337538 A337539 A337540 KEYWORD nonn AUTHOR A.H.M. Smeets, Aug 31 2020 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified June 18 23:16 EDT 2021. Contains 345125 sequences. (Running on oeis4.)