The general decision problem for Markov algorithms with axiom.
Charles E. Hughes · Notre Dame Journal of Formal Logic · 1975
Introduction* Let Mj denote the general decision problem for Markov algorithms with axiom.Of interest to us is whether or not this class of problems is as richly structured, with regard to degrees of unsolvability, as those classes studied in Hughes, Overbeek, and Singletary [2].In this paper we shall present proofs which show this to be so.In particular we shall show that the general decision problem for the range of total recursive functions is many-one reducible to Mj and consequently that every r.e.many-one degree of unsolvability is represented by Mj.Furthermore we shall show this result to be best possible, with regard to degree representation, in that every r.e.one-one degree is not represented by this family of decision problems.And finally we shall demonstrate a simple application of these results to the study of splinters.Preliminaries A semi-Thue system S is a pair (Σ, P) where Σ is a finite alphabet and P is a finite set of rules each of which is of the form a -> β, for a and β words over Σ.For any arbitrary pair of words W ι , W 2 over Σ, we say that W 2 is an immediate successor of W λ in S, denoted (W l9 W 2 )s, if there exist a pair of words £/, V over Σ and a rule a -» β in P such that W x = UaV and W 2 = UβV.W 2 is said to be derivable from W 1 in S, denoted Wi \~s W 2 , if eitheror (ii) there exists a finite sequence V l9 . .., F&, where k > 1, of words over Σ such that W x = V u W 2 Ξ V k , and (V, , V i+ι ) s , for i = 1, . .., k -1.A Markov alogorithm M is a pair (Σ, P) where Σ is a finite alphabet and P = {oiiRi βi\ 1 ^ i ^ m] is a finite ordered set of rules where