Published online by Cambridge University Press: 12 March 2014
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.
The Main Result of the present paper was presented to the International Congress of Mathematicians, Moscow, August 1966.