[seqfan] Re: 3 more Post-type tag systems

[Allan Wechsler]

I believe Conway put some time into studying the first variant (1011),
perhaps under the impression that it was the one that had caught Post's
attention. He called it "Oo-Bobb", but I can't find any references to his
work online.

On Fri, Aug 18, 2017 at 3:51 PM, Neil Sloane <njasloane at gmail.com> wrote:

> Post's original tag system from the 1930's
> is based on the two strings 00 and 1101.
>
> There are 3 more tag systems of this type that were studied by
> Watanabe in 1962. See A284116 for an annotated scan of his paper.
>
> They can be defined by the strings {00,1011}, {00, 1110}, and
> {00,0111}.  I just created A291067, -8, -9 for them.
>
> The cross-refs line says:
>
> For the 3-shift tag systems (00,1101}, {00, 1011}, {00, 1110}, {00,
> 0111} see A284116, A291067, A291068, A291069 respectively (as well as
> the cross-referenced entries mentioned there).
>
> All three of the new ones need more terms.  There are also a lot of
> other subsidiary sequences that could be added to go with them (just
> as A284116 has a lot of cross-referenced children), in case people
> would like to help (Don?)
>
> The main open problem is (Allan W. will correct me if I'm wrong) to
> decide for the tag systems (00,1101} or {00, 1011} if there is any
> starting string that blows up. These are important unsolved questions
> going back 80 years or so.  Watanabe appears to assert that for the
> systems {00, 1110} and {00, 0111} there are no strings that blow up -
> but I did not check his proof.
>
> De Mol (see especially her thesis referenced in A284116) is a bit
> critical of the Watanabe paper, and I agree that his Fig 7 doesn't
> seem quite right.
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>