משתמש:שמוס או וונג/בעיית המילה
במתמטיקה ובמדעי המחשב בעיית המילה היא בעיית הכרעה שדנה באפשרות להכריע האם שני עצמים מאותה קבוצה נתונה הם שקולים או לא (פירוט בהמשך). בעיית המילה היא דוגמה לבעייה לא כריעה. למעשה, ניתן להציג בעיות לא כריעות רבות במתמטיקה כבעיית מילה.
תיאור הבעיה
[עריכת קוד מקור | עריכה]בתיאור הבעיה ייעשה שימוש במונחים הבאים -
- א"ב: קבוצה סופית של סימנים ( או "אותיות").
- מילה: קבוצה סופית וסדורה של אותיות השייכות לא"ב נתון.
