A291793 Period of orbit of Post's tag system applied to the word (100)^n (version 2), or -1 if the orbit increases without limit.

2, 6, 6, 6, 0, 10, 28, 6, 10, 6, 6, 6, 0, 0, 6, 28, 10, 6, 10, 6, 6, 0, 6, 6, 0, 6, 6, 6, 6, 6, 6, 52, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 28, 6, 0, 0, 28, 6, 6, 6, 6, 6, 0, 6, 6, 6, 10, 6, 6, 6, 6, 0, 6, 0, 6, 6, 6, 6, 0, 6, 6, 6, 0, 6, 6, 6, 0, 10, 0, 10, 6, 6

Offset: 1

Author

N. J. A. Sloane, Sep 04 2017, based on Jeffrey Shallit's A284121

Keywords

• nonn

Comments

Post's tag system 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.

Here, following Asveld, a(n)=0 if the orbit ends at the empty word. On the other hand, Shallit defines a(n) to be 1 if that happens, which gives a different sequence, A284121.

From A.H.M. Smeets, Jul 16 2020: (Start)

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) 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.

Here, the period lengths a(n) refer to the tags ({0,1},{(0,00),(1,1101)},3,100^n).

a(n) is an even number. Proof: for each cycle the number of associations (productions) 0 -> 00 must equal the number of associations (productions) 1 -> 1101 applied within a cycle. (End)

Examples

			For n = 2 the orbit of (100)^2 = 100100 consists of a preperiod of length 15, followed by a periodic portion of length 6.
		

Links

• Lars Blomberg, Table of n, a(n) for n = 1..6075 (corrected for n=165 by _A.H.M. Smeets_)
• Peter R. J. Asveld, On a Post's System of Tag. Bulletin of the EATCS 36 (1988), 96-102.
• Lars Blomberg, Histogram over non-zero terms
• 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. A284116, A284119, A291792, A284121, A336287, A336327.

Programs

Python

def step(w):
    i = 0
    while w[0] != alfabet[i]:
        i = i+1
    w = w+suffix[i]
    return w[n:len(w)]
alfabet, suffix, n, ws, w0, m = "01", ["00","1101"], 3, "100", "", 0
while m < 83:
    w0, m = w0+ws, m+1
    w, ww, i, a = w0, w0, 0, 0
    while w != "" and a == 0:
        w, i = step(w), i+1
        if i%1000 == 0:
            ww = w
        else:
            if w == ww or w == "":
                if w != "":
                    a = i%1000
                print(m,a) # A.H.M. Smeets, Jul 16 2020

Extensions

a(50)-a(83) from Lars Blomberg, Sep 08 2017