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

“בעיית ההתאמה של פוסט” - Post Correspondence Problem, ובקיצור PCP - היא בעיה נחמדה במדעי המחשב שנקראת על שם אמיל פוסט, אחד מחלוצי מדעי המחשב (ואינה קשורה לדואר, כמו שחשבתי הרבה זמן) שתיאר אותה ב-1946. מה שנחמד בבעיה הזו הוא שהיא בלתי פתירה, דהיינו לא קיים אלגוריתם שיודע לפתור אותה; זה נשמע כמו חסרון, אבל למי שמעוניינים להוכיח שעוד בעיות במדעי המחשב הן לא פתירות זה דווקא יתרון: כדי להראות שבעיה במדעי המחשב אינה פתירה, מספיק להראות טיעון מהצורה “אם הבעיה שלי הייתה פתירה, אז היינו יכולים לפתור בעזרתה את בעיית ההתאמה של פוסט”. מה שטוב בבעיית ההתאמה של פוסט הוא שמצד אחד היא לא פתירה, אבל מצד שני היא מאוד פשוטה לניסוח, ולכן הוכחות של “כך אני פותר את פוסט, בהינתן פתרון לבעיה המוזרה שלי” הן קלות יחסית.

איך מוגדרת הבעיה? ההגדרה קצת מוזרה, אז נתחיל עם דוגמה. בואו נסתכל על שלושה זוגות של מילים מעל \( \left\{ 0,1\right\} \) (כלומר, סדרות של 0 ו-1):

\( \left(00,0\right),\left(1,00\right),\left(0,10\right) \)

שתי מילים אפשר לשרשר - לכתוב אותן אחת אחרי השניה. השרשור של 00 עם 01 הוא המילה 0001. אז גם זוגות נשרשר “רכיב רכיב”, כלומר \( \left(00,0\right)\cdot\left(1,00\right)=\left(001,000\right) \). עכשיו, הבה ונסתכל על סדרת השרשורים הבאים:

\( \left(00,0\right)\cdot\left(00,0\right)\cdot\left(1,00\right)\cdot\left(0,10\right)=\left(000010,000010\right) \)

שימו לב מה קיבלתי - זוג שבו המילה בצד ימין והמילה בצד שמאל הן זהות, למרות שבכל הזוגות שמהם בניתי אותו המילים הללו תמיד שונות.

בואו נתאר את זה בצורה טיפה יותר פורמלית. נסמן את הזוגות בתור \( \left(a_{1},b_{1}\right),\left(a_{2},b_{2}\right),\left(a_{3},b_{3}\right) \). למשל, \( b_{3}=10 \) ו-\( a_{2}=1 \). אז האבחנה שלעיל היא בעצם האבחנה ש-\( a_{1}a_{1}a_{2}a_{3}=b_{1}b_{1}b_{2}b_{3} \). עוד יותר פורמלית: מצאנו סדרת אינדקסים \( j_{1},j_{2},\dots,j_{k} \) כך ש-\( a_{j_{1}}a_{j_{2}}\cdots a_{j_{k}}=b_{j_{1}}b_{j_{2}}\cdots b_{j_{k}} \).

אצלנו \( n=4 \) ו-\( j_{1}=j_{2}=1 \), \( j_{3}=2 \) ו-\( j_{4}=3 \).

הדוגמה הזו בעצם מתארת כמעט לגמרי מה קורה באופן כללי: הקלט לבעיה הוא סדרה סופית של זוגות, \( \left(a_{1},b_{1}\right),\dots,\left(a_{n},b_{n}\right) \), שכולן מעל אותו א”ב (הוא יכול להיות שונה מ-\( \left\{ 0,1\right\} \) ובהמשך אשתמש בזה, אבל זה לצורך נוחות בלבד; אפשר היה בתיאוריה לעשות את הכל גם עם 0,1). השאלה היא האם קיימת סדרת אינדקסים סופית \( j_{1},\dots,j_{k} \) כך ש-\( a_{j_{1}}a_{j_{2}}\cdots a_{j_{k}}=b_{j_{1}}b_{j_{2}}\cdots b_{j_{k}} \). כן או לא. זה הכל. והבעיה האלגוריתמית הזו - אינה כריעה.

המטרה העיקרית שלי בפוסט היא להציג את הוכחת אי הכריעות של הבעיה, שהיא נפלאה לטעמי, אבל לפני כן אני רוצה להראות את היישום הסטנדרטי של הבעיה להוכחת אי הכריעות של בעיה אחרת - ובעיה טבעית ומעניינת למדי: בדיקה האם דקדוק חופשי-הקשר הוא דו-משמעי. זה מצריך ממני להציג בזריזות את ההגדרה של דקדוק חופשי-הקשר, שעדיין לא הצגתי בבלוג בכללת אבל אפשר גם לראות אותה בויקיפדיה. אני חושב על דקדוק בתור מעין מכונה ליצירת מילים: מתחילים מאיזה משתנה התחלתי \( S \), ומבצעים סדרה של גזירות, כאשר כל גזירה מחליפה משתנה במילה שיש לנו כרגע בתת-מילה חדשה, שמכילה משתנים חדשים וסימבולים (טרמינלים) שאי אפשר לגזור. דקדוק \( G=\left(V,T,S,P\right) \) כולל קבוצה סופית \( V \) של משתנים, קבוצה סופית \( T \) של טרמינלים, משתנה התחלתי \( S\in V \) וקבוצה סופית \( P \) של כללי גזירה שמסומנים \( A\to\beta \) כאשר \( A \) הוא המשתנה שגוזרים ו-\( \beta \) היא מילה שיכולה לכלול משתנים וטרמינלים.

בואו נסתכל לדוגמה על דקדוק טיפשי לגזירת ביטויים חשבוניים. הטרמינלים שלנו יהיו \( 0,1,2,\dots,9,+,\times \). יהיה לנו רק משתנה אחד: \( S \) עצמו. ויהיו לנו כללי גזירה מהצורה \( S\to0,S\to1,\dots,S\to9 \) וכמו כן את \( S\to S+S \) ואת \( S\to S\times S \). עכשיו בואו ונראה שתי גזירות למילה \( 1+2\times3 \):

\( S\Rightarrow S+S\Rightarrow1+S\Rightarrow1+S\times S\Rightarrow1+2\times S\Rightarrow1+2\times3 \)

\( S\Rightarrow S\times S\Rightarrow S\times3\Rightarrow S+S\times3\Rightarrow S+2\times3\Rightarrow1+2\times3 \)

שתי הגזירות הללו שונות זו מזו באופן מהותי. ההסבר הפורמלי הוא שיש להן עצי גזירה שונים אבל אני לא אגדיר את המושג הזה בפוסט, אז הנה אינטואיציה: בגזירה הראשונה, הצעד הראשון מפרק את הביטוי לשני חלקים - מה שמשמאל לפלוס ומה שלימינו. אם אנחנו מנסים לחשב את ערכו של הביטוי החשבוני, אפשר לחשוב שמעכשיו אנחנו מחשבים כל חלק בנפרד ובסוף נבצע חיבור שלהם. אגף שמאל יהיה שווה 1, ואגף ימין יהיה שווה \( 2\times3=6 \), ולכן הסכום ייתן 7. עד כאן, הגיוני; אבל אם נעשה את זה גם לגזירה השניה נראה שאחרי הצעד הראשון אנחנו מפרקים את הביטוי לאגף שמאל כפול אגף ימין, כאשר אגף ימין שווה ל-3 אבל אגף שמאל שווה ל-\( 1+2=3 \) ולכן המכפלה צריכה לתת… תשע? לא הגיוני, כמובן - לנו זה נראה מובן מאליו שהביטוי שווה 7 כי אנחנו מניחים במובלע סדר קדימויות בין כפל וחיבור, אבל מבחינת הדקדוק זה לא קיים.

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

מה הרעיון? פשוט מאוד: נניח שיש לנו קלט לבעיית PCP, כלומר \( \left(a_{1},b_{1}\right),\dots,\left(a_{n},b_{n}\right) \). אנחנו רוצים לבנות דקדוק שבו יש מילה שניתן לגזור בשתי דרכים שונות אם ורק אם אפשר להרכיב גם מה-\( a \)-ים וגם מה-\( b \)-ים את אותה מילה… די ברור מה צריך לעשות. פשוט נגדיר דקדוק שמשתניו הם \( S,A,B \) עם כללי הגזירה \( S\to A|B \) (הקו המפריד הזה אומר “או” - בעצם אני מתאר כאן שני כללי גזירה בו זמנית) וכמו כן \( A\to a_{i}A|a_{i} \) ו-\( B\to b_{i}B|b_{i} \) לכל \( 1\le i\le n \).

למשל, עבור בעיית ה-PCP שהבאתי כדוגמה בתחילת הפוסט, עם הזוגות \( \left(00,0\right),\left(1,00\right),\left(0,10\right) \), אקבל כללי גזירה כמו \( A\to00A \) ו-\( A\to00 \) ו-\( B\to10 \) וכדומה. והנה שתי גזירות שונות של אותה מילה:

\( S\Rightarrow A\Rightarrow00A\Rightarrow0000A\Rightarrow00001A\Rightarrow000010 \)

\( S\Rightarrow B\Rightarrow0B\Rightarrow00B\Rightarrow0000B\Rightarrow000010 \)

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

\( S\Rightarrow A\Rightarrow00 \)

\( S\Rightarrow B\Rightarrow00 \)

קל לבדוק ולוודא שאלו גזירות חוקיות בדקדוק, אבל 00 היא לא באמת מילה שיכולה להיווצר בבעיית ה-PCP בתור מילה משותפת, שכן היא מצריכה שימוש באינדקסים שונים עבור סדרות ה-\( a \) וה-\( b \) (\( a_{1}=00 \) אבל \( b_{2}=00 \)). לכן הדקדוק שלנו יצטרך בצורה כלשהי גם לציין מה היו האינדקסים שבהם הוא השתמש ביצירת המילה. התעלול הוא לפלוט אותם בסוף המילה. אז הנה מה שנעשה: נוסיף לטרמינלים שלנו סימבולים \( t_{1},\dots,t_{n} \) ואת הסימבול \( \# \) (שהוא מיותר אבל יעשה את מה שאעשה בהמשך טיפה יותר קריא) וכעת נבנה את הדקדוק הבא:

\( S\to A|B \)

\( A\to a_{i}At_{i}|\# \) לכל \( 1\le i\le n \)

\( B\to b_{i}Bt_{i}|\# \)לכל \( 1\le i\le n \)

כעת אדגים שוב את הגזירות שנותנות את אותו הדבר:

\( S\Rightarrow A\Rightarrow00At_{1}\Rightarrow0000At_{1}t_{1}\Rightarrow00001At_{2}t_{1}t_{1}\Rightarrow000010At_{3}t_{2}t_{1}t_{1}\Rightarrow000010\#t_{3}t_{2}t_{1}t_{2} \)

\( S\Rightarrow B\Rightarrow0Bt_{1}\Rightarrow00Bt_{1}t_{1}\Rightarrow0000Bt_{2}t_{1}t_{1}\Rightarrow000010Bt_{3}t_{2}t_{1}t_{1}\Rightarrow000010\#t_{3}t_{2}t_{1}t_{1} \)

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

עכשיו קל לראות שהגזירה השגויה שהצגתי למעלה, של 00, לא תעבוד:

\( S\Rightarrow A\Rightarrow00At_{1}\Rightarrow00\#t_{1} \)

\( S\Rightarrow B\Rightarrow00Bt_{2}\Rightarrow00\#t_{2} \)

כלומר, לא קיבלנו את אותה המילה כי \( t_{1}\ne t_{2} \). צריך עדיין לשבת ולהוכיח פורמלית שהרדוקציה עובדת, אבל היא עובדת. מסקנה: אם היינו יכולים לבדוק שדקדוק הוא רב משמעי, היינו יכולים לפתור את PCP, ולכן לא ניתן לבדוק את זה.

כמעט אותה בניה מראה לנו שעוד בעיה נפוצה עבור דקדוקים היא לא פתירה - נניח שיש לנו שני דקדוקים \( G_{1},G_{2} \), ואנחנו רוצים לבדוק שיש מילה ששניהם יודעים לייצר - כלומר, שהחיתוך של השפות שהם מייצרים הוא לא ריק. איך הבעיה הזו פותרת לנו את PCP? פשוט מאוד. במקום כללי הגזירה \( S\to A,S\to B \) בדקדוק הקודם, פשוט נייצג שני דקדוקים ש-\( A \) הוא המשתנה ההתחלתי של אחד מהם, ו-\( B \) הוא המשתנה ההתחלתי של השני. באנג! עוד בעיה לא כריעה.

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

התשובה היא שנעשה תעלול טכני. מתוך הקלט \( \left(x,y\right),\left(a_{1},b_{1}\right),\dots,\left(a_{n},b_{n}\right) \) אני הולך ליצור סדרה חדשה של זוגות, שמהונדסים בצורה ש”תכריח” את הזוג שמתאים ל-\( \left(x,y\right) \) להיות ראשון, למרות שחוקי המשחק לא מאפשרים לי להגדיר במפורש שאיבר כלשהו יהיה ראשון.

כרגיל, יהיה הכי נוח להסביר עם דוגמה, אז הנה קלט לדוגמה - וקלט ממש טיפשי, רק כדי שהמניפולציות שאעשה בהמשך יהיו ברורות. \( \left(x,y\right)=\left(11,1\right) \) ו-\( \left(a_{1},b_{1}\right)=\left(11,11\right) \). ברור שאין מילה משותפת, כי האורך של מילה שמתחילה ב-\( x \) יהיה זוגי והאורך של מילה שמתחילה ב-\( y \) יהיה אי זוגי, אבל אני לא יכול סתם לקחת את הזוגות הללו ולהתייחס אליהן כאל בעיית PCP רגילה, כי \( a_{1}=b_{1} \) הוא פתרון לבעיית ה-PCP הרגילה (פשוט מתעלמים מה-\( \left(x,y\right) \)). אני חייב איכשהו להכריח את \( \left(x,y\right) \) להיות הזוג הראשון אם בכלל תהיה תקווה כלשהי לכך שנקבל מילה משותפת.

הרעיון הוא לדחוף סימן מיוחד - שוב פעם אשתמש ב-\( \# \) - בין כל שתי אותיות, של כל מילה שמופיעה בכל זוג, אבל בצורה כזו שהמילה השמאלית בכל זוג תסתיים ב-\( \# \), ואילו המילה הימנית בכל זוג תתחיל ב-\( \# \). כלומר, אני אהפוך את הזוג \( \left(11,11\right) \) לזוג \( \left(1\#1\#,\#1\#1\right) \). שימו לב לחוסר ההתאמה הזה במיקומי ה-\( \# \)-ים; הוא מכוון.

כעת, גם ל-\( \left(x,y\right) \) אעניק טיפול דומה במובן זה שאדחוף להם \( \# \) בין כל שתי אותיות, אבל אף אחד מהם לא יתחיל ב-\( \# \), ורק השמאלי יסתיים ב-\( \# \), כלומר, אני הופך את \( \left(11,1\right) \) ל-\( \left(1\#1\#,1\right) \).

עכשיו, מה קורה פה? המילה \( xa_{1} \), שקודם הייתה \( 1111 \), הפכה עכשיו ל-\( 1\#1\#1\#1\# \). המילה \( yb_{1} \) הפכה ל-\( 1\#1\#1 \). כלומר - כל מילה שמורכבת מהמילים השמאליות בכל זוג הולכת להסתיים ב-\( \# \), וכל מילה שמורכבת מהמילים הימניות בכל זוג תסתיים בלי ה-\( \# \) הזה. הדרך היחידה לקבל מילה זהה היא “לסגור” את הסיפור באמצעות עוד זוג מיוחד - הזוג \( \left(@,\#@\right) \) כאשר גם \( @ \) הוא תו מיוחד חדש שבו אני משתמש ולא מופיע במילים האחרות.

בואו נתאר פורמלית את מה שעשיתי. נגדיר אופרטור \( \Phi \) שלוקח מילה \( w=\sigma_{1}\dots\sigma_{k} \) ודוחף לה \( \# \) בין כל האותיות, כלומר \( \Phi\left(w\right)=\sigma_{1}\#\sigma_{2}\dots\#\sigma_{k} \). כעת, אם קיבלנו בעיית PCP-עם-זוג-התחלתי \( \left(x,y\right),\left(a_{1},b_{1}\right),\dots,\left(a_{n},b_{n}\right) \) נייצר בעיית PCP “רגילה” עם הזוגות הבאים: לכל \( \left(a_{i},b_{i}\right) \) יהיה לנו את הזוג \( \left(\Phi\left(a_{i}\right)\#,\#\Phi\left(b_{i}\right)\right) \). כמו כן, במקום \( \left(x,y\right) \) יהיה לנו \( \left(\Phi\left(x\right)\#,\Phi\left(y\right)\right) \), וכמו כן יהיה לנו את הזוג הנוסף \( \left(@,\#@\right) \). זה תרגיל מצויין לשבת ולהוכיח שזה עובד - שלבעיה המקורית היה פתרון אם ורק אם לבעיה החדשה עם ה-\( \# \)-ים יש.

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

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

פורמלית מכונת טיורינג \( M \) בנויה מקבוצת מצבים סופית \( Q \), מא”ב סופי כלשהו \( \Sigma \) ומפונקציית מעברים \( \delta:Q\times\Sigma\to Q\times\Sigma\times\left\{ R,L,S\right\} \). \( \delta\left(q,\sigma\right)=\left(p,\tau,X\right) \) פירושו “אם היית במצב \( q \) וקראת \( \sigma \) עבור למצב \( p \), שנה את תוכן התא ל-\( \tau \) והזז את הראש \( X \)” כאשר אם \( X \) הוא \( L \) מזיזים את הראש צעד אחד שמאלה, אם הוא \( R \) מזיזים אותו צעד אחד ימינה ואם הוא \( S \) לא זזים. כמו כן למכונה יש מצב מיוחד \( q_{f}\in Q \) שאם המכונה נכנסה אליו, אומרים שהיא “עצרה” ומפסיקים את החישוב שלה, ו-\( \delta \) לא מוגדרת עליו (זה לא מתאים לכתיב הפורמלי שלי שבו \( \delta \) מוגדרת על התחום \( Q\times\Sigma \) אבל למי אכפת - אני מרשה לפונקציה הזו לא להיות מוגדרת על כל התחום שלה). יש גם סימן מיוחד \( \flat\in\Sigma \) שמהווה את תוכן תאי הסרט כשהמכונה רק מתחילה לרוץ (חושבים עליו בתור “תא ריק”) ומצב מיוחד \( q_{0}\in Q \) שבו המכונה נמצאת כשהיא מתחילה לרוץ.

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

כעת, בכל רגע נתון של הריצה שלה, הריצה של המכונה מאופיינת על ידי שלושה דברים: המצב הפנימי הנוכחי של המכונה; המיקום של הראש הקורא/כותב על גבי הסרט; ותוכן הסרט. שלושת אלו יחד נקראים הקונפיגורציה של המכונה. אפשר לכתוב קונפיגורציה בקיצור בצורה הבאה: סדרה של תווים שמתארת את תוכן תאי הסרט, כאשר התא שמעליו נמצא הראש הקורא/כותב אינו תו מתוך \( \Sigma \) אלא תו מיוחד שהוא זוג של תו מתוך \( \Sigma \) יחד עם תו שמתאר את המצב הפנימי הנוכחי של המכונה. למשל, \( ab\flat\left(q_{3},b\right)\flat a\flat \) היא מחרוזת שמתארת את הקונפיגורציה הבאה: תוכן הסרט הוא \( ab\flat b\flat a\flat\flat\flat\dots \), המצב הפנימי הוא \( q_{3} \) ומיקום הראש הוא מעל תא 4 (אם מתחילים את הספירה מ-1). שימו לב שקונפיגורציה מתוארת על ידי מחרוזת סופית למרות שהסרט הוא אינסופי - זאת מכיוון שאנחנו יודעים בודאות שכל תא שהמכונה טרם הגיעה אליו הוא ריק, ולכן אפשר להסכים שהמחרוזת מתארת רק את תוכן כל תאי הסרט שהמכונה הגיעה אליהם עד כה מתישהו במהלך ריצתה.

כעת, נניח שבמכונה שאת הקונפיגורציה שלה תיארתי לפני רגע יש את המעבר הבא: \( \delta\left(q_{3},b\right)=\left(q_{5},c,R\right) \). אז מהקונפיגורציה \( ab\flat\left(q_{3},b\right)\flat a\flat \) המכונה הולכת לעבור לקונפיגורציה \( ab\flat c\left(q_{5},\flat\right)a\flat \). ודאו לעצכם שאתם מבינים למה - זה יהיה קריטי לחלוטין בשביל מה שנעשה בהמשך להבין את כל הקטע המעיק הזה של מעבר קונפיגורציות (מעיק? למה מעיק? לדעתי זה נפלא, צורת התיאור הזו; אבל כל עוד לא רואים איך עושים איתה דברים מגניבים - כמו רדוקציה ל-PCP - זה נראה כמו משהו טכני יבשושי).

אם מקונפיגורציה א’ מגיעים לקונפיגורציה ב’ תוך צעד אחד, אומרים שב’ היא עוקבת של א’. כמו כן, למכונה יש קונפיגורציה התחלתית פשוטה במיוחד - \( \left(q_{0},\flat\right) \) (“הסרט ריק, המצב הוא \( q_{0} \), הראש נמצא בתחילת הסרט”). קונפיגורציה סופית היא כל קונפיגורציה שבה המצב של המכונה הוא \( q_{f} \). בעיית העצירה היא בסך הכל השאלה הבאה - בהינתן מכונה \( M \), האם קיימת סדרת קונפיגורציות עוקבות שמתחילה בקונפיגורציה ההתחלתית ומסתיימת בקונפיגורציה סופית? והשאלה הזו, כאמור, אינה כריעה (לא ניכנס כעת להוכחה של הטענה הזו).

איך כל זה קשור ל-PCP? על פניו זה לא נראה כל כך קשור; אבל בואו ננסה לחשוב איך בכל זאת אפשר לקשר. ב-PCP השאלה היא האם קיימת “מילה משותפת” שאפשר לבנות בשתי דרכים שונות עם אותה סדרת אינדקסים; בבעיית העצירה השאלה היא האם קיימת “סדרת קונפיגורציות” שמתארת ריצה חוקית מקונפיגורציה התחלתית לקונפיגורציה סופית. אלו האובייקטים שעלינו לתרגם ביניהם - האם אפשר לתאר סדרת קונפיגורציות חוקית בתור מילה? בוודאי! כבר הראיתי איך לתאר קונפיגורציה בודדת בתור מילה, אז פשוט בואו נתקע איזה סימן \( \# \) בין קונפיגורציות עוקבות! וכדי לפשט קצת יותר את העניינים, בואו ניפטר מהסוגריים המיותרים הללו שיש בתוך קונפיגורציה: במקום לכתוב \( ab\flat\left(q_{3},b\right)\flat a\flat \) נכתוב \( ab\flat q_{3}b\flat a\flat \) וכל עוד הסימבולים שמתארים מצבים והסימבולים שמתארים את הא”ב של המכונה הם שונים זה מזה לא תהיה בעיה של דו משמעות כאן.

הנה דוגמה לסדרת קונפיגורציות שכזו:

\( q_{0}\flat\#aq_{1}\flat\#q_{2}aa\#q_{f}aa \)

אל תקראו רגע את ההמשך - שבו וכתבו במפורש אילו מעברים צריכים להיות במכונה כדי שתיתן את סדרת הקונפיגורציות הזו. רק כך נוכל להיות בטוחים שאתם מבינים את הפרטים הטכניים הרלוונטיים כאן - והפרטים הללו יהיו לב העניין אחר כך. כתבתם? יפה. המעברים הם \( \delta\left(q_{0},\flat\right)=\left(q_{1},a,R\right) \) ו-\( \delta\left(q_{1},\flat\right)=\left(q_{2},a,L\right) \) ו-\( \delta\left(q_{2},a\right)=\left(q_{f},a,S\right) \).

עכשיו משהסכמנו על כך שהמילה המשותפת שנייצר תהיה סדרת קונפיגורציות שמתארת ריצה חוקית שעוצרת, נשאלת רק השאלה איך “לכפות” על המילה שנוצרת באמת לתאר ריצה כזו. לשם כך נצטרך להתבסס בצורה חזקה על הדרישה שיש לנו מ-PCP: שאותה סדרה תיווצר בשתי דרכים שונות, על ידי אותם אינדקסים. מה שנעשה הוא שניצור את המילה בצורה כזו שצד שמאל “רודף” כל הזמן אחרי צד ימין ומפגר אחריו בקונפיגורציה אחת בדיוק, וההזדמנות היחידה שלו להשיג את צד ימין ולהשלים את המילה היא אם צד ימין הגיע למצב הסופי \( q_{f} \). כדי לעשות את זה יותר ברור אני לא אצייר את המילים בתור צד שמאל וצד ימין אלא בתור למעלה ולמטה. בהתחלה שתי המילים שנבנות ייראו כך:

\( \begin{array}{cc}\#\\\# & q_{0}\flat\#\end{array} \)

כעת, כדי שלמילה למעלה יהיה סיכוי “להדביק” את המילה שלמטה ועדיין להיות זהה לה, האותיות הבאות שחייבות להתווסף אליה הן \( q_{0}\flat \). עכשיו, נניח שלמכונה יש את הצעד הבא: \( \delta\left(q_{0},\flat\right)=\left(q_{1},a,R\right) \). אנחנו רוצים שאחרי הוספת הזוג הבא, המילים שאנחנו בונים ייראו כך:

\( \begin{array}{ccc}\# & q_{0}\flat\\\# & q_{0}\flat & \#aq_{1}\end{array} \)

כלומר, המילה שלמעלה “כיסתה” את החלק של \( q_{0}\flat \) ואילצה את המילה שלמטה לבצע את המעבר שמקודד ב-\( \delta\left(q_{0},\flat\right) \). איך נעשה את זה? פשוט מאוד: לרשימת הזוגות שלנו נוסיף את הזוג \( \left(q_{0}\flat,aq_{1}\right) \). הוספת הזוג הזה למילה שנבנית יגרום בדיוק לתוצאה שאנחנו מעוניינים בה.

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

\( \begin{array}{cccc}\# & q_{0}\flat & \#\\\# & q_{0}\flat & \# & aq_{1}\#\end{array} \)

עכשיו, נניח שיש לנו את המעבר \( \delta\left(q_{1},\flat\right)=\left(q_{2},\flat,S\right) \). איך נטפל בו? אנחנו אמורים להוסיף את הזוג \( \left(q_{1}\flat,q_{2}\flat\right) \) וזה בסדר גמור, אבל אם תשימו לב, במילה שלנו \( q_{1} \) נמצא משמאל ל-\( \# \) שמסמן את סוף הקונפיגורציה, ולא משמאל ל-\( \flat \). הרעיון הוא שהראש של המכונה הגיע אל הקצה של הסרט שכבר ראינו, ולכן במובלע נובע שיש שם \( \flat \) אבל זה לא נכתב במפורש עדיין. איך נפתור את הבעיה הזו? פתרון מתבקש אחד הוא להוסיף מעבר מהצורה \( \left(q_{1}\#,q_{2}\flat\#\right) \) - אבל זה קצת מסורבל. אפשר להיות יותר חכמים ולמנוע את הבעיה מראש, כבר בשלב סגירת הקונפיגורציה: במקום להשתמש בזוג \( \left(\#,\#\right) \) אנחנו רוצים לאפשר גם להשתמש בזוג \( \left(\#,\flat\#\right) \) שאומר לקונפיגורציה למטה להוסיף \( \flat \) כי אולי נזדקק לו תכף. אם היינו משתמשים בזוג הזה, זוג המילים שאנחנו בונים היה מהצורה:

\( \begin{array}{cccc}\# & q_{0}\flat & \#\\\# & q_{0}\flat & \# & aq_{1}\flat\#\end{array} \)

וכעת אין בעיה; הזוג \( \left(q_{1}\flat,q_{2}\flat\right) \) מטפל בסיטואציה הנוכחית. האם סיימנו? לא, כי שימו לב ל-\( a \) בתחילת הקונפיגורציה - זו האות הבאה שהמילה למעלה צריכה להוסיף לעצמה, וגם במילה למטה היא צריכה להופיע כי המכונה לא נוגעת בה בצעד הזה. אז נוסיף לנו זוג \( \left(a,a\right) \), וכעת על ידי שימוש ב-\( \left(a,a\right) \) ואחריו ב-\( \left(q_{1}\flat,q_{2}\flat\right) \), נקבל:

\( \begin{array}{ccccccc}\# & q_{0}\flat & \# & a & q_{1}\\\# & q_{0}\flat & \# & a & q_{1} & \# & aq_{2}\flat\end{array} \)

לבסוף, נסגור את הקונפיגורציה בצורה “רגילה” עם \( \left(\#,\#\right) \) ונקבל:

\( \begin{array}{cccccc}\# & q_{0}\flat & \# & a & q_{1}\#\\\# & q_{0}\flat & \# & a & q_{1}\# & aq_{2}\flat\#\end{array} \)

בואו נדבר עכשיו על תזוזה שמאלה של הראש, כלומר נניח שיש לנו את המעבר \( \delta\left(q_{2},\flat\right)=\left(q_{3},b,L\right) \). מה קורה כאן? אנחנו רוצים לעבור לסיטואציה הבאה:

\( \begin{array}{cccccccc}\# & q_{0}\flat & \# & a & q_{1}\# & aq_{2}b\\\# & q_{0}\flat & \# & a & q_{1}\# & aq_{2}\flat & \# & q_{3}ab\end{array} \)

כלומר, ב”מחיר” של הוספת \( aq_{2}b \) למעלה אנחנו רוצים להוסיף \( q_{3}ab \) למטה. לכן נוסיף את הזוג \( \left(aq_{2}b,q_{3}ab\right) \) לרשימת הזוגות שלנו.

רק דבר אחד עוד נותר לנו להבין לפני שנעבור לתיאור פורמלי של הכל - איך מסיימים? איך מאפשרים למילה שלמעלה להדביק את המילה שלמטה?

ובכן, בואו ניתן למכונה הבדיונית המסכנה שלי להגיע אל המנוחה והנחלה - נניח שיש לנו את המעבר \( \delta\left(q_{3},a\right)=\left(q_{f},a,S\right) \). קודם כל, הוא יתבטא, כרגיל, בזוג \( \left(q_{3}a,q_{f}a\right) \) ונגיע אל הסיטואציה הבאה:

\( \begin{array}{ccccccccc}\# & q_{0}\flat & \# & a & q_{1}\# & aq_{2}b & \# & q_{3}a\\\# & q_{0}\flat & \# & a & q_{1}\# & aq_{2}\flat & \# & q_{3}a & b\#q_{f}a\end{array} \)

המילה שלמעלה עדיין צריכה להדביק את ה-\( b\# \) שלמטה עד שתגיע למצב שבו היא צריכה להשוות את ה-\( q_{f} \) שלמטה; את זה היא תעשה עם הזוגות \( \left(b,b\right) \) ו-\( \left(\#,\#\right) \), ואז נגיע למצב הבא:

\( \begin{array}{cccccccccc}\# & q_{0}\flat & \# & a & q_{1}\# & aq_{2}b & \# & q_{3}a & b\#\\\# & q_{0}\flat & \# & a & q_{1}\# & aq_{2}\flat & \# & q_{3}a & b\# & q_{f}ab\#\end{array} \)

מה היינו רוצים שיקרה עכשיו? ובכן, היינו שמחים אם היה לנו את הזוג הבא: \( \left(q_{f}ab\#\#,\#\right) \), שהיה משלים אותנו למילה המשותפת הבאה:

\( \begin{array}{cccccccccc}\# & q_{0}\flat & \# & a & q_{1}\# & aq_{2}b & \# & q_{3}a & b\# & q_{f}ab\#\#\\\# & q_{0}\flat & \# & a & q_{1}\# & aq_{2}\flat & \# & q_{3}a & b\# & q_{f}ab\#\#\end{array} \)

למה לא להוסיף זוג כזה, באמת? למה לא להוסיף זוגות מהצורה \( \left(q_{f}w\#,\#\right) \) כאשר \( w \) הוא המשך של קונפיגורציה עד ה-\( \# \) שבסוף שלה, וזאת לכל \( w \) אפשרית? תיאורטית, זה בדיוק מה שהיינו רוצים לעשות. מעשית, זה בלתי אפשרי כי יש אינסוף ערכים אפשריים של \( w \), אבל בעיית PCP תמיד מורכבת ממספר סופי של זוגות. אז יש לנו כאן מגבלה טכנית קלה, ולכן יהיה לה פתרון טכני קל. במקום “לאכול” את כל הקונפיגורציה בבת אחת, נאכל אותה תו תו.

מה זה אומר? זה אומר שנתחיל עם הזוג \( \left(q_{f}a,q_{f}\right) \), ואחרי שנשתמש בו נגיע לסיטואציה הבאה:

\( \begin{array}{ccccccccccc}\# & q_{0}\flat & \# & a & q_{1}\# & aq_{2}b & \# & q_{3}a & b\# & q_{f}a\\\# & q_{0}\flat & \# & a & q_{1}\# & aq_{2}\flat & \# & q_{3}a & b\# & q_{f}a & b\#q_{f}\end{array} \)

עכשיו נעתיק את שארית הקונפיגורציה עד לפעם הבאה שבה המילה שלמעלה תצטרך לכתוב \( q_{f} \), ונגיע לדבר הבא:

\( \begin{array}{cccccccccccc}\# & q_{0}\flat & \# & a & q_{1}\# & aq_{2}b & \# & q_{3}a & b\# & q_{f}a & b\#\\\# & q_{0}\flat & \# & a & q_{1}\# & aq_{2}\flat & \# & q_{3}a & b\# & q_{f}a & b\# & q_{f}b\#\end{array} \)

מה קרה פה? אם נקרא רק את המילה למטה, זה נראה כאילו עברנו מהקונפיגורציה \( q_{f}ab \) לקונפיגורציה \( q_{f}b \) - כאילו ה-\( a \) “נאכל” על ידי \( q_{f} \). זה בדיוק מה שהולך לקרות - \( q_{f} \) הרעבתן הולך לבלוס את כל המילה שנמצאת מימינו בקונפיגורציה, אות אחרי אות. ומתי נוכל לסיים? כשיגיע הזמן לבלוס את ה-\( \# \) שבסוף. כלומר, כשנגיע למצב הבא:

\( \begin{array}{cccccccccccccc}\# & q_{0}\flat & \# & a & q_{1}\# & aq_{2}b & \# & q_{3}a & b\# & q_{f}a & b\# & q_{f}b & \#\\\# & q_{0}\flat & \# & a & q_{1}\# & aq_{2}\flat & \# & q_{3}a & b\# & q_{f}a & b\# & q_{f}b & \# & q_{f}\#\end{array} \)

את זה אפשר לסיים על ידי הזוג \( \left(q_{f}\#\#,\#\right) \), מה שיביא אותנו אל

\( \begin{array}{cccccccccccccc}\# & q_{0}\flat & \# & a & q_{1}\# & aq_{2}b & \# & q_{3}a & b\# & q_{f}a & b\# & q_{f}b & \# & q_{f}\#\#\\\# & q_{0}\flat & \# & a & q_{1}\# & aq_{2}\flat & \# & q_{3}a & b\# & q_{f}a & b\# & q_{f}b & \# & q_{f}\#\#\end{array} \)

וסיימנו!

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

\( \begin{array}{cc}\#q_{0}\flat\#\\\#q_{0}\flat\# & aq_{f}\#\end{array} \)

מה עכשיו? כדי להשוות את ה-\( a \) שיש למטה, חייבים להשתמש בזוג \( \left(a,a\right) \), ואז נגיע לסיטואציה הבאה:

\( \begin{array}{ccc}\#q_{0}\flat\# & a\\\#q_{0}\flat\# & a & q_{f}\#a\end{array} \)

אבל עכשיו אם נשתמש בזוג \( \left(q_{f}\#\#,\#\right) \), מה שנגיע אליו יהיה

\( \begin{array}{cccc}\#q_{0}\flat\# & a & q_{f}\#\#\\\#q_{0}\flat\# & a & q_{f}\#a & \#\end{array} \)

ויש לנו כאן בבירור אי התאמה. לכן אין מנוס - נצטרך “לאכול” את ה-\( a \) עם זוג מהצורה \( \left(aq_{f},q_{f}\right) \). יחד איתנו נגיע ישירות מהמצב הבא:

\( \begin{array}{cc}\#q_{0}\flat\#\\\#q_{0}\flat\# & aq_{f}\#\end{array} \)

אל המצב הזה:

\( \begin{array}{ccc}\#q_{0}\flat\# & aq_{f}\\\#q_{0}\flat\# & aq_{f} & \#q_{f}\end{array} \)

ומכאן נגיע אל

\( \begin{array}{cccc}\#q_{0}\flat\# & aq_{f} & \#\\\#q_{0}\flat\# & aq_{f} & \# & q_{f}\#\end{array} \)

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

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

• הזוג ההתחלתי יהיה \( \left(\#,\#q_{0}\flat\#\right) \).
• לכל \( a\in\Sigma \) יהיה לנו הזוג \( \left(a,a\right) \)
• יהיו לנו הזוגות \( \left(\#,\#\right) \) ו-\( \left(\#,\flat\#\right) \).
• לכל מעבר \( \delta\left(q,\sigma\right)=\left(p,\tau,R\right) \) יהיה לנו הזוג \( \left(q\sigma,\tau p\right) \).
• לכל מעבר \( \delta\left(q,\sigma\right)=\left(p,\tau,S\right) \) יהיה לנו הזוג \( \left(q\sigma,p\tau\right) \).
• לכל מעבר \( \delta\left(q,\sigma\right)=\left(p,\tau,L\right) \) ולכל \( a\in\Sigma \) יהיה לנו הזוג \( \left(aq\sigma,pa\tau\right) \).
• לכל \( a\in\Sigma \) יהיו לנו הזוגות \( \left(q_{f}a,q_{f}\right) \) ו-\( \left(aq_{f},q_{f}\right) \).
• יהיה לנו הזוג \( \left(q_{f}\#\#,\#\right) \).

וזו הבניה כולה! קלה, אחרי שמבינים את הרעיון. האם הצלחתי להסביר את הרעיון?