Combinatorial systems defined over one- and two-letter alphabets

In this paper we shall investigate some families of decision problems associated with a number of combinatorial systems whose alphabets are restricted to one and two letters. Our purpose is to try to gain a better understanding of the boundaries between classes of combinatorial systems whose decision problems are solvable and those whose decision problems are of any prescribed r.e. many-one degree of unsolvability. We show that, for one-letter alphabets, the decision problems considered here for semi-Thue systems, Thue systems, Post normal systems, Markov algorithms and Post correspondence classes are each solvable. In contrast, for two-letter alphabets, each such family of decision problems represents every r.e. many-one degree of unsolvability.