Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

2026-08-25T03:58:11Z

Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29503656; atribusi sumber disertakan.

2026-08-25T03:18:10Z

Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29503656; atribusi sumber disertakan.

Halaman baru

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 [[Generating set of a group | 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 grup | 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 (penulisan ulang abstrak) | 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 algoritma 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 [[Teori pembatalan kecil#Algoritma Dehn | 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 [[Masalah yang tidak dapat diputuskan | tidak dapat diputuskan]]. Segera diikuti bahwa masalah kata seragam juga tidak dapat diputuskan. Bukti berbeda diperoleh oleh [[William Boone (matematikawan) | 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 abstrak | 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 algoritma 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 <math>\Sigma</math> untuk masalah kita. Kemudian setiap elemen di '' G '' diwakili dalam '' beberapa cara '' oleh produk

:''abc ... pqr''

simbol dari <math>\Sigma</math>, dari beberapa panjang, dikalikan dengan '' G ''. String dengan panjang 0 ([[pita kosong | 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'' | ''a''3}. 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 | 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 [[Presentasi absolut grup | 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 asli|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:
:<math>\begin{array}{lllll}\langle & a,b,c,d,e,p,q,r,t,k & | & &\\
&p^{10}a = ap, &pacqr = rpcaq, &ra=ar, &\\
&p^{10}b = bp, &p^2adq^2r = rp^2daq^2, &rb=br, &\\
&p^{10}c = cp, &p^3bcq^3r = rp^3cbq^3, &rc=cr, &\\
&p^{10}d = dp, &p^4bdq^4r = rp^4dbq^4, &rd=dr, &\\
&p^{10}e = ep, &p^5ceq^5r = rp^5ecaq^5, &re=er, &\\
&aq^{10} = qa, &p^6deq^6r = rp^6edbq^6, &pt=tp, &\\
&bq^{10} = qb, &p^7cdcq^7r = rp^7cdceq^7, &qt=tq, &\\
&cq^{10} = qc, &p^8ca^3q^8r = rp^8a^3q^8, &&\\
&dq^{10} = qd, &p^9da^3q^9r = rp^9a^3q^9, &&\\
&eq^{10} = qe, &a^{-3}ta^3k = ka^{-3}ta^3 &&\rangle \end{array}</math>

== 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:
:::<math>S=\{\langle u,v \rangle : u \text{ dan } v \text{ adalah kata-kata } X \text{ dan } u=v \text{ pada } G\ \}</math>
::lalu ada fungsi rekursif parsial ''fP'' yaitu:
:::<math>f_P(\langle u,v \rangle) =
\begin{cases}
0 &\text{jika}\ \langle u,v \rangle \in S \\
\text{tidak terdefinisi/tidak berhenti}\ &\text{if}\ \langle u,v \rangle \notin S
\end{cases}</math>

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:
::<math>g(\langle u,v \rangle) =
\begin{cases}
0 &\text{jika}\ \langle u,v \rangle \notin S \\
\text{tidak terdefinisi/tidak berhenti}\ &\text{jika}\ \langle u,v \rangle \in S
\end{cases}</math>

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:
::<math>h(x) =
\begin{cases}
0 &\text{jika}\ x\neq1\ \text{pada}\ G \\
\text{tidak terdefinisi/tidak berhenti}\ &\text{jika}\ x=1\ \text{pada}\ G
\end{cases}</math>

=== 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 [[grup hingga lokal | 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:

::<math>h(x) =
\begin{cases}
0 &\text{jika}\ x\neq 1\ \text{pada}\ G \\
\text{tidak terdefinisi/tidak berhenti}\ &\text{jika}\ x=1\ \text{pada}\ G
\end{cases} </math>

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:

::<math>S_w = \langle X | R\cup \{w\} \rangle.</math>

Ada fungsi rekursif <math>f_{\langle X | R\cup \{w\} \rangle}</math> yaitu:

::<math>f_{\langle X | R\cup \{w\} \rangle}(x) =
\begin{cases}
0 &\text{jika}\ x=1\ \text{pada}\ S_w\\
\text{tidak terdefinisi/tidak berhenti}\ &\text{jika}\ x\neq 1\ \text{pada}\ S_w.
\end{cases}</math>

Menulis:

::<math>g(w, x) = f_{\langle X | R\cup \{w\} \rangle}(x).</math>

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

Maka dari itu: bersifat rekursif. Dengan konstruksi:

::<math>h(w) =
\begin{cases}
0 &\text{jika}\ a=1\ \text{pada}\ S_w\\
\text{tidak terdefinisi/tidak berhenti}\ &\text{jika}\ a\neq 1\ \text{pada}\ S_w.
\end{cases}</math>

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

::<math>h(w) =
\begin{cases}
0 &\text{jika}\ w\ne 1\ \text{pada}\ S\\
\text{tidak terdefinisi/tidak berhenti}\ &\text{jika}\ w=1\ \text{pada}\ S.
\end{cases}</math>

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]]
* [[Otomat tumpukan bersarang#Sifat | Automata tumpukan bersarang]] (telah digunakan untuk memecahkan masalah kata untuk grup)

== Catatan ==

== Referensi ==
*
* W. W. Boone, F. B. Cannonito, and [[Roger Lyndon|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.
*
*

== Sumber dan atribusi ==

Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Masalah+kata+untuk+grup&oldid=29503656 Wikipedia bahasa Indonesia], revisi 29503656 (2026-07-29T07:31:16Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

Masalah kata untuk grup - Riwayat revisi

Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29503656; atribusi sumber disertakan.