The following theorem is a refinement of an unsolvability result due to E. Post:For any recursively enumerable degree D of recursive unsolvability there is a recursive class of sequences(of the same length)of nonempty words on an alphabet A such that the Post correspondence decision problem for that class is of degree D. This theorem is proved and then applied to obtain degree analogues of the ambiguity problem and the common program problem for the class of context-free grammars.

The correspondence decision problem was first formulated and shown to be recursively unsolvable in Post (1946). The method of proof was to reduce the known unsolvable decision problem for the class of normal systems on a, b to the correspondence decision problem. In the present paper the concept of a standard Post normal system is used so as to obtain some equivalence reductions of combinatorial systems. In particular the following main result is obtained.

At the Princeton Bicentennial in 1946 Tarski posed the question as to whether or not certain problems connected with partial propositional calculi were recursively solvable. Since that time the specific problems mentioned by Tarski as well as a number of related problems have been shown to be recursively unsolvable. Such results are due to Post and Linial [5], Yntema [9], Gladstone [2], Ihrig [3] and Singletary [7], [8].