作者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