A336287 -id:A336287 - cp's OEIS frontend

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

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

nonn

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)

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

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

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

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

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

A336327 Period of orbit of Post's tag system ({0,1},{(0,0),(1,01101)},3,100^n).

Original entry on oeis.org

0, 4, 0, 4450, 0, 4450, 0, 0, 0, 4450, 0, 0, 6, 0, 0, 4450, 0, 0, 0, 0, 910, 4450, 0, 4450, 910, 4450, 0, 4450, 0, 4450, 910, 0, 0, 4450, 0, 4450, 910, 4, 0, 4, 0, 0, 910, 0, 6, 0, 910, 0, 0, 4450, 0, 4450, 910, 4450, 0, 292, 0, 4450, 0, 0, 910, 4450, 6, 4450

Offset: 1

A.H.M. Smeets, Jul 17 2020

nonn

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?
a(n) is an even number. Proof: for each cycle the number of associations (productions) 0 -> 0 must equal the number of associations (productions) 1 -> 01101 applied within a cycle.
For n=85 the tag is hard to solve by a brute force method, similar to the tag for n=110 with associated function {(0,00),(1,1101)} as reported in A284119.
Also period of orbit of Post's tag system ({0,1},{(0,0),(0,11010)},3,100^(n-1)).

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

Cf. A284119, A291793, A292091, A336287.

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", ["0", "01101"], 3, "100", "", 0
while m >= 0:
    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%100000 == 0:
            ww = w
        else:
            if w == ww or w == "":
                if w != "":
                    a = i%100000
                print(m, a)

Observed: if n is even then a(n) in {0, 4, 292, 4450}, if n is odd then a(n) in {0, 6, 910}.

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

Original entry on oeis.org

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

A.H.M. Smeets, Aug 31 2020

nonn

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.

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

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

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Extensions

A336327 Period of orbit of Post's tag system ({0,1},{(0,0),(1,01101)},3,100^n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs