(One can have lists instead of strings, replacing StringJoin by Flatten .) … With 2 string pairs PCP was shown to be decidable in 1981. … With r string pairs and n = StringLength[StringJoin[p]] there are 2 n Binomial[n - 1, 2r - 1] possible constraints (assuming no strings of zero length), each being related to at most 8 r!

With k colors each giving a string of the same length s the recurrence relation is Thread[Map[ ϕ [#][t + 1, ω ] &, Range[k] - 1]  Apply[Plus, MapIndexed[Exp[  ω (Last[#2] - 1) s t ] ϕ [#1][t, ω ] &, Range[k] - 1 /. rules, {-1}], {1}]/ √ s ] Some specific properties of the examples shown include: (a) (Thue–Morse sequence) The spectrum is essentially Nest[Range[2 Length[#]] Join[#, Reverse[#]] &, {1}, t] . … The generating function for the sequence (with 0 replaced by -1) satisfies f[z]  (1 - z) f[z 2 ] , so that f[z]  Product[1 - z 2 n , {n, 0, ∞ }] .