login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A337537 Period of orbit of Post's tag system ({0,1},{(0,0101100),(1,11000111100000)},10,(1+0^9)^n). 0
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 18 23:16 EDT 2021. Contains 345125 sequences. (Running on oeis4.)