Informatics Report Series
Report
 EDI-INF-RR-0894
 Related Pages Report (by Number) Index Report (by Date) Index Author Index Institute Index Home
Title:Turing Degrees and the Word and Conjugacy Problems for Finitely Presented Groups
Authors: Kyriakos Kalorkoti
Date:Dec 2006
Publication Title:South East Asian Bulletin of Mathematics
Publication Type:Journal Article Publication Status:Published
Volume No:30 Page Nos:855-888
Abstract:
Let {\bf a}, {\bf b} be two recursively enumerable Turing degrees with ${\bf a}\leq_T{\bf b}$. It was shown by Bokut' [Degrees of unsolvability of the conjugacy problem for finitely presented groups' (in Russian), {\it Algebra i Logika Sem.}, 7 (1968), no.~5, 4--70; no.~6, 4--52] and Collins [Recursively enumerable degrees and the conjugacy problem', {\it Acta. Math.}, 122 (1969), 115--160] that there are finitely presented groups with solvable word problem but with conjugacy problem of degree {\bf b}. Later on Collins [Representation of Turing reducibility by word and conjugacy problems in finitely presented groups', {\it Acta. Math.}, 128 (1972), 73--90] generalised this by showing that there are finitely presented groups with word problem of degree {\bf a} and conjugacy problem of degree {\bf b}. In this paper we provide new proofs of these results. The proofs use modular machines and certain normal forms for Britton towers which were introduced by Bokut' [On a property of the Boone groups' (in Russian), {\it Algebra i Logika Sem.}, 5 (1966) No. 5, 5--23; 6 (1967) No.1, 15--24]. A fair amount of simplification results from this approach.