Given an arbitrary positive integer n and a list of n+1 arbitrary words P₁,P₂,...,P_n,Q on the alphabet {1,2,...,n}, does repeated application of the tag operation t: ijX -> XP_i eventually convert Q into a word of length less than 2? That is, does the sequence Q, t¹(Q), t²(Q), t³(Q), ... terminate?

Historical note on the definition of tag system

The above definition differs from that of , whose tag systems use no halting symbol, but rather halt only

1.Previous
3.Next