Representation of Turing reducibility by word and conjugacy problems in finitely presented groups

DOI10.1007/BF02392160zbMath0229.20036MaRDI QIDQ2550077

Donald J. Collins

Publication date: 1972

Published in: Acta Mathematica (Search for Journal in Brave)

Mathematics Subject Classification ID

Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Recursively (computably) enumerable sets and degrees (03D25)

Related Items (6)

Unsolvable algorithmic problems for semigroups, groups and rings ⋮ Markov-Type Properties ⋮ Gröbner–Shirshov bases and their calculation ⋮ Groups with decidable word problem that do not embed in groups with decidable conjugacy problem ⋮ Gröbner-Shirshov basis for the braid group in the Birman-Ko-Lee generators. ⋮ Degree problems for modular machines

Cites Work

• Unnamed Item
• Unnamed Item
• Word problems and recursively enumerable degrees of unsolvability. A sequel on finitely presented groups
• Recursively enumerable degress and the conjugacy problem
• Machine Configuration and Word Problems of Given Degree of Unsolvability
• Finitely Presented Groups with Word Problems of Arbitrary Degrees of Insolubility
• The word problem

This page was built for publication: Representation of Turing reducibility by word and conjugacy problems in finitely presented groups