字問題

假設有人用一個表現給你一個群，並寫下一串由生成元及其逆構成的字串——一個字。你想知道一件看似簡單的事：把這個字乘開來，它是否等於單位元？換言之，一旦運用該群的關係，這串符號的乘積是否化為烏有？對固定表現中的所有字一致地提出的這個是非問題，就是字問題。

精確地說，有限表現群 G 的字問題，要求一個演算法：給定生成元上的任意字 w，判定在 G 中是否有 w = 1。這是 Max Dehn 於 1911 年提出的三個經典判定問題之一，另外兩個是共軛問題與同構問題。當這樣的演算法存在時，稱該群有可解的字問題；這是群本身的性質，而非某個表現的性質，因為更換表現這件事本身是演算法性的。

令人震驚的事實（由 Novikov 於 1955 年、Boone 於 1958 年獨立證明）是：存在字問題不可解的有限表現群——沒有任何演算法能判定它們的元素是否為單位元。所以字問題一般而言是不可判定的。然而極大類的群對它給出肯定回答——有限群、自由群、阿貝爾群與冪零群、雙曲群、自動群、剩餘有限的有限表現群——而幾何群論很大程度上是透過 Dehn 函數來度量這個問題到底有多難。