Masalah kata untuk grup

Dalam matematika, terutama di bidang aljabar abstrak dikenal sebagai teori grup kombinatorial, masalah kata untuk grup yang dihasilkan secara hingga  G  adalah masalah algoritmik untuk memutuskan apakah dua kata dalam generator mewakili elemen yang sama. Lebih tepatnya, jika  A  adalah himpunan terbatas  generator untuk  G  maka kata uji coba adalah masalah keanggotaan untuk bahasa formal dari semua kata dalam  A  dan sekumpulan formal invers yang memetakan identitas di bawah peta alami dari monoid bebas. Jika  B  adalah himpunan penghasil hingga lain untuk  G , maka masalah kata di himpunan pembangkit  B  setara dengan masalah kata di atas himpunan pembangkit  A . Jadi seseorang dapat berbicara dengan jelas tentang desidabilitas dari masalah kata untuk grup  G  yang dihasilkan secara tak terbatas.

Masalah kata seragam yang terkait tetapi berbeda untuk kelas  K  dari grup yang disajikan secara rekursif adalah masalah algoritmik dalam memutuskan, diberikan sebagai masukan  presentasi  P  untuk grup  G  di kelas  K  dan dua kata di generator  G , baik kata mewakili elemen yang sama dari  G . Beberapa penulis mensyaratkan kelas  K  untuk didefinisikan oleh sekumpulan presentasi secara rekursif dapat dihitung.

Sejarah 

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.

Penjelasan yang lebih konkrit 

Dalam istilah yang lebih konkret, soal kata seragam dapat diekspresikan sebagai pertanyaan menulis ulang, untuk pita literal. Untuk presentasi  P  dari grup  G ,  P  akan menentukan sejumlah generator

x, y, z, ...

untuk  G . Kita perlu memperkenalkan satu huruf untuk  x  dan huruf lainnya (untuk kenyamanan) untuk elemen grup yang diwakili oleh x−1. Sebut huruf-huruf ini (dua kali lebih banyak dari generator) alfabet  untuk masalah kita. Kemudian setiap elemen di  G  diwakili dalam  beberapa cara  oleh produk

abc ... pqr

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 .

Contoh 
Grup berikut memiliki masalah kata yang bisa dipecahkan:
 Grup otomatis, termasuk:
 Grup hingga
  Grup melengkung negatif (alias hiperbolik)
 Grup Euklides
 Grup Coxeter
 Grup kepang
 Grup hingga geometris 
Dibuat tanpa batas grup gratis
 Dibuat tanpa batas grup abelian bebas
 Grup poliklik
Dibuat secara rekursif  grup obsolut, termasuk:
 Grup sederhana yang disajikan dengan sempurna.
 Grup residual finite yang ditampilkan secara terbatas
Satu grup relator (ini adalah teorema Magnus), termasuk:
 Gruo dasar manifold dua dimensi berorientasi tertutup.
 Kelompok yang dapat diserang
 Grup autostackable

Contoh dengan masalah kata yang tidak terpecahkan juga diketahui:
 Diberikan himpunan yang dapat dihitung secara rekursif  A  dari bilangan bulat positif yang memiliki masalah keanggotaan yang tidak terpecahkan, ⟨a,b,c,d | anban = cndcn : n ∈ A⟩ adalah grup yang dihasilkan secara terbatas dengan presentasi yang dapat dihitung secara rekursif yang masalah katanya tidak terpecahkan
Setiap grup yang dihasilkan secara terbatas dengan presentasi yang dapat dihitung secara rekursif dan masalah kata yang tidak terpecahkan adalah subkelompok dari grup yang disajikan secara terbatas dengan masalah kata yang tidak dapat larut
Jumlah relator dalam kelompok yang disajikan secara terbatas dengan masalah kata yang tidak terpecahkan mungkin serendah 14 kali atau bahkan 12 kali.
Contoh eksplisit dari presentasi singkat yang masuk akal dengan masalah kata yang tidak terpecahkan diberikan dalam Collins 1986:

Solusi parsial dari masalah kata 

Masalah kata untuk grup yang disajikan secara rekursif dapat diselesaikan sebagian dalam pengertian berikut:

