Word problems and recursively enumerable degrees of unsolvability. A sequel on finitely presented groups
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.
- Turing degrees and the word and conjugacy problems for finitely presented groups.
- Algorithmically insoluble problems about finitely presented solvable groups, Lie and associative algebras. I
- scientific article; zbMATH DE number 3995984
- A finitely presented group with almost solvable conjugacy problem.
- Degrees of unsolvability of first order decision problems for finitely presented groups
- Model-theoretic and algorithmic questions in group theory
- Recursive functions in group theory
- Unsolvable algorithmic problems for semigroups, groups and rings
- The complexity of Grigorchuk groups with application to cryptography
- Turing degrees and the word and conjugacy problems for finitely presented groups.
- Recursively enumerable degress and the conjugacy problem
- A new non-Hopf group
- On recognising properties of groups which have solvable word problem
- On the complexity of reduction algorithms in Novikov-Boone constructions
- On the complexity of the identity problem for finitely defined groups
- Embeddings into hopfian groups
- Degrees of unsolvability of the conjugacy problem for finitely-presented groups
- Representation of Turing reducibility by word and conjugacy problems in finitely presented groups
- The word problem for finitely presented quandles is undecidable
- Degrees of word problem for algebras without finitely presented expansions
- The word problem and the isomorphism problem for groups
- Markov-Type Properties
- An algebraic characterization of groups with soluble word problem
- Recursively enumerable sets and degrees
- scientific article; zbMATH DE number 3439107 (Why is no real title available?)
- Degrees of unsolvability of first order decision problems for finitely presented groups
- On Britton's Theorem A
- Computability Theory and Differential Geometry
- Word problems and ceers
- Two results on complexities of decision problems of 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)