בעיית ההתאמה של פוסט
בעיית ההתאמה של פוסט היא בעיה ידועה במדעי המחשב, שתוארה לראשונה בשנת 1946 בידי אמיל פוסט ומהווה דוגמה פשוטה יחסית (ועל כן שימושית) לבעיה בלתי כריעה, כלומר שאינה ניתנת לפתרון באמצעות מודלי החישוב המקובלים (ובפרט על ידי מחשב).
תיאור הבעיה
הבעיה עוסקת במחרוזות - רצפי אותיות מעל אלפבית כלשהו. נתונה קבוצה סופית של זוגות של מחרוזות (בלי מגבלה על האורכים האפשריים שלהן), מהצורה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (a_1,b_1),(a_2,b_2),\dots(a_n,b_n)} . השאלה היא האם ניתן לבחור חלק מהזוגות (אולי יותר מפעם אחת) ולשרשר את כל ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a_i} בזוגות שנבחרו ואת ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ b_i} בזוגות שנבחרו (כלומר, לכתוב אותם בזה אחר זה) כך ששני השרשורים יתנו את אותה המחרוזת.
בכתיבה פורמלית, השאלה היא האם קיימת סדרת אינדקסים, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ i_1,i_2,\dots i_k} , כולם בתחום הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 1,\dots,n} כך ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a_{i_1}a_{i_2}\dots a_{i_k}=b_{i_1}b_{i_2}\dots b_{i_k}} .
דוגמה
|
, |
|
בדוגמה זו ניתן ליצור את המילה "בללייקה" סימולטנית באמצעות סדרת האינדקסים 1,2,2,3,4: החזרה על אינדקס ה-2 מכפילה את הל' בסדרת ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a_i} , ואת ה-י' בסדרת ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ b_i} .
אם יוסר זוג מספר 2, לא ניתן יהיה למצוא התאמה. זאת מכיוון שאם סדרת ההתאמות מכילה את זוג מספר 1, אז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ b_1} יוסף את האות ל' למילה הנבנית, וזו לא ניתנת ליצירה מה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a_i} (לאחר שהורדנו את זוג מספר 2), אם היא מכילה את 3 אז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a_3} יוסיף את האות י' למילה הנבנית, וזו לא קיימת עבור ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ b_i} ; מכאן עולה שהיא חייבת להיות מורכבת מ-4 בלבד, אבל אורך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a_4} שונה מאורך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ b_4} ולכן שתי המילים שהם בונים בו זמנית יהיו בעלות אורך שונה, ובפרט לא אותה מילה.
בדוגמה זו ניתן להיווכח בקיום/אי קיום התאמה על ידי שיקולים פשוטים יחסית; בדוגמאות מורכבות יותר השיקולים הללו לא יעבדו יותר, ומכאן המוטיבציה לניסיון למציאת אלגוריתם כללי לפתרון הבעיה - אלגוריתם שכאמור, אינו יכול להתקיים.
הוכחת אי כריעות
ההוכחה המקובלת לאי כריעות בעיית ההתאמה מבוססת על אי כריעותה של בעיית העצירה. הרעיון הבסיסי של ההוכחה הוא להראות כי ניתן לבצע מעין סימולציה של ריצת מכונת טיורינג באמצעות מופע של בעיית ההתאמה, כך שהמכונה מסיימת את ריצתה אם ורק אם קיימת התאמה במופע זה. אם בעיית ההתאמה הייתה ניתנת לפתרון, אז בהינתן מכונת טיורינג וקלט ניתן היה לתרגם אותן למופע המתאים של בעיית ההתאמה, לפתור את המופע הזה (כלומר, לגלות האם קיימת בו התאמה או לא) ולהכריע בשאלת עצירתה של מכונת הטיורינג המקורית. מכיוון שבעיית העצירה אינה כריעה, נובע מכך שגם בעיית ההתאמה חייבת להיות אי כריעה.
ההמרה מבוצעת בשני שלבים. ראשית, במקום לעסוק ישירות בבעיית ההתאמה של פוסט עוסקים בווריאנט שלה, הזהה לה כמעט לחלוטין פרט לכך שזוג המחרוזות הראשונות שייבחר נתון מראש, ולא ניתן לבחירה מתוך כלל המחרוזות. הבדל זה מאפשר ליצור מחרוזת מיוחדת שמתארת את "המצב ההתחלתי" של מכונת טיורינג, ובאמצעותה לבצע סימולציה בו זמנית של ריצת המכונה הן באיברים השמאליים בכל זוג שמתווסף למילה אותה מרכיבים, והן באיברים הימניים, כשהריצה שבאגף שמאל תמיד מקדימה בצעד אחד את הריצה שבאגף ימין, כך שהדרך היחידה שבה תושג התאמה (כלומר, המילה שנבנתה על ידי אגף שמאל תשתווה למילה שנבנתה על ידי אגף ימין) היא אם ריצת המכונה תסתיים ובכך אגף ימין יוכל "להשיג" את אגף שמאל.
שלב א' - מעבר לבעיית התאמה עם מחרוזת ראשונה נתונה
הווריאנט על בעיית פוסט שבו משתמשים בהוכחת אי הכריעות הוא כדלהלן: נתון אוסף של זוגות של מחרוזות, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (a_1,b_1),(a_2,b_2),\dots(a_n,b_n)} , ובנוסף נתון עוד זוג אחד מיוחד, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (x,y)} . השאלה היא האם קיימת סדרת אינדקסים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ i_1,i_2,\dots i_k} , כולם בתחום הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 1,\dots,n} כך ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ xa_{i_1}a_{i_2}\dots a_{i_k}=yb_{i_1}b_{i_2}\dots b_{i_k}} .
בחלק הבא של ההוכחה מוכיחים כי בעיה זו אינה כריעה. מכאן שכדי להראות כי בעיית פוסט המקורית היא בלתי כריעה, יש להראות כי ניתן "לתרגם" כל מופע של הבעיה החדשה למופע של הבעיה המקורית בצורה כזו שהמופע של הבעיה החדשה פתיר אם ורק אם המופע של הבעיה הישנה פתיר (דבר שכזה מכונה רדוקציה חישובית).
אם כן, נניח כי נתון אוסף זוגות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (a_1,b_1),(a_2,b_2),\dots(a_n,b_n)} וכמו כן נתון הזוג המיוחד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (x,y)} . הרעיון הבסיסי בהמרת בעיה זו לבעיית פוסט המקורית היא לקחת סימן שאינו באלפבית הנוכחי של המחרוזות (למשל, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ *} ) ו"להשתיל" אותו בתוך כל הזוגות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (a_i,b_i)} באופן כזה שבאיבר הימני של כל זוג הכוכביות מופיעות לפני כל אות, ואילו באיבר השמאלי הכוכביות מופיעות אחרי כל אות. מכאן שלא ניתן להתחיל את בניית המילה המשותפת עם אף אחד מהזוגות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (a_i,b_i)} ש"טופלו" באופן שכזה, כי האיבר הימני בזוג מתחיל בכוכבית, ואילו השמאלי לא. כדי שעדיין יהיה ניתן ליצור מילה משותפת, יש לתקן את הזוג הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (x,y)} בהתאם, וכמו כן להוסיף זוג אחד נוסף, ש"יסיים" את בניית המחרוזת וישווה את מספר הכוכביות שבכל אחד מהעותקים.
כדי לתאר בצורה פורמלית את הבנייה נוח להגדיר שתי פונקציות על מילים, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ L(w),R(w)} , שעבור המילה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ w=w_1w_2\dots w_m} "משתילות" כוכביות באופן הבא:
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ L(w)=*w_1*w_2*\dots *w_m}
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ R(w)=w_1*w_2*\dots *w_m*}
כעת, אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ P=\left\{(x,y),(a_i,b_i)\right\}} הוא אוסף הכללים של הבעיה שאותה מתרגמים, אז אוסף הכללים החדש יהיה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ P^\prime=\left\{(R(a_i),L(b_i))|1\le i\le n\right\}\cup\left\{(L(x)*,L(y)),(\$,*\$)\right\}}
כאשר גם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \$} הוא סימן שאינו שייך לאלפבית של הבעיה המקורית.
שלב ב' - סימולציה של מכונת טיורינג באמצעות בעיית ההתאמה
חלקה השני של ההוכחה מסתמך על כך שהמודל החישובי של מכונת טיורינג הוא פשוט מאוד לתיאור, ועל כן ניתן לבצע מעין "סימולציה" שלו באמצעות בעיית ההתאמה. הרעיון הבסיסי הוא לתאר חישוב של מכונת טיורינג בתור סדרה של תצורות (קונפיגורציות) שכל אחת מהן מתארת את מצבו הנוכחי של סרט הקלט, מיקום הראש הקורא והמצב הפנימי הנוכחי של המכונה. קונפיגורציה שכזו נוח לתאר באמצעות סדרת תווים מהאלפבית של המכונה, המציינת את תוכן סרט הקלט הנוכחי (עם סימן מיוחד המצביע על הנקודה שבה מסתיים החלק של הסרט שבו נעשה שימוש עד כה), אשר בתוכה "מושתל" סימן המתאים למצב הפנימי הנוכחי של המכונה, והוא נמצא משמאל לתא בסרט שהמכונה קוראת. כך למשל הסדרה הבאה:
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 01001q_3010\$}
מייצגת את הקונפיגורציה שבה החלק של הסרט שבשימוש מכיל את המחרוזת "01001010", המכונה נמצאת במצב הפנימי מס' 3, והראש הקורא מצביע על ה-"0" הלפני אחרון.
ניתן כעת לחשוב על חישוב שלם של המכונה כסדרה עוקבת של קונפיגורציות שמופרדות על ידי סימן מיוחד (למשל, כוכבית) כך שכל אחת מהן מתקבלת מקודמתה באמצעות פונקציית המעברים של מכונת הטיורינג. דוגמה לסדרה שכזו:
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ q_000\$*1q_10\$*11q_2\$*11q_30\$*1q_010\$}
מחרוזת זו מייצגת את הריצה שבה המכונה התחילה במצב 0 ועם שני אפסים כתובים על הסרט, שינתה את הראשון מביניהם ל-1 עברה למצב 1 ונעה עם הראש הקורא ימינה, שינתה את השני ל-1, עברה למצב 2 ונעה שוב ימינה, כתבה 0 על הסרט, עברה למצב הפנימי 3 ונשארה באותו מקום על הסרט, ולבסוף נעה צעד אחד שמאלה ועברה למצב הפנימי 0.
הסימולציה של מכונת הטיורינג מתבצעת כך: ראשית, הזוג ההתחלתי של מילים בבעיית ההתאמה יהיה הזוג הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (*q_0w\$*,*)} , כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ w} היא המילה שעבורה נבדקת עצירת המכונה. כלומר - האיבר השמאלי בזוג מתאר את הקונפיגורציה ההתחלתית של המכונה, ואילו האיבר הימני הוא "ריק". מכאן שכדי שהזוגות ירכיבו את אותה המילה, בחירת האיברים הבאים צריכה להיות כזו ש"תעתיק" את הקונפיגורציה שקיימת באגף שמאל לאגף ימין. הרעיון הוא שתוך כדי ביצוע ההעתקה הזו לאגף ימין, תיווצר (על ידי האיברים השמאליים בזוגות שיתווספו) קונפיגורציה חדשה באגף שמאל - כזו שנובעת מיידית מהקונפיגורציה הקודמת. כך למשל לכל תו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \sigma} , הזוג הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (\sigma,\sigma)} מבטיח העתקה של תוכן הסרט מהקונפיגורציה הקודמת לנוכחית, וזוגות כמו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (\tau p, q \sigma)} (שמתאים למעבר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (p,\tau, R)\in\delta(q,\sigma)} ) מבטיחים את שינוי הקונפיגורציה החדשה על פי פעולה אפשרית עבור מכונת הטיורינג המסמלצת.
כל עוד המכונה לא הגיע למצב מקבל, אגף ימין לא יכול להדביק את אגף שמאל; על כן, מוסיפים זוגות שמאפשרים, בהינתן שאגף שמאל מייצג קונפיגורציה שהגיעה למצב מקבל, "למחוק" חלקים מהקונפיגורציה בכל העתקה שלה, עד שלבסוף אגף ימין מדביק את אגף שמאל. בצורה זו מובטח שקיים פתרון לבעיית ההתאמה אם ורק אם המכונה המסומלצת מגיעה למצב מקבל.
בעיית ההתאמה של פוסט38013699Q798572