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!)
A289675 Consider the Post tag system described in A284116 (but adapted to the alphabet {1,2}) ; sequence lists the words that terminate in the empty word. 9
1, 2, 11, 12, 111, 112, 121, 122, 1111, 1121, 1211, 1221, 2111, 2121, 2211, 2221, 11111, 11112, 11121, 11122, 11211, 11212, 11221, 11222, 12111, 12112, 12121, 12122, 12211, 12212, 12221, 12222, 111111, 111112, 111121, 111122, 112111, 112112, 112121, 112122, 121111, 121112, 121121, 121122, 122111, 122112, 122121, 122122 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

Post's tag system maps a word w over {1,2} to w', where if w begins with 1, w' is obtained by appending 11 to w and deleting the first three letters, or if w begins with 2, w' is obtained by appending 2212 to w and deleting the first three letters.

Under this Post tag system, some words when iterated end at the empty word, others go into cycles, and others may have an orbit which grows without limit. See A289670 and A289671 for the counts of the first two types. This sequence gives a list of the words that end at the empty word.

We work over {1,2} rather than the official alphabet {0,1} because of the prohibition in the OEIS of terms (other than 0 itself) which begin with 0.

Stillwell (2016, page 100) remarks that Post was unable to find an algorithm to determine which words belong to this sequence, "and in fact this particular `halting problem' remains unsolved to this day".

REFERENCES

John Stillwell, Elements of Mathematics: From Euclid to Goedel, Princeton, 2016. See page 100, Post's tag system.

LINKS

Rémy Sigrist, Table of n, a(n) for n = 1..25000

Emil L. Post, Formal Reductions of the General Combinatorial Decision Problem, Amer. J. Math. 65, 197-215, 1943. See page 204.

EXAMPLE

Working over the more usual alphabet {0,1}, the following are the orbits of the first few words that terminate at the empty word:

[0, -1]

[1, 01, 0, -1]

[00, 0, -1]

[01, 0, -1]

[000, 00, 0, -1]

[001, 00, 0, -1]

[010, 00, 0, -1]

[011, 00, 0, -1]

[0000, 000, 00, 0, -1]

[0010, 000, 00, 0, -1]

[0100, 000, 00, 0, -1]

[0110, 000, 00, 0, -1]

[1000, 01101, 0100, 000, 00, 0, -1]

[1010, 01101, 0100, 000, 00, 0, -1]

[1100, 01101, 0100, 000, 00, 0, -1]

[1110, 01101, 0100, 000, 00, 0, -1]

[00000, 0000, 000, 00, 0, -1]

...

Writing the initial words in this list over {1,2} rather than {0,1} gives the sequence.

MATHEMATICA

A289675 = {};

Do[For[i = 0, i < 2^n, i++, lst = {};

   w = IntegerString[i, 2, n];

   While[! MemberQ[lst, w],

    AppendTo[lst, w];

    If[w == "", AppendTo[A289675, IntegerString[i, 2, n]]; Break[]];

    If[StringTake[w, 1] == "0", w = StringDrop[w <> "00", 3],

     w = StringDrop[w <> "1101", 3]]]], {n, 6}];

Map[StringReplace[#, {"1" -> "2", "0" -> "1"}] &, A289675]

(* Robert Price, Sep 26 2019 *)

CROSSREFS

Cf. A284116, A284119, A284121, A289670, A289671, A289672, A289673, A289674.

Sequence in context: A140148 A117547 A037091 * A127303 A286153 A068972

Adjacent sequences:  A289672 A289673 A289674 * A289676 A289677 A289678

KEYWORD

nonn

AUTHOR

N. J. A. Sloane, Jul 30 2017

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 August 14 07:04 EDT 2020. Contains 336477 sequences. (Running on oeis4.)