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,1

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)

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

Example

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

Prog

(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

Crossrefs

Cf. A284116, A284119, A291792, A284121, A336287, A336327.

Sequence in context: A065486 A069806 A123945 * A284121 A198102 A097466

Adjacent sequences: A291790 A291791 A291792 * A291794 A291795 A291796

Keyword

nonn

Author

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

Extensions

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

Status

approved