After a brief discussion of historical matters in §1, twenty-seven predicates of formal grammers are introduced in §2. The next two sections discuss recursively enumerable predicates and nonrecursively enumerable predicates, respectively. These results show that the degree of unsolvability of a predicate is determined by its domain of definition. The paper concludes with a degree diagram and suggestions for further development.

Using the concept of one-one reducibility, it is shown that 12 unsolvable problems of formal grammars are of the same degree of unsolvability.For 1 < i < 12 and 1 < j < 20there are one-one effective maps fii such that f~l is effective, and f~j(~) C SC] where SC is a general problem of the formal grammars considered.KEY WORDS AND PHRASES: formal grammars, Post correspondence problem, partial correspondence problem, one-one equivalent reducibility, one-one degrees, general problem, halting problem, ambiguity problem, nonrecursively enumerable degrees, unsolvability, decision problem for a recursively enumerable set of nonnegative integers, recursively enumerable degrees CR CATEGORIES: 4.22, 5.21, 5.22, 5.23, 5.24 By a problem P is meant a recursive collection 1 of questions in some specified language such that the correct answer to each question is either Yes or No.The problem P is said to be a reeursively enumerable problem, if there is a reeursive function which enumerates those questions p0 which have the answer Yes or one which enumerates those questions P1 which have the answer No.A general problem (P is a family of problems, and (p will be said to be a reeursively enumerable general problem if each of the problems P ~ 6 ~ is a recursively enumerable problem.Examples of general problems are the general halting problem for Turing machines and the general word problem for Thue systems.The general halting problem for Turing machines is the problem of determining for an arbitrary Turing machine M, given arbitrary initial tape content and initial state q0 of M, whether or not M, started in state q0 on that initial tape content, eventually halts.Let us agree that for any two general problems (Pl and (P~, (Pl is one-one strongly reducible to (P: if for each P1 C (Pl there is a P2 E (P2 such that P1 i is one-one reducible to P iin the sense of Post [1, p. 297] for some pair i,j C {0, 1}.The general problem ~i is said to be one-one equivalently reducible to the general problem ~2 provided that for each P1 E (P1 there is a P2 C (P2 such that p i is one-one reducible to P~ and P2 j is one-one reducible to Pi ~ for some i, j E {0, 1} .Analogous definitions can be given for many-one, bounded truth table, unbounded truth table, and general Turing strong reducibility and equivalent reducibility of general problems.We can now state our results.THEOREM 1.Every recursively enumerable general problem is one-one equivalently reducible to each of the following general problems: ~ the general Post correspondence problem with axiom, the general partial correspondence problem with axiom.In par-* Computer Science Department Z Throughout the following we will assume that the questions of P can be arithmetized into unique natural numbers and we denote the subset of questions of P with answer Yes and No by p0 and p1, respectively.Precise definitions of these general problems are given later in Section 1.

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.