Representation of turing reducibility by word and conjugacy problems in finitely presented groups
Donald J. Collins · Acta Mathematica · 1972
Introduction.We consider the relationship between the word and conjugacy problems in finitely presented groups.In any finitely presented group G a word is equal to the identity if and only if it is conjugate to the identity.This means that if there exists an algorithm to solve the conjugaey problem for G, then there exists an algorithm to solve the word problem for G.More generally, using the language of Turing degrees of unsolvability, we can assert that if the word problem for G is of degree a and the conjugacy problem for G is of degree b then a and b are recursively enumerable degrees (r.e.degrees) and a ~<b.Our aim is to determine for which pairs a and b of r.e.degrees with a ~<b, there exists a finitely presented group whose word problem is of degree a and whose conjugacy problem is of degree b.Now it is known that for every r.e.degree a there is a finitely presented group whose word problem is of degree a (Boone [4], Clapham [6] and Fridman [8,9]).Also, for every r.e.degree b there exists a finitely presented group whose conjugacy problem is of degree b (Bokut' [3], the author [7] and Miller [10]).Now it happens that the groups constructed by Bokut', the author and Miller all have solvable word problem.It is therefore a priori possible (but unlikely) that if a finitely presented group has unsolvable word problem, then its conjugacy problem is of the highest possible r.e.degree.A more natural conjecture is that any two r.e.degrees a and b with a ~b are the degrees of the word and conjugacy problems for a suitable finitely presented group.Our main result settles the issue.TH]~ORWM.Let a and b be recursively enumerable Turing degrees o/unsolvability such that a <. b.Then there is a/initely presented group whose word problem is o/degree a and whose conjugacy problem is o/degree b.One point should be noted.We know from [3], [7] and [10] that for any r.e.degree b there exists a finitely presented group Gl(b ) whose word problem is solvable and whose conjugacy problem is of degree b.In order to prove the theorem, it would suffice to construct,