Skip to main content
3 of 3
added 72 characters in body
Francesco Polizzi
  • 66.3k
  • 5
  • 180
  • 283

The decidability of the word problem does not imply the decidability of the order problem, and in fact the following more general result holds.

Theorem. Let $\mathbf{a}, \, \mathbf{b}, \, \mathbf{c}$ be three recursively enumerable degrees of unsolvability (i.e., Turing degrees) with $\mathbf{a} \leq \mathbf{b}$ and $\mathbf{a} \leq \mathbf{c}$. Then there exists a finitely presented group $L$ such that

  • the word problem for $L$ is of degree $\mathbf{a};$
  • the power problem for $L$ is of degree $\mathbf{b};$
  • the order problem for $L$ is of degree $\mathbf{c}.$

See

D. J. Collins: The word, power and order problems in finitely presented groups, in "Word Problems, Decision Problems and the Burnside Problem in Group Theory", Studies in Logic and Fundations of Mathematics 71 (1973).

Francesco Polizzi
  • 66.3k
  • 5
  • 180
  • 283