字问题

假设有人用一个表现给你一个群，并写下一串由生成元及其逆构成的字符串——一个字。你想知道一件看似简单的事：把这个字乘开来，它是否等于单位元？换言之，一旦运用该群的关系，这串符号的乘积是否化为乌有？对固定表现中的所有字一致地提出的这个是非问题，就是字问题。

精确地说，有限表现群 G 的字问题，要求一个算法：给定生成元上的任意字 w，判定在 G 中是否有 w = 1。这是 Max Dehn 于 1911 年提出的三个经典判定问题之一，另外两个是共轭问题与同构问题。当这样的算法存在时，称该群有可解的字问题；这是群本身的性质，而非某个表现的性质，因为更换表现这件事本身是算法性的。

令人震惊的事实（由 Novikov 于 1955 年、Boone 于 1958 年独立证明）是：存在字问题不可解的有限表现群——没有任何算法能判定它们的元素是否为单位元。所以字问题一般而言是不可判定的。然而极大类的群对它给出肯定回答——有限群、自由群、阿贝尔群与幂零群、双曲群、自动群、剩余有限的有限表现群——而几何群论很大程度上是通过 Dehn 函数来度量这个问题到底有多难。