Jelaskan Sejarah dari Masalah kata untuk grup

Sepanjang sejarah subjek, komputasi dalam kelompok telah dilakukan menggunakan berbagai  bentuk normal. Ini biasanya secara implisit memecahkan masalah kata untuk kelompok yang bersangkutan. Pada tahun 1911 Max Dehn mengusulkan bahwa masalah kata adalah bidang studi penting dalam dirinya sendiri, bersama dengan masalah konjugasi dan masalah isomorfisme grup. Pada tahun 1912 ia memberikan algoritme yang memecahkan masalah kata dan konjugasi untuk grup fundamental dari manifold dua dimensi yang dapat diorientasikan tertutup dari genus yang lebih besar dari atau sama dengan 2.  Penulis selanjutnya telah memperluas  Algoritma Dehn dan menerapkannya ke berbagai teori grup masalah keputusan.

Hal ini ditunjukkan oleh Pyotr Novikov pada tahun 1955 bahwa terdapat kelompok  G  yang disajikan secara terbatas sehingga kata masalah untuk  G  adalah  tidak dapat diputuskan. Segera diikuti bahwa masalah kata seragam juga tidak dapat diputuskan. Bukti berbeda diperoleh oleh  William Boone pada tahun 1958.

Kata masalah adalah salah satu contoh pertama dari masalah yang tidak dapat diselesaikan yang tidak ditemukan di logika matematika atau teori algoritma, tetapi di salah satu cabang utama matematika klasik,  aljabar. Sebagai hasil dari ketidakmampuannya, beberapa masalah lain dalam teori gruo kombinatorial telah terbukti tidak dapat diselesaikan juga.

Penting untuk disadari bahwa kata problem sebenarnya dapat dipecahkan untuk banyak grup  G . Misalnya, grup polisiklik memiliki masalah kata yang dapat dipecahkan karena bentuk normal dari kata arbitrer dalam presentasi polisiklik mudah dihitung; algoritma lain untuk grup mungkin, dalam keadaan yang sesuai, juga memecahkan masalah kata, lihat Algoritma Todd-Coxeter dan Algoritma penyelesaian Knuth–Bendix. Di sisi lain, fakta bahwa algoritme tertentu tidak menyelesaikan masalah kata untuk grup tertentu tidak menunjukkan bahwa grup tersebut memiliki masalah kata yang tidak dapat diselesaikan. Misalnya algoritma Dehn tidak memecahkan masalah kata untuk grup fundamental dari torus. Bagaimanapun kelompok ini adalah produk langsung dari dua grup siklik tak hingga dan memiliki masalah kata yang dapat dipecahkan.