בעיית המילה

בעיית המילה היא אחת מבעיות ההכרעה העיקריות באלגברה קומבינטורית, הראשונה משלוש בעיות דן. הבעיה היא לקבוע, באובייקט אלגברי (חבורה, חבורה למחצה, חוג וכדומה) הנתון על ידי ייצוג סופי, האם מילה נתונה שווה לאיבר היחידה. בעיית המילה אינה פתירה בחבורה כללית, ואפילו לא בחבורה פתירה כללית (Kharlampovich 1981).

הפתירות של בעיית המילה בחבורה הנתונה על ידי יוצרים ויחסים אינה תלויה בייצוג. הבעיה פתירה בחבורה אם ורק אם פונקציית דן של החבורה היא רקורסיבית.

בעיית המילה פתירה בחבורות עם יחס יחיד (Magnus, 1932). לא ידוע האם בעיית המילה פתירה בכל חבורה עם שני יחסים. את הדוגמה הראשונה לחבורה מוצגת סופית עם בעיית מילה לא פתירה נתנו Novikov (ב-1955) ו-Boone (ב-1959), משני צידי מסך הברזל, ובאופן בלתי תלוי. לחבורה נוצרת סופית יש בעיית מילה פתירה אם ורק אם היא מוכלת בחבורה פשוטה המוכלת בחבורה מוצגת סופית (זהו משפט Boone-Higman, 1973).

בעיית המילה אינה פתירה במונויד $\ <a,b,s,t,z|as=sa,at=ta,bs=sb,bt=tb,zta=tz,zsb=sz,tta=ttaz>$ (Tsejtin, 1958).

ראו גם

• בעיית הצמידות