20/05/17 12:23:52.57 OxYJzrF1.net
>>978の続き
有限表示群における決定不能問題
「Novikov–Boone の定理
群に対する語の問題に対する否定的な解答として、
任意の有限表示 ⟨S | R⟩ に対して、
与えられた二つの語 u, v がその群の同じ元を定めるか否か
を決定するアルゴリズムは存在しないことが知られている。
これは Pyotr Novikovが1955年に、
また別証明をWilliam Booneが1958年に
それぞれ得ている。」
20/05/17 12:23:52.57 OxYJzrF1.net
>>978の続き
有限表示群における決定不能問題
「Novikov–Boone の定理
群に対する語の問題に対する否定的な解答として、
任意の有限表示 ⟨S | R⟩ に対して、
与えられた二つの語 u, v がその群の同じ元を定めるか否か
を決定するアルゴリズムは存在しないことが知られている。
これは Pyotr Novikovが1955年に、
また別証明をWilliam Booneが1958年に
それぞれ得ている。」