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

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

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

Table of n, a(n) for n=1..42.

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