- Source: 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
Σ
{\displaystyle \Sigma }
untuk masalah kita. Kemudian setiap elemen di G diwakili dalam beberapa cara oleh produk
abc ... pqr
simbol dari
Σ
{\displaystyle \Sigma }
, 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:
⟨
a
,
b
,
c
,
d
,
e
,
p
,
q
,
r
,
t
,
k
|
p
10
a
=
a
p
,
p
a
c
q
r
=
r
p
c
a
q
,
r
a
=
a
r
,
p
10
b
=
b
p
,
p
2
a
d
q
2
r
=
r
p
2
d
a
q
2
,
r
b
=
b
r
,
p
10
c
=
c
p
,
p
3
b
c
q
3
r
=
r
p
3
c
b
q
3
,
r
c
=
c
r
,
p
10
d
=
d
p
,
p
4
b
d
q
4
r
=
r
p
4
d
b
q
4
,
r
d
=
d
r
,
p
10
e
=
e
p
,
p
5
c
e
q
5
r
=
r
p
5
e
c
a
q
5
,
r
e
=
e
r
,
a
q
10
=
q
a
,
p
6
d
e
q
6
r
=
r
p
6
e
d
b
q
6
,
p
t
=
t
p
,
b
q
10
=
q
b
,
p
7
c
d
c
q
7
r
=
r
p
7
c
d
c
e
q
7
,
q
t
=
t
q
,
c
q
10
=
q
c
,
p
8
c
a
3
q
8
r
=
r
p
8
a
3
q
8
,
d
q
10
=
q
d
,
p
9
d
a
3
q
9
r
=
r
p
9
a
3
q
9
,
e
q
10
=
q
e
,
a
−
3
t
a
3
k
=
k
a
−
3
t
a
3
⟩
{\displaystyle {\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^{2}adq^{2}r=rp^{2}daq^{2},&rb=br,&\\&p^{10}c=cp,&p^{3}bcq^{3}r=rp^{3}cbq^{3},&rc=cr,&\\&p^{10}d=dp,&p^{4}bdq^{4}r=rp^{4}dbq^{4},&rd=dr,&\\&p^{10}e=ep,&p^{5}ceq^{5}r=rp^{5}ecaq^{5},&re=er,&\\&aq^{10}=qa,&p^{6}deq^{6}r=rp^{6}edbq^{6},&pt=tp,&\\&bq^{10}=qb,&p^{7}cdcq^{7}r=rp^{7}cdceq^{7},&qt=tq,&\\&cq^{10}=qc,&p^{8}ca^{3}q^{8}r=rp^{8}a^{3}q^{8},&&\\&dq^{10}=qd,&p^{9}da^{3}q^{9}r=rp^{9}a^{3}q^{9},&&\\&eq^{10}=qe,&a^{-3}ta^{3}k=ka^{-3}ta^{3}&&\rangle \end{array}}}
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:
S
=
{
⟨
u
,
v
⟩
:
u
dan
v
adalah kata-kata
X
dan
u
=
v
pada
G
}
{\displaystyle S=\{\langle u,v\rangle :u{\text{ dan }}v{\text{ adalah kata-kata }}X{\text{ dan }}u=v{\text{ pada }}G\ \}}
lalu ada fungsi rekursif parsial fP yaitu:
f
P
(
⟨
u
,
v
⟩
)
=
{
0
jika
⟨
u
,
v
⟩
∈
S
tidak terdefinisi/tidak berhenti
if
⟨
u
,
v
⟩
∉
S
{\displaystyle 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}}}
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:
g
(
⟨
u
,
v
⟩
)
=
{
0
jika
⟨
u
,
v
⟩
∉
S
tidak terdefinisi/tidak berhenti
jika
⟨
u
,
v
⟩
∈
S
{\displaystyle 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}}}
Namun u = v di G jika dan hanya jika uv−1=1 di G . Oleh karena itu, untuk menyelesaikan masalah kata untuk P cukup dengan membangun fungsi rekursif h sehingga:
h
(
x
)
=
{
0
jika
x
≠
1
pada
G
tidak terdefinisi/tidak berhenti
jika
x
=
1
pada
G
{\displaystyle 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}}}
= 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 w ≠ 1 dalam G jika dan hanya beberapa pemetaan X menjadi S menyebabkan homomorfisme sedemikian rupa sehingga w ≠ 1 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:
h
(
x
)
=
{
0
jika
x
≠
1
pada
G
tidak terdefinisi/tidak berhenti
jika
x
=
1
pada
G
{\displaystyle 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}}}
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:
S
w
=
⟨
X
|
R
∪
{
w
}
⟩
.
{\displaystyle S_{w}=\langle X|R\cup \{w\}\rangle .}
Ada fungsi rekursif
f
⟨
X
|
R
∪
{
w
}
⟩
{\displaystyle f_{\langle X|R\cup \{w\}\rangle }}
yaitu:
f
⟨
X
|
R
∪
{
w
}
⟩
(
x
)
=
{
0
jika
x
=
1
pada
S
w
tidak terdefinisi/tidak berhenti
jika
x
≠
1
pada
S
w
.
{\displaystyle 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}}}
Menulis:
g
(
w
,
x
)
=
f
⟨
X
|
R
∪
{
w
}
⟩
(
x
)
.
{\displaystyle g(w,x)=f_{\langle X|R\cup \{w\}\rangle }(x).}
Kemudian karena konstruksi f seragam, ini adalah fungsi rekursif dari dua variabel.
Maka dari itu:
h
(
w
)
=
g
(
w
,
a
)
{\displaystyle h(w)=g(w,a)}
bersifat rekursif. Dengan konstruksi:
h
(
w
)
=
{
0
jika
a
=
1
pada
S
w
tidak terdefinisi/tidak berhenti
jika
a
≠
1
pada
S
w
.
{\displaystyle 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}}}
Karena S adalah grup sederhana, satu-satunya grup hasil bagi adalah dirinya sendiri dan grup trivial. Karena itu:
h
(
w
)
=
{
0
jika
w
≠
1
pada
S
tidak terdefinisi/tidak berhenti
jika
w
=
1
pada
S
.
{\displaystyle h(w)={\begin{cases}0&{\text{jika}}\ w\neq 1\ {\text{pada}}\ S\\{\text{tidak terdefinisi/tidak berhenti}}\ &{\text{jika}}\ w=1\ {\text{pada}}\ S.\end{cases}}}
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
Word problem, PlanetMath.org.
W. W. Boone, F. B. Cannonito, and R. C. Lyndon. Word Problems: Decision Problem in Group Theory. Netherlands: North-Holland. 1973.
Boone, W. W.; Higman, G. (1974). "An algebraic characterization of the solvability of the word problem". J. Austral. Math. Soc. 18: 41–53. doi:10.1017/s1446788700019108 .
Boone, W. W.; Rogers Jr, H. (1966). "On a problem of J. H. C. Whitehead and a problem of Alonzo Church". Math. Scand. 19: 185–192. doi:10.7146/math.scand.a-10808 .
Borisov, V. V. (1969), "Simple examples of groups with unsolvable word problem", Akademiya Nauk SSSR. Matematicheskie Zametki, 6: 521–532, ISSN 0025-567X, MR 0260851
Collins, Donald J. (1969), "Word and conjugacy problems in groups with only a few defining relations", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 15 (20–22): 305–324, doi:10.1002/malq.19690152001, MR 0263903
Collins, Donald J. (1972), "On a group embedding theorem of V. V. Borisov", Bulletin of the London Mathematical Society, 4 (2): 145–147, doi:10.1112/blms/4.2.145, ISSN 0024-6093, MR 0314998
Collins, Donald J. (1986), "A simple presentation of a group with unsolvable word problem", Illinois Journal of Mathematics, 30 (2): 230–234, doi:10.1215/ijm/1256044631 , ISSN 0019-2082, MR 0840121
Collins, Donald J.; Zieschang, H. (1990), Combinatorial group theory and fundamental groups, Berlin, New York: Springer-Verlag, hlm. 166, MR 1099152
Dehn, Max (1911), "Über unendliche diskontinuierliche Gruppen", Mathematische Annalen, 71 (1): 116–144, doi:10.1007/BF01456932, ISSN 0025-5831, MR 1511645, diarsipkan dari versi asli tanggal 2016-03-05, diakses tanggal 2020-12-11
Dehn, Max (1912), "Transformation der Kurven auf zweiseitigen Flächen", Mathematische Annalen, 72 (3): 413–421, doi:10.1007/BF01456725, ISSN 0025-5831, MR 1511705, diarsipkan dari versi asli tanggal 2016-03-05, diakses tanggal 2020-12-11
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.
Rotman, Joseph (1994), An introduction to the theory of groups, Berlin, New York: Springer-Verlag, ISBN 978-0-387-94285-8
Stillwell, J. (1982). "The word problem and the isomorphism problem for groups". Bulletin of the AMS. 6: 33–56. doi:10.1090/s0273-0979-1982-14963-1 .
Kata Kunci Pencarian:
- Masalah kata untuk grup
- Dewa 19
- Komando Pasukan Khusus
- Noah (grup musik)
- Daftar topik teori grup
- Linkin Park
- Baskara Putra
- Ahmad Dhani
- Daftar kata serapan dari bahasa Inggris dalam bahasa Indonesia
- Project Pop
- 2017 Liga 2 (Indonesia)
