בעיית המילה

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

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

בעיית המילה פתירה בחבורות עם יחס יחיד (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).

ראו גם

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

31596641בעיית המילה