Jelaskan abc ... pqr dari Masalah kata untuk grup

simbol dari , dari beberapa panjang, dikalikan dengan  G . String dengan panjang 0 ( string null) adalah singkatan dari elemen identitas  e  dari  G . Inti dari keseluruhan masalah adalah untuk dapat mengenali  semua  cara  e  dapat direpresentasikan, dengan beberapa hubungan.

Efek dari  relasi  dalam  G  adalah membuat berbagai string tersebut mewakili elemen yang sama dari  G . Sebenarnya relasi menyediakan daftar string yang bisa dikenalkan di tempat yang kita inginkan, atau dibatalkan setiap kali kita melihatnya, tanpa mengubah 'nilai', yaitu elemen grup yang merupakan hasil perkalian.

Untuk contoh sederhana, ambil presentasi {a | a3}. Menulis  A  untuk kebalikan dari  a , kami memiliki kemungkinan string yang menggabungkan sejumlah simbol  a  dan  A . Kapanpun kita melihat  aaa , atau  aA  atau  Aa  kita mungkin mencoretnya. Kami juga harus ingat untuk mencoret  AAA ; Ini mengatakan bahwa karena kubus  a  adalah elemen identitas  G , begitu pula kubus dari kebalikan dari  a . Dalam kondisi seperti ini kata soal menjadi mudah. Pertama kurangi string menjadi string kosong,  a ,  aa ,  A  atau  AA . Kemudian perhatikan bahwa kami juga dapat mengalikan dengan  aaa , sehingga kami dapat mengonversi  A  menjadi  aa  dan mengubah  AA  menjadi  a . Hasilnya adalah bahwa masalah kata, di sini untuk grup siklik dari orde tiga, dapat dipecahkan.

Namun, ini bukan kasus yang khas. Sebagai contoh, kami memiliki bentuk kanonik tersedia yang mengurangi string apa pun menjadi satu string maksimal tiga, dengan mengurangi panjangnya secara monoton. Secara umum, tidak benar bahwa seseorang bisa mendapatkan bentuk kanonik untuk elemen, dengan pembatalan bertahap. Seseorang mungkin harus menggunakan relasi untuk memperluas pita berkali-kali lipat, untuk akhirnya menemukan pembatalan yang menurunkan panjangnya.

Hasilnya adalah, dalam kasus terburuk, bahwa hubungan antara string yang mengatakan mereka sama di  G  adalah  Masalah yang tidak dapat diputuskan .