群の表示に関する決定問題の多くは一般には解けない（決定不能）ことが知られている。これは群論と計算理論の深い関係を示している。
語の問題
群 の語の問題（word problem）とは、 上の語 が与えられたとき、（ で単位元を表す）かどうかを判定する問題である。
であることは、 が の正規閉包に属することと同値である。
語の問題が解ける群
有限群では語の問題は解ける。すべての元を列挙して比較すればよい。
自由群では語の問題は解ける。語を簡約して空語になるかを調べる。
有限表示可解群、自動群（automatic group）、双曲群などで語の問題は解ける。
語の問題が解けない群
Novikov（1955）と Boone（1958）が独立に、語の問題が決定不能な有限表示群の存在を示した。
すなわち、ある有限表示群 に対して、任意の語 が で単位元かどうかを判定するアルゴリズムは存在しない。
共役問題
の共役問題（conjugacy problem）とは、2つの語 が与えられたとき、 と が で共役かどうかを判定する問題である。
語の問題が解けても共役問題は解けないことがある。
同型問題
2つの有限表示 と が同型な群を定義するかどうかを判定する問題を同型問題という。
同型問題は一般に決定不能である（Adian, Rabin）。
自明性問題
与えられた有限表示が自明群を定義するかどうかを判定する問題も決定不能である。
Dehn のアルゴリズム
曲面群や双曲群では、Dehn のアルゴリズムにより語の問題が線形時間で解ける。
関係式の「半分以上」が語に現れたら置換するという操作を繰り返す。
決定不能性の証明の概略
計算理論のチューリングマシンの停止問題を群の語の問題に帰着させる。
チューリングマシンの計算ステップを群の関係式でエンコードし、計算が停止することと特定の語が単位元になることを対応させる。
計算複雑性
語の問題が解ける群でも、その計算複雑性は様々である。
帰結
有限表示群の性質の多くは、表示から機械的に判定できない。
これらはすべて一般には決定不能である。
