語の問題と決定不能性

群の表示に関する決定問題の多くは一般には解けない（決定不能）ことが知られている。これは群論と計算理論の深い関係を示している。

語の問題

群 $G = ⟨ S ∣ R ⟩$ の語の問題（word problem）とは、 $S$ 上の語 $w$ が与えられたとき、 $w = e$ （ $G$ で単位元を表す）かどうかを判定する問題である。

$w = e$ であることは、 $w$ が $R$ の正規閉包に属することと同値である。

有限群では語の問題は解ける。すべての元を列挙して比較すればよい。

自由群では語の問題は解ける。語を簡約して空語になるかを調べる。

有限表示可解群、自動群（automatic group）、双曲群などで語の問題は解ける。

Novikov（1955）と Boone（1958）が独立に、語の問題が決定不能な有限表示群の存在を示した。

すなわち、ある有限表示群 $G$ に対して、任意の語 $w$ が $G$ で単位元かどうかを判定するアルゴリズムは存在しない。

$G$ の共役問題（conjugacy problem）とは、2つの語 $u, v$ が与えられたとき、 $u$ と $v$ が $G$ で共役かどうかを判定する問題である。

$u \sim v \Leftrightarrow \exists g \in G, v = gu g^{- 1}$

語の問題が解けても共役問題は解けないことがある。

2つの有限表示 $⟨ S_{1} ∣ R_{1} ⟩$ と $⟨ S_{2} ∣ R_{2} ⟩$ が同型な群を定義するかどうかを判定する問題を同型問題という。

同型問題は一般に決定不能である（Adian, Rabin）。

与えられた有限表示が自明群を定義するかどうかを判定する問題も決定不能である。

曲面群や双曲群では、Dehn のアルゴリズムにより語の問題が線形時間で解ける。

関係式の「半分以上」が語に現れたら置換するという操作を繰り返す。

計算理論のチューリングマシンの停止問題を群の語の問題に帰着させる。

チューリングマシンの計算ステップを群の関係式でエンコードし、計算が停止することと特定の語が単位元になることを対応させる。

語の問題が解ける群でも、その計算複雑性は様々である。

自由群：線形時間

双曲群：線形時間

自動群：二次時間

一般の解ける群：指数時間以上もありうる

有限表示群の性質の多くは、表示から機械的に判定できない。

群が自明か

群が有限か

群が可換か

群がある特定の群と同型か

これらはすべて一般には決定不能である。