Diberikan presentasi rekursif P = ⟨X|R⟩ untuk grup  G , tentukan:

lalu ada fungsi rekursif parsial fP yaitu:

Lebih informal, ada algoritma yang berhenti jika  u = v , tapi tidak melakukannya sebaliknya.

Oleh karena itu, untuk menyelesaikan masalah kata untuk  P  cukup dengan membangun fungsi rekursif g sedemikian rupa sehingga:

Namun  u = v  di  G  jika dan hanya jika  di  G . Oleh karena itu, untuk menyelesaikan masalah kata untuk  P  cukup dengan membangun fungsi rekursif  h  sehingga:

Contoh 
Berikut ini akan dibuktikan sebagai contoh penggunaan teknik ini:

 Teorema: Grup residual finit yang disajikan secara terbatas memiliki masalah kata yang dapat dipecahkan.

Bukti: Seharusnya G = ⟨X|R⟩ adalah suatu grup yang terbatas sisa.

Misalkan  S  menjadi grup dari semua permutasi dari N, bilangan asli, yang memperbaiki semua kecuali banyak bilangan hingga:
 S adalah  terbatas lokal dan berisi salinan dari setiap grup hingga.
 Masalah kata dalam  S  dapat dipecahkan dengan menghitung produk permutasi.
 Ada pencacahan rekursif dari semua pemetaan himpunan hingga  X  menjadi  S .
 Karena  G  adalah residual finite, jika  w  adalah sebuah kata di generator  X  dari  G  maka  dalam  G  jika dan hanya beberapa pemetaan  X  menjadi  S  menyebabkan homomorfisme sedemikian rupa sehingga  pada S.

Dengan fakta-fakta ini, algoritma ditentukan oleh pseudocode berikut:

 For setiap pemetaan X menjadi S
     If setiap relator di R puas di S
         If w ≠ 1 pada S
             return 0
         End if
     End if
 End for

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:

Ada fungsi rekursif  yaitu:

Menulis:

Kemudian karena konstruksi  f  seragam, ini adalah fungsi rekursif dari dua variabel.

Maka dari itu:  bersifat rekursif. Dengan konstruksi:

Karena  S  adalah grup sederhana, satu-satunya grup hasil bagi adalah dirinya sendiri dan grup trivial. Karena itu:

Adanya fungsi seperti itu cukup untuk membuktikan bahwa masalah kata dapat dipecahkan untuk  S .

Bukti ini tidak membuktikan adanya algoritma yang seragam untuk menyelesaikan masalah kata untuk kelas kelompok ini. Ketidakseragaman terletak pada pemilihan elemen non-sepele dari kelompok sederhana. Tidak ada alasan untuk menganggap bahwa ada fungsi rekursif yang memetakan presentasi dari grup sederhana ke elemen non-trivial grup. Namun, dalam kasus grup yang disajikan secara terbatas, kami tahu bahwa tidak semua generator bisa sepele (Generator individual apa pun, tentu saja). Menggunakan fakta ini dimungkinkan untuk memodifikasi bukti untuk menunjukkan:

Masalah kata dapat dipecahkan secara seragam untuk kelas kelompok sederhana yang disajikan secara terbatas.

Lihat pula 
 Kombinatorik pada kata
 SQ-grup universal
 Masalah kata (matematika)
 Reachability problem
  Automata tumpukan bersarang (telah digunakan untuk memecahkan masalah kata untuk grup)

Catatan

Referensi 

 W. W. Boone, F. B. Cannonito, and R. C. Lyndon. Word Problems: Decision Problem in Group Theory. Netherlands: North-Holland. 1973.
 
 

 
 
 
 

 A. V. Kuznetsov, "Algorithms as operations in algebraic systems", Izvestia Akad. Nauk SSSR Ser Mat (1958)
 C. F. Miller. "Decision problems for groups -- survey and reflections." In Algorithms and Classification in Combinatorial Group Theory, pages 1–60. Springer, 1991.

 

Teori grup
Kombinatorik pada kata-kata
Artikel dengan contoh kodesemu