Jelaskan return 0 dari Masalah kata untuk grup

mendefinisikan fungsi rekursif  h  seperti itu:

Ini menunjukkan bahwa  G  memiliki masalah kata yang dapat dipecahkan.

Struktur aljabar dan soal kata

Ada beberapa hasil yang menghubungkan solvabilitas dari soal kata dan struktur aljabar. Yang paling signifikan dari ini adalah Teorema Boone-Higman:

Grup yang disajikan secara terbatas memiliki masalah kata yang dapat dipecahkan jika dan hanya jika dapat disematkan dalam grup sederhana yang dapat disematkan dalam grup yang disajikan secara terbatas.

Dipercaya secara luas bahwa konstruksi harus mungkin dilakukan sehingga kelompok sederhana itu sendiri disajikan dengan baik. Jika demikian, orang akan sulit untuk membuktikannya karena pemetaan dari presentasi ke grup sederhana harus non-rekursif.

Berikut ini telah dibuktikan oleh Bernhard Neumann dan Angus Macintyre:

Grup yang disajikan secara terbatas memiliki masalah kata yang dapat dipecahkan jika dan hanya jika dapat disematkan di setiap grup tertutup aljabar

Hal yang luar biasa tentang hal ini adalah bahwa grup tertutup secara aljabar sangat liar sehingga tidak ada yang memiliki presentasi rekursif.

Hasil tertua yang menghubungkan struktur aljabar dengan solvabilitas masalah kata adalah teorema Kuznetsov:

Grup sederhana yang disajikan secara rekursif  S  memiliki masalah kata yang dapat dipecahkan.

Untuk membuktikan ini mari ⟨X|R⟩ menjadi presentasi rekursif untuk  S . Pilih  a  ∈ S sehingga  a  ≠ 1 pada  S .

Jika  w  adalah kata pada generator  X  dari  S , maka biarkan: