בעיית ההתאמה של פוסט

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

תיאור הבעיה

הבעיה עוסקת במחרוזות - רצפי אותיות מעל אלפבית כלשהו. נתונה קבוצה סופית של זוגות של מחרוזות (בלי מגבלה על האורכים האפשריים שלהן), מהצורה $(a_{1},b_{1}),(a_{2},b_{2}),\dots (a_{n},b_{n})$. השאלה היא האם ניתן לבחור חלק מהזוגות (אולי יותר מפעם אחת) ולשרשר את כל ה-$\ a_{i}$ בזוגות שנבחרו ואת ה-$\ b_{i}$ בזוגות שנבחרו (כלומר, לכתוב אותם בזה אחר זה) כך ששני השרשורים יתנו את אותה המחרוזת.

בכתיבה פורמלית, השאלה היא האם קיימת סדרת אינדקסים, $\ i_{1},i_{2},\dots i_{k}$, כולם בתחום $\ 1,\dots ,n$ כך ש-$\ a_{i_{1}}a_{i_{2}}\dots a_{i_{k}}=b_{i_{1}}b_{i_{2}}\dots b_{i_{k}}$.

דוגמה

$a_{1}$ $a_{2}$ $a_{3}$ $a_{4}$ ב ל יי קה

,

$b_{1}$ $b_{2}$ $b_{3}$ $b_{4}$ בלל י ק ה

בדוגמה זו ניתן ליצור את המילה "בללייקה" סימולטנית באמצעות סדרת האינדקסים 1,2,2,3,4: החזרה על אינדקס ה-2 מכפילה את הל' בסדרת ה-$\ a_{i}$, ואת ה-י' בסדרת ה-$\ b_{i}$.

אם יוסר זוג מספר 2, לא ניתן יהיה למצוא התאמה. זאת מכיוון שאם סדרת ההתאמות מכילה את זוג מספר 1, אז $\ b_{1}$ יוסף את האות ל' למילה הנבנית, וזו לא ניתנת ליצירה מה-$\ a_{i}$ (לאחר שהורדנו את זוג מספר 2), אם היא מכילה את 3 אז $\ a_{3}$ יוסיף את האות י' למילה הנבנית, וזו לא קיימת עבור ה-$\ b_{i}$; מכאן עולה שהיא חייבת להיות מורכבת מ-4 בלבד, אבל אורך $\ a_{4}$ שונה מאורך $\ b_{4}$ ולכן שתי המילים שהם בונים בו זמנית יהיו בעלות אורך שונה, ובפרט לא אותה מילה.

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

הוכחת אי כריעות

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

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

שלב א' - מעבר לבעיית התאמה עם מחרוזת ראשונה נתונה

הוריאנט על בעיית פוסט שבו משתמשים בהוכחת אי הכריעות הוא כדלהלן: נתון אוסף של זוגות של מחרוזות, $(a_{1},b_{1}),(a_{2},b_{2}),\dots (a_{n},b_{n})$, ובנוסף נתון עוד זוג אחד מיוחד, $\ (x,y)$. השאלה היא האם קיימת סדרת אינדקסים $\ i_{1},i_{2},\dots i_{k}$, כולם בתחום $\ 1,\dots ,n$ כך ש-$\ xa_{i_{1}}a_{i_{2}}\dots a_{i_{k}}=yb_{i_{1}}b_{i_{2}}\dots b_{i_{k}}$.

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

אם כן, נניח כי נתון אוסף זוגות $(a_{1},b_{1}),(a_{2},b_{2}),\dots (a_{n},b_{n})$ וכמו כן נתון הזוג המיוחד $\ (x,y)$. הרעיון הבסיסי בהמרת בעיה זו לבעיית פוסט המקורית היא לקחת סימן שאינו באלפבית הנוכחי של המחרוזות (למשל, $\ *$) ו"להשתיל" אותו בתוך כל הזוגות $\ (a_{i},b_{i})$ באופן כזה שבאיבר הימני של כל זוג הכוכביות מופיעות לפני כל אות, ואילו באיבר השמאלי הכוכביות מופיעות אחרי כל אות. מכאן שלא ניתן להתחיל את בניית המילה המשותפת עם אף אחד מהזוגות $\ (a_{i},b_{i})$ ש"טופלו" באופן שכזה, כי האיבר הימני בזוג מתחיל בכוכבית, ואילו השמאלי לא. כדי שעדיין יהיה ניתן ליצור מילה משותפת, יש לתקן את הזוג $\ (x,y)$ בהתאם, וכמו כן להוסיף זוג אחד נוסף, ש"יסיים" את בניית המחרוזת וישווה את מספר הכוכביות שבכל אחד מהעותקים.

כדי לתאר בצורה פורמלית את הבנייה נוח להגדיר שתי פונקציות על מילים, $\ L(w),R(w)$, שעבור המילה $\ w=w_{1}w_{2}\dots w_{m}$ "משתילות" כוכביות באופן הבא:

$\ L(w)=*w_{1}*w_{2}*\dots *w_{m}$

$\ R(w)=w_{1}*w_{2}*\dots *w_{m}*$

כעת, אם $\ P=\left\{(x,y),(a_{i},b_{i})\right\}$ הוא אוסף הכללים של הבעיה שאותה מתרגמים, אז אוסף הכללים החדש יהיה $\ P^{\prime }=\left\{(R(a_{i}),L(b_{i}))|1\leq i\leq n\right\}\cup \left\{(L(x)*,L(y)),(\$,*\$)\right\}$

כאשר גם $\ \$$ הוא סימן שאינו שייך לאלפבית של הבעיה המקורית.

שלב ב' - סימולציה של מכונת טיורינג באמצעות בעיית ההתאמה

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

$\ 01001q_{3}010\$$

מייצגת את הקונפיגורציה שבה החלק המשומש של הסרט מכיל את המחרוזת "01001010", המכונה נמצאת במצב הפנימי מס' 3, והראש הקורא מצביע על ה-"0" הלפני אחרון.

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

$\ q_{0}00\$*1q_{1}0\$*11q_{2}\$*11q_{3}0\$*1q_{0}10\$$

מחרוזת זו מייצגת את הריצה שבה המכונה התחילה במצב 0 ועם שני אפסים כתובים על הסרט, שינתה את הראשון מביניהם ל-1 עברה למצב 1 ונעה עם הראש הקורא ימינה, שינתה את השני ל-1, עברה למצב 2 ונעה שוב ימינה, כתבה 0 על הסרט, עברה למצב הפנימי 3 ונשארה באותו מקום על הסרט, ולבסוף נעה צעד אחד שמאלה ועברה למצב הפנימי 0.

הסימולציה של מכונת הטיורינג מתבצעת כך: ראשית, הזוג ההתחלתי של מילים בבעיית ההתאמה יהיה הזוג $\ (*q_{0}w\$*,*)$, כאשר $\ w$ היא המילה שעבורה נבדקת עצירת המכונה. כלומר - האיבר השמאלי בזוג מתאר את הקונפיגורציה ההתחלתית של המכונה, ואילו האיבר הימני הוא "ריק". מכאן שכדי שהזוגות ירכיבו את אותה המילה, בחירת האיברים הבאים צריכה להיות כזו ש"תעתיק" את הקונפיגורציה שקיימת באגף שמאל לאגף ימין. הרעיון הוא שתוך כדי ביצוע ההעתקה הזו לאגף ימין, תיווצר (על ידי האיברים השמאליים בזוגות שיתווספו) קונפיגורציה חדשה באגף שמאל - כזו שנובעת מיידית מהקונפיגורציה הקודמת. כך למשל לכל תו $\ \sigma$, הזוג $\ (\sigma ,\sigma )$ מבטיח העתקה של תוכן הסרט מהקונפיגורציה הקודמת לנוכחית, וזוגות כמו $\ (\tau p,q\sigma )$ (שמתאים למעבר $\ (p,\tau ,R)\in \delta (q,\sigma )$) מבטיחים את שינוי הקונפיגורציה החדשה על פי פעולה אפשרית עבור מכונת הטיורינג המסמלצת.

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