作者xcycl (XOO)
看板CSSE
标题[问题] Word problem
时间Tue Feb 3 23:44:23 2009
关於 Word problem 的介绍参考 wiki 这篇，
http://en.wikipedia.org/wiki/Word_problem_for_groups
简单来讲是这样，在一个 group 由我们规定一些等式，
例如 xy = 1 这样，等式可以是可数多个，全部称为 P，
那在这个群里头给两个元素，是否能判断这两个元素是一样的。
以前已经有人证明，存在即使 P 是有限等式下，对於判断
两个元素是否相等的问题是 undecidable。
我想问的是，对於此问题是否有进一步推广到其他的结构上，
甚至是 algebraic category 上？而不是只限於 group。
以及是否有相关的资料可以参考。谢谢！
--
实在不知道该贴在数学版还是这里好 XD
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 123.193.203.88
1F：推 ccshan:推广有，例如 monoid 的 undecidability 比 group 还简单 02/04 06:55
2F：→ ccshan:但是不知道你心目中要的是什麽资料 02/04 06:55
3F：→ xcycl:嗯～有比较完整的参考书吗？ 02/04 23:03