cp's OEIS Frontend

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.

%I A289675 #35 Sep 27 2019 07:49:51
%S A289675 1,2,11,12,111,112,121,122,1111,1121,1211,1221,2111,2121,2211,2221,
%T A289675 11111,11112,11121,11122,11211,11212,11221,11222,12111,12112,12121,
%U A289675 12122,12211,12212,12221,12222,111111,111112,111121,111122,112111,112112,112121,112122,121111,121112,121121,121122,122111,122112,122121,122122
%N 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.
%C A289675 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.
%C A289675 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.
%C A289675 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.
%C A289675 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".
%D A289675 John Stillwell, Elements of Mathematics: From Euclid to Goedel, Princeton, 2016. See page 100, Post's tag system.
%H A289675 Rémy Sigrist, <a href="/A289675/b289675.txt">Table of n, a(n) for n = 1..25000</a>
%H A289675 Emil L. Post, <a href="http://www.jstor.org/stable/2371809">Formal Reductions of the General Combinatorial Decision Problem</a>, Amer. J. Math. 65, 197-215, 1943. See page 204.
%e A289675 Working over the more usual alphabet {0,1}, the following are the orbits of the first few words that terminate at the empty word:
%e A289675 [0, -1]
%e A289675 [1, 01, 0, -1]
%e A289675 [00, 0, -1]
%e A289675 [01, 0, -1]
%e A289675 [000, 00, 0, -1]
%e A289675 [001, 00, 0, -1]
%e A289675 [010, 00, 0, -1]
%e A289675 [011, 00, 0, -1]
%e A289675 [0000, 000, 00, 0, -1]
%e A289675 [0010, 000, 00, 0, -1]
%e A289675 [0100, 000, 00, 0, -1]
%e A289675 [0110, 000, 00, 0, -1]
%e A289675 [1000, 01101, 0100, 000, 00, 0, -1]
%e A289675 [1010, 01101, 0100, 000, 00, 0, -1]
%e A289675 [1100, 01101, 0100, 000, 00, 0, -1]
%e A289675 [1110, 01101, 0100, 000, 00, 0, -1]
%e A289675 [00000, 0000, 000, 00, 0, -1]
%e A289675 ...
%e A289675 Writing the initial words in this list over {1,2} rather than {0,1} gives the sequence.
%t A289675 A289675 = {};
%t A289675 Do[For[i = 0, i < 2^n, i++, lst = {};
%t A289675    w = IntegerString[i, 2, n];
%t A289675    While[! MemberQ[lst, w],
%t A289675     AppendTo[lst, w];
%t A289675     If[w == "", AppendTo[A289675, IntegerString[i, 2, n]]; Break[]];
%t A289675     If[StringTake[w, 1] == "0", w = StringDrop[w <> "00", 3],
%t A289675      w = StringDrop[w <> "1101", 3]]]], {n, 6}];
%t A289675 Map[StringReplace[#, {"1" -> "2", "0" -> "1"}] &, A289675]
%t A289675 (* _Robert Price_, Sep 26 2019 *)
%Y A289675 Cf. A284116, A284119, A284121, A289670, A289671, A289672, A289673, A289674.
%K A289675 nonn
%O A289675 1,2
%A A289675 _N. J. A. Sloane_, Jul 30 2017