Combinatorial systems with axiom.
Charles E. Hughes, Wilson E. Singletary · Notre Dame Journal of Formal Logic · 1973
Introduction:* The purpose of this paper is to investigate the general decision problems associated with a number of combinatorial systems with axiom. In particular, we shall show the many-one equivalence of the general halting problem for Turing machines, the general decision problem for Thue systems with axiom, the general decision problem for semi-Thue systems with axiom, and the general decision problem for Post normal systems with axiom. This, combined with a recent result of Overbeek [5], shows that every recursively enumerable (r.e.) many-one degree (of unsolvability) is represented by each of these general problems for systems with axiom. Finally, this latter result is proven to be best possible in that it does not hold for every r.e. one-one degree. Historical Background: Semi-Thue systems, Thue systems and Post normal systems were defined by Post as proper subsets of canonical forms. Decision problems associated with these systems have been studied by various authors, e.g., [l], [2], [3], [4], [6], [7], and [8]. In particular, W. E. Singletary [7] has combined results of his own and those of others in such a way as to provide an effective proof of the (r.e.) equivalence of the general decision problems which are of concern to us here. The stronger results to be proven here were announced in [4] and form part of an extensive study into the equivalence of general combinatorial decision problems. Preliminary Definitions: A semi-Thue system T is a pair (Σ,R) where Σ is a finite alphabet and R is a finite set of productions of the form a —» β, for a and β words over Σ. T is said to be a Thue system if a -* β belongs to R implies β —> a is also in R. For any arbitrary pair of words W, W r over Σ, we say that Wr is an immediate successor of W in T, denoted T(W, W) if W = P a Q, W = P β Q, P and Q are words over Σ, and a — β is inR.