login
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.
10
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.
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
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