半群的字问题(word problem for semigroups )是历史上最先被证明不可判定性的一个问题。所有有限半群和许多可数半群，可以由有穷个产生元及这些产生元组成的有穷串(称为字)上的有穷个等价关系(称为定义关系)产生。半群的字问题(word problem for semigroups )是历史上最先被证明不可判定性的一个问题。所有有限半群和许多可数半群，可以由有穷个产生元及这些产生元组成的有穷串(称为字)上的有穷个等价关系(称为定义关系)产生。例如，半群〈N，+〉可以由一个产生元产生(没有定义关系)，而〈n，+n〉(+n表示模n加法)则可以由一个产生元g使定义关系g～∧产生(∧表示空串，g表示i(i<n))。所谓半群的字问题是指：是否存在能行的算法，使得对任意由有穷个产生元和有穷个定义关系生成的半群，及由这些产生元组成的两个字W1，W2，该算法可以判定W1与W2在半群中是否表示同一个元。