Word problems and recursively enumerable degrees of unsolvability. A sequel on finitely presented groups

From MaRDI portal
Publication:2531870





The present paper is a sequel to and dependent upon the author's article [Ann. Math. (2) 83, 520--571 (1966; Zbl 0173.01204)]. Based on techniques utilized by Britton in his solution to the word problem for groups, the author gives explicit group theoretic constructions which, if added to the presentations of the Thue systems in the previous paper (referenced above), exhibit finitely presented groups with word problem of arbitrary recursively enumerable degree of unsolvability. (Result G). The precise connection between the degree of unsolvability of the word problems for the Thue system \( T \) and the finitely presented group \( G_{T} \) depending on \( T \) is given in Result \( F \) -- that is, an explicit recursive construction produces \( G_{T} \) from \( T \) and the degree of unsolvability for the respective word problems is equal. Among the interesting ancillary results is the existence of a finitely presented group with recursively solvable word problem such that the extended word problem in the sense of Magnu is recursively unsolvable. Contrary to the suggestion in footnote 4, page 50, it seems to be open whether or not there exists a finitely presented group with word problem of arbitrary truthtable degree. The difficulty here seems to be in the application of Britton's lemma in the presence of a requirement for full Turing reducibility instead of (sharper) reducibility. The author strongly conjectures that the assertion is valid, however. The paper is very comprehensive and is larded with the author's observations on the relations between this work and that of others, comments on the methods of proof of both the author's and others in solving these and related problems, and a wealth of conceptual suggestions. Unquestionably it is the present definitive work on the subject of r.e. degrees of unsolvability of various kinds of word problems in groups.











This page was built for publication: Word problems and recursively enumerable degrees of unsolvability. A sequel on finitely presented groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2531870)