In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a finitely generated group G is the algorithmic problem of deciding whether two words in the generators represent the same element of G .
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.
The related but different uniform word problem for a class K of recursively presented groups is the algorithmic problem of deciding, given as input a presentation P for a group G in the class K and two words in the generators of G , whether the words represent the same element of G .
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 .
Some authors require the class K to be definable by a recursively enumerable set of presentations.
Beberapa penulis mensyaratkan kelas K untuk didefinisikan oleh sekumpulan presentasi secara rekursif dapat dihitung.
Throughout the history of the subject, computations in groups have been carried out using various normal forms.
Sepanjang sejarah subjek, komputasi dalam kelompok telah dilakukan menggunakan berbagai bentuk normal.
These usually implicitly solve the word problem for the groups in question.
Ini biasanya secara implisit memecahkan masalah kata untuk kelompok yang bersangkutan.
In 1911 Max Dehn proposed that the word problem was an important area of study in its own right, together with the conjugacy problem and the group isomorphism problem.
Pada tahun 1911 Max Dehn mengusulkan bahwa masalah kata adalah bidang studi penting dalam dirinya sendiri, bersama dengan masalah konjugasi dan masalah isomorfisme grup.
In 1912 he gave an algorithm that solves both the word and conjugacy problem for the fundamental groups of closed orientable two-dimensional manifolds of genus greater than or equal to 2.
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.
Subsequent authors have greatly extended Dehn's algorithm and applied it to a wide range of group theoretic decision problems.
Penulis selanjutnya telah memperluas Algoritma Dehn dan menerapkannya ke berbagai teori grup masalah keputusan.
It was shown by Pyotr Novikov in 1955 that there exists a finitely presented group G such that the word problem for G is undecidable.
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.
A different proof was obtained by William Boone in 1958.
Bukti berbeda diperoleh oleh William Boone pada tahun 1958.
The word problem was one of the first examples of an unsolvable problem to be found not in mathematical logic or the theory of algorithms, but in one of the central branches of classical mathematics, algebra.
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.
For example, polycyclic groups have solvable word problems since the normal form of an arbitrary word in a polycyclic presentation is readily computable; other algorithms for groups may, in suitable circumstances, also solve the word problem, see the Todd–Coxeter algorithm and the Knuth–Bendix completion algorithm.
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.
On the other hand, the fact that a particular algorithm does not solve the word problem for a particular group does not show that the group has an unsolvable word problem.
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.
For instance Dehn's algorithm does not solve the word problem for the fundamental group of the torus.
Misalnya algoritma Dehn tidak memecahkan masalah kata untuk grup fundamental dari torus.
In more concrete terms, the uniform word problem can be expressed as a rewriting question, for literal strings.
Dalam istilah yang lebih konkret, soal kata seragam dapat diekspresikan sebagai pertanyaan menulis ulang, untuk pita literal.
For a presentation P of a group G , P will specify a certain number of generators x , y , z , … for G .
Untuk presentasi P dari grup G , P akan menentukan sejumlah generator x, y, z, ... untuk G .
We need to introduce one letter for x and another (for convenience) for the group element represented by x − 1 } .
Kita perlu memperkenalkan satu huruf untuk x dan huruf lainnya (untuk kenyamanan) untuk elemen grup yang diwakili oleh x−1.
Call these letters (twice as many as the generators) the alphabet Σ for our problem.
Sebut huruf-huruf ini (dua kali lebih banyak dari generator) alfabet Σ untuk masalah kita.
p q r of symbols from Σ , of some length, multiplied in G .
pqr simbol dari Σ , dari beberapa panjang, dikalikan dengan G .
The string of length 0 (null string) stands for the identity element e of G .
( string null) adalah singkatan dari elemen identitas e dari G .
The crux of the whole problem is to be able to recognise all the ways e can be represented, given some relations.
Inti dari keseluruhan masalah adalah untuk dapat mengenali semua cara e dapat direpresentasikan, dengan beberapa hubungan.
The effect of the relations in G is to make various such strings represent the same element of G .
Efek dari relasi dalam G adalah membuat berbagai string tersebut mewakili elemen yang sama dari G .
In fact the relations provide a list of strings that can be either introduced where we want, or cancelled out whenever we see them, without changing the 'value', i.e. the group element that is the result of the multiplication.
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.
Writing A for the inverse of a , we have possible strings combining any number of the symbols a and A .
Menulis A untuk kebalikan dari a , kami memiliki kemungkinan string yang menggabungkan sejumlah simbol a dan A .
First reduce strings to the empty string, a , a a , A or A A .
Pertama kurangi string menjadi string kosong, a , aa , A atau AA .
This is not, however, the typical case.
Namun, ini bukan kasus yang khas.
For the example, we have a canonical form available that reduces any string to one of length at most three, by decreasing the length monotonically.
Sebagai contoh, kami memiliki bentuk kanonik tersedia yang mengurangi string apa pun menjadi satu string maksimal tiga, dengan mengurangi panjangnya secara monoton.
The upshot is, in the worst case, that the relation between strings that says they are equal in G is an Undecidable problem.
Hasilnya adalah, dalam kasus terburuk, bahwa hubungan antara string yang mengatakan mereka sama di G adalah Masalah yang tidak dapat diputuskan .
An explicit example of a reasonable short presentation with insoluble word problem is given in Collins 1986: ⟨ a , b , c ,
Contoh eksplisit dari presentasi singkat yang masuk akal dengan masalah kata yang tidak terpecahkan diberikan dalam Collins 1986: ⟨ a , b , c ,
d q 10q d , p 9 d a 3 q 9 rr p 9 a 3 q 9 , e q 10q e , a − 3 t a 3 kk a − 3 t a 3 ⟩ {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}}} The word problem for a recursively presented group can be partially solved in the following sense: Given a recursive presentation P⟨ X | R ⟩ for a group G , define: S{ ⟨ u , v ⟩ : u and v are words in X and uv in G } }v{\text{ are words in }}X{\text{ and }}u=v{\text{ in }}G\ \}} then there is a partial recursive function f P } such that: f P ( ⟨ u , v ⟩ )
d q 10q d , p 9 d a 3 q 9 rr p 9 a 3 q 9 , e q 10q e , a − 3 t a 3 kk a − 3 t a 3 ⟩ {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}}} 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 uv pada G } }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 if ⟨ u , v ⟩ ∈ S undefined/does not halt if ⟨ u , v ⟩ ∉ S (\langle u,v\rangle )={\begin{cases}0&{\text{if}}\ \langle u,v\rangle \in S\\{\text{undefined/does not halt}}\ &{\text{if}}\ \langle u,v\rangle \notin S\end{cases}}} More informally, there exists an algorithm that halts if uv , but does not do so otherwise.
{ 0 jika ⟨ u , v ⟩ ∈ S tidak terdefinisi/tidak berhenti if ⟨ u , v ⟩ ∉ S (\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 uv , tapi tidak melakukannya sebaliknya.
It follows that to solve the word problem for P it is sufficient to construct a recursive function g such that: g ( ⟨ u , v ⟩ )
Oleh karena itu, untuk menyelesaikan masalah kata untuk P cukup dengan membangun fungsi rekursif g sedemikian rupa sehingga:
{ 0 if ⟨ u , v ⟩ ∉ S undefined/does not halt if ⟨ u , v ⟩ ∈ S 0&{\text{if}}\ \langle u,v\rangle \notin S\\{\text{undefined/does not halt}}\ &{\text{if}}\ \langle u,v\rangle \in S\end{cases}}} However uv in G if and only if u v − 111} in G .
{ 0 jika ⟨ u , v ⟩ ∉ S tidak terdefinisi/tidak berhenti jika ⟨ u , v ⟩ ∈ S 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 uv di G jika dan hanya jika uv−1=1 di G .
{ 0 if w ≠ 1 in G undefined/does not halt if w1 in G 0&{\text{if}}\ w\neq 1\ {\text{in}}\ G\\{\text{undefined/does not halt}}\ &{\text{if}}\ w=1\ {\text{in}}\ G\end{cases}}} Boone–Rogers Theorem: There is no uniform partial algorithm that solves the word problem in all finitely presented groups with solvable word problem.
{ 0 jika x ≠ 1 pada G tidak terdefinisi/tidak berhenti jika x1 pada G 0&{\text{jika}}\ x\neq 1\ {\text{pada}}\ G\\{\text{tidak terdefinisi/tidak berhenti}}\ &{\text{jika}}\ x=1\ {\text{pada}}\ G\end{cases}}} Berikut ini akan dibuktikan sebagai contoh penggunaan teknik ini: Teorema: Grup residual finit yang disajikan secara terbatas memiliki masalah kata yang dapat dipecahkan.
0&{\text{if}}\ w\neq 1\ {\text{in}}\ H\\{\text{undefined/does not halt}}\ &{\text{if}}\ w=1\ {\text{in}}\ H.\end{cases}}} The function f clearly depends on the presentation P .
\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 )
0&{\text{if}}\ w\neq 1\ {\text{in}}\ H\\{\text{undefined/does not halt}}\ &{\text{if}}\ w=1\ {\text{in}}\ H.\end{cases}}} But this uniformly solves the word problem for the class of all finitely presented groups with solvable word problem, contradicting Boone–Rogers.
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 .
The most significant of these is the Boone–Higman theorem: A finitely presented group has solvable word problem if and only if it can be embedded in a simple group that can be embedded in a finitely presented group.
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.
It is widely believed that it should be possible to do the construction so that the simple group itself is finitely presented.
Dipercaya secara luas bahwa konstruksi harus mungkin dilakukan sehingga kelompok sederhana itu sendiri disajikan dengan baik.
If so one would expect it to be difficult to prove as the mapping from presentations to simple groups would have to be non-recursive.
Jika demikian, orang akan sulit untuk membuktikannya karena pemetaan dari presentasi ke grup sederhana harus non-rekursif.
The oldest result relating algebraic structure to solvability of the word problem is Kuznetsov's theorem:
Hasil tertua yang menghubungkan struktur aljabar dengan solvabilitas masalah kata adalah teorema Kuznetsov:
A recursively presented simple group S has solvable word problem.
Grup sederhana yang disajikan secara rekursif S memiliki masalah kata yang dapat dipecahkan.
To prove this let ⟨ X | R ⟩ be a recursive presentation for S .
Untuk membuktikan ini mari ⟨X|R⟩ menjadi presentasi rekursif untuk S .
If w is a word on the generators X of S , then let: S w⟨ X | R ∪ { w } ⟩ .
Jika w adalah kata pada generator X dari S , maka biarkan: S w⟨ X | R ∪ { w } ⟩ .
=\langle X|R\cup \{w\}\rangle .} There is a recursive function f ⟨ X | R ∪ { w } ⟩ \rangle }} such that: f ⟨ X | R ∪ { w } ⟩ ( x )
Ada fungsi rekursif f ⟨ X | R ∪ { w } ⟩ \rangle }} yaitu: f ⟨ X | R ∪ { w } ⟩ ( x )
{ 0 if x1 in S w undefined/does not halt if x ≠ 1 in S w .
{ 0 jika x1 pada S w tidak terdefinisi/tidak berhenti jika x ≠ 1 pada S w .
\rangle }(x)={\begin{cases}0&{\text{if}}\ x=1\ {\text{in}}\ S_{w}\\{\text{undefined/does not halt}}\ &{\text{if}}\ x\neq 1\ {\text{in}}\ S_{w}.\end{cases}}} Write: g ( w , x )f ⟨ X | R ∪ { w } ⟩ ( x ) .
\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 )
Then because the construction of f was uniform, this is a recursive function of two variables.
Kemudian karena konstruksi f seragam, ini adalah fungsi rekursif dari dua variabel.
It follows that: ⁠ h ( w )
Maka dari itu: ⁠ h ( w )
g ( w , a ) ⁠ is recursive.
g ( w , a ) ⁠ bersifat rekursif.
By construction: h ( w ){ 0 if a1 in S w undefined/does not halt if a ≠ 1 in S w .
{ 0 jika w ≠ 1 pada S tidak terdefinisi/tidak berhenti jika w1 pada S .
0&{\text{if}}\ a=1\ {\text{in}}\ S_{w}\\{\text{undefined/does not halt}}\ &{\text{if}}\ a\neq 1\ {\text{in}}\ S_{w}.\end{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 .
Therefore: h ( w )
Karena itu: h ( w )
{ 0 if w ≠ 1 in S undefined/does not halt if w1 in S .
{ 0 jika w ≠ 1 pada S tidak terdefinisi/tidak berhenti jika w1 pada S .
0&{\text{if}}\ w\neq 1\ {\text{in}}\ S\\{\text{undefined/does not halt}}\ &{\text{if}}\ w=1\ {\text{in}}\ S.\end{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 .
This proof does not prove the existence of a uniform algorithm for solving the word problem for this class of groups.
Bukti ini tidak membuktikan adanya algoritma yang seragam untuk menyelesaikan masalah kata untuk kelas kelompok ini.
The non-uniformity resides in choosing a non-trivial element of the simple group.
Ketidakseragaman terletak pada pemilihan elemen non-sepele dari kelompok sederhana.
There is no reason to suppose that there is a recursive function that maps a presentation of a simple groups to a non-trivial element of the group.
Tidak ada alasan untuk menganggap bahwa ada fungsi rekursif yang memetakan presentasi dari grup sederhana ke elemen non-trivial grup.
However, in the case of a finitely presented group we know that not all the generators can be trivial (Any individual generator could be, of course).
Namun, dalam kasus grup yang disajikan secara terbatas, kami tahu bahwa tidak semua generator bisa sepele (Generator individual apa pun, tentu saja).
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.
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, D. J.; Zieschang, H. (1993), "Combinatorial group theory and fundamental groups", Algebra VIII: Combinatorial Group Theory, Applications to Geometry, Encyclopaedia of Mathematical Sciences, vol. 58, Berlin: Springer, pp.
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 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 asli tanggal 2016-03-05, diakses tanggal 2020-12-11 A. V. Kuznetsov, "Algorithms as operations in algebraic systems", Izvestia Akad.