A Remark on Post Normal Systems

ABSTRACT

Let N(T) be the normal system of Post which corresponds to the Thue system, T, as in Martin Davis, Computability and Unsolvability (McGraw-Hill, New York, 1958), pp. 98-100. It is proved that for any recursively enumerable degree of unsolvability, D, there exists a normal system, NT(D), such that the decision problem for NT(D) is of degree D. Define a generalized normal system as a normal system without initial assertion. For such a GN the decision problem is to determine for any enunciations A and B whether or not A and B are equivalent in GN. Thus the generalized system corresponds more naturally to algebraic problems. It is proved that for any recursively enumerable degree of unsolvability, D, there exists a generalized normal system, GNT(D), such that the decision problem for GNT(D), such that the decision problem for GNT(D) is of degree D.

REFERENCES

• 1: BOONE, W. W. Word problems and reeursively enumerable degrees of unsolvability. A first paper on Thue systems. Ann. Math. 83 (1966), 520-571.
• 2: ----, AND RO~ERS, H., JR. On a problem of J. H. C. Whitetmad and a problem of Alonzo Church. Math. Scand. (to appear).
• 3: DAvis, MARTIN. Computability and Unsolvability. McGraw-Hill, New York, 1958.
• 4: IHRIG, A .H . Remarks about Post normal systems. Amer. Math. Soc. Notices, No. 64T-9.
• 5: POST, EMIL L. Formal reduction of the general combinatorial decision problem. Amer. J. Math. 65 (1943), 197-215.
• 6: Recursive unsolvability of a problem of Thue. J. Symbolic Logic 12 (1947), 1-11.
• 7: SINGLETARY, W. E. Private communication.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Thue systems

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Computability theory

General Terms:
Theory, Verification