תורת החישוביות/כריעות שפות/רדוקציה חישובית

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

דוגמה לרדוקציה ומאפייניה

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

1. נקח את הרשימה המקורית, ונמיר אותה לרשימת המספרים ההפוכים בסימניהם לרשימה המקורית (לדוגמה, הרשימה $[1,-3,4,2]$ תהפוך לרשימה $[-1,3,-4,-2]$).
2. נפעיל את השגרה שכבר קיימת לנו, ונחזיר את תוצאתה.

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

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

1. לכל קלט לבעיה המקורית יש קלט מומר לבעיה הקודמת – ניתן להמיר כל קלט.
2. ניתן לבצע את ההמרה ע״י מ״ט – ההמרה ברת־חישוב.
3. מפתרון הבעיה הקודמת אפשר להסיק חד-משמעית את הפתרון לבעיה .

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

רדוקציות בין שפות

רדוקציה: כל הקלטים ב־$L_{1}$ ממופים לקלטים של $L_{2}$, ואילו קלטים שאינם ב־$L_{1}$ ממופים לקלטים שאינם ב־$L_{2}$

הגדרה: תהיינה $L_{1},L_{2}$ שפות מעל א"ב $\Sigma$. הפונקציה $f:\Sigma ^{*}\to \Sigma ^{*}$ נקראת רדוקציה מ־$L_{1}$ ל־$L_{2}$ אם מתקיים: f היא פונקציה מלאה. f ניתנת לחישוב. הרדוקציה תקפה: $x\in L_{1}$ אם״ם $f(x)\in L_{2}$. נאמר ששפה $L_{1}$ ניתנת לרדוקציה ל־$L_{2}$ אם קיימת רדוקציה מ־$L_{1}$ ל־$L_{2}$, ונסמן: $L_{1}\leq L_{2}$.

המשמעות היא שניתן להמיר קלט עבור הבעיה $L_{1}$ לקלט מתאים עבור השפה $L_{2}$. אם יש לנו "כלי" שמכריע את השפה $L_{2}$, אותו כלי יכול לשמש להכרעת $L_{1}$.

דוגמאות

רדוקציה משפת האלכסון לשפה האוניברסלית

נראה כי שפת האלכסון $L_{D}$ ניתנת לרדוקציה לשפה האוניברסלית $L_{U}$, כלומר $L_{D}\leq L_{U}$.

נגדיר את פונקצית הרדוקציה $f(\langle M\rangle )=(\langle M\rangle ,\langle M\rangle )$. נוכיח כי זו רדוקציה בהתאם להגדרה:

1. f אכן פונקציה מלאה, לכל מחרוזת קלט מוגדרת מחרוזת פלט שהיא שכפול של מחרוזת הקלט.
2. f ניתנת לחישוב במ״ט – כל שהמכונה צריכה לעשות הוא לשכפל את הקלט על סרט הזיכרון.
3. הרדוקציה תקפה:
   • אם $\langle M\rangle \in L_{D}$ אזי מהגדרת $L_{D}$ נובע ש־$\langle M\rangle \in L(M)$, כלומר המכונה M מקבלת את המחרוזת $\langle M\rangle$. מכאן נובע $(\langle M\rangle ,\langle M\rangle )\in L_{U}$ לפי הגדרת השפה $L_{U}$.
   • הכיוון השני מוכח באופן זהה:

$\langle M\rangle \notin L_{D}\Rightarrow \langle M\rangle \notin L(M)\Rightarrow (\langle M\rangle ,\langle M\rangle )\notin L_{U}$

שימו לב: טענת אם״ם מוכיחים ע״י הוכחת שני הכיוונים: כיוון ה"אם" וכיוון ה"ורק אם"..

רדוקציה מהשפה האוניברסלית לבעיית העצירה

נראה כי השפה האוניברסלית $L_{U}$ ניתנת לרדוקציה לבעיית העצירה $L_{\text{HP}}$, כלומר $L_{U}\leq L_{\text{HP}}$.

נגדיר את הפונקציה $f(\langle M\rangle ,x)=(\langle A\rangle ,x)$ כאשר $\langle A\rangle$ היא קידוד של מ״ט שנבנית מתוך הקידוד של M באופן הבא: כל מעבר של M למצב $q_{rej}$ מוחלף בלולאה אינסופית (למשל, ע״י מעבר למצב חדש q שתמיד עובר לעצמו, ללא תלות בקלט). נובע:

• M ו־A מתקדמות באופן זהה פרט לכך שאם M מנסה לדחות, A נכנסת ללולאה:
  • אם M לא עוצרת ← A לא עוצרת
  • אם M דוחה ← A לא עוצרת
  • אם M מקבלת ← A מקבלת
• לכן, אם $(\langle M\rangle ,x)\in L_{U}$, כלומר, M מקבלת את הקלט x אזי A מקבלת את הקלט x, ובפרט עוצרת עליו, ומתקיים $(\langle A\rangle ,x)\in L_{\text{HP}}$.
• מצד שני כאשר $(\langle M\rangle ,x)\notin L_{U}$ אזי M או דוחה את x או לא עוצרת עליו. בשני המקרים A לא עוצרת על x ומתקיים $(\langle A\rangle ,x)\notin L_{\text{HP}}$.
• משני אלו נובעת התקפות של הרדוקציה. קל לראות שזו פונקציה מלאה וניתנת לחישוב ע״י מ״ט (כל שהמכונה נדרשת לעשות הוא החלפת הקידוד של מעבר ל־$q_{rej}$ במעבר אחר).

תכונות בסיסיות של רדוקציות

1. לכל שפה L, מתקיים $L\leq L$ ע״י פונקציית הזהות.
2. אם f היא רדוקציה מ־$L_{1}$ ל־$L_{2}$, ו־g היא רדוקציה מ־$L_{2}$ ל־$L_{3}$, אזי ההרכבה $g\circ f$ היא רדוקציה מ־$L_{1}$ ל־$L_{3}$. (זוהי תכונת טרנזיטיביות)$L_{1}\leq L_{2},L_{2}\leq L_{3}\;\Rightarrow \;L_{1}\leq L_{3}$
3. אם f היא רדוקציה מ־$L_{1}$ ל־$L_{2}$ אז אותה הפונקציה f היא גם רדוקציה מ־${\overline {L_{1}}}$ ל־${\overline {L_{2}}}$. (נובע מהגדרת הרדוקציה)

משפט הרדוקציה

משפט: משפט הרדוקציה אם $L_{1},L_{2}$ שפות מעל $\Sigma$ כך שקיימת רדוקציה $L_{1}\leq L_{2}$ אזי:     $L_{2}\in R\Rightarrow L_{1}\in R$ $L_{2}\in RE\Rightarrow L_{1}\in RE$ $L_{2}\in coRE\Rightarrow L_{1}\in coRE$

במילים אחרות, אם השפה $L_{2}$ שייכת למחלקה כלשהי, גם השפה $L_{1}$ שייכת לאותה מחלקה. באופן אינטואיטיבי, העובדה ש־$L_{2}$ שייכת לאחת מן המחלקות הללו משמעותה שקיימת מ״ט מסויימת (לפי ההגדרה המתאימה של המחלקה) שמכריעה או מזהה אותה. עקב קיומה של פונקצית הרדוקציה, ניתן לבנות מ״ט שראשית ממירה קלט של $L_{1}$ לקלט של $L_{2}$ (ע״י חישוב הפונקציה f), ואח״כ מריצה את המכונה של $L_{2}$ על מנת לפתור את הבעיה $L_{1}$. כעת נוכיח רעיון זה באופן פורמלי:

הוכחה: נניח שקיימת רדוקציה f מ־$L_{1}$ ל־$L_{2}$ והיא ניתנת לחישוב ע״י מ״ט $M_{f}$.

$L_{2}\in R$ אזי קיימת מ״ט $M_{2}$ המכריעה את $L_{2}$. נבנה מ״ט $M_{1}$ המכריעה את $L_{1}$:

על קלט x, המכונה $M_{1}$ מריצה את $M_{f}$ (הפיכת הקלט x לקלט שמתאים ל־$L_{2}$), ומריצה את $M_{2}$ על הקלט המומר. המכונה מחזירה את אותה התשובה שהחזירה $M_{2}$ על הקלט המומר.

מכיוון ש־f פונקציה מלאה, חישוב $f(x)$ יסתיים לכל קלט x, ומכיוון ש־$M_{2}$ מכריעה (כלומר, עוצרת על כל קלט) גם המכונה $M_{1}$ עוצרת לבסוף על כל קלט. כמו כן, f תקפה, כלומר $x\in L_{1}$ אם״ם $f(x)\in L_{2}$. לכן אם $x\in L_{1}$ אז הקלט המומר $f(x)\in L_{2}$, ו־$M_{2}$ תקבל את הקלט. מכאן שבמקרה זה $M_{1}$ מקבלת את x. מצד שני, אם $x\notin L_{1}$ אזי $f(x)\notin L_{2}$ ולכן $M_{2}$ דוחה את הקלט המומר, וגם $M_{1}$ דוחה כנדרש. מכאן נובע – $M_{1}$ מכריעה את $L_{1}$ ו־$L_{1}\in R$ לפי ההגדרה.

ההוכחות עבור סעיפים 2 ו־3 דומות להוכחה לעיל. במקרה זה ייתכן ש־$M_{2}$ לא עוצרת על קלטים מסויימים, וגם $M_{1}$ לא תעצור על אותם הקלטים. אבל אלו יהיו בדיוק הקלטים עליהם מותר ל־$M_{1}$ לא לעצור, לפי ההגדרה המתאימה של $RE$, $coRE$.

המשפט לעיל מענין דווקא בגלל הכיוון ההפוך שלו:

משפט: משפט הרדוקציה ההפכי נניח $L_{1}\leq L_{2}$ אזי, $L_{1}\notin R\;\Rightarrow \;L_{2}\notin R$ $L_{1}\notin RE\;\Rightarrow \;L_{2}\notin RE$ $L_{1}\notin coRE\;\Rightarrow \;L_{2}\notin coRE$

הסבר: נניח ש־$L_{1}\notin R$. אם $L_{2}\in R$ נובע ממשפט הרדוקציה שהוכחנו לעיל שגם $L_{1}\in R$, וזו סתירה.

משפט זה שימושי ביותר להראות ששפות אינן כריעות. מספיק להוכיח ששפה מסוימת $L_{1}$ אינה כריעה (כלומר, אינה ב־R), ובעזרתה נוכל להוכיח ששפות אחרות אינן כריעות ע״י רדוקציה מ־$L_{1}$ אל אותן השפות. בד״כ ביצוע רדוקציה היא פעולה פשוטה בהרבה מאשר הוכחה ישירה ששפה אינה כריעה.

שימושים במשפט הרדוקציה

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

טענה:      ${\overline {L_{D}}}\notin R$

נראה, בשיטת הלכסון כי השפה ${\overline {L_{D}}}\notin R$. כזכור,

${\overline {L_{D}}}=\{\langle M\rangle \;\mid \;\langle M\rangle \notin L(M)\}$

נניח בשלילה ש־${\overline {L_{D}}}\in R$ ולכן קיימת מ״ט $M_{D}$ שמכריעה את ${\overline {L_{D}}}$.

נביט על המחרוזת $\langle M_{D}\rangle$. נניח כי $\langle M_{D}\rangle \in {\overline {L_{D}}}$ אזי מהגדרת השפה נובע כי $\langle M_{D}\rangle \notin L(M_{D})$. במילים אחרות, אם מריצים את $M_{D}$ על המחרוזת $\langle M_{D}\rangle$, המכונה לא תקבל את הקלט, ובפרט היא תדחה אותו (כי היא מכונה מכריעה). אבל, זו סתירה, כי הנחנו ש־$\langle M_{D}\rangle \in {\overline {L_{D}}}$, כלומר, הקלט בשפה ו־$M_{D}$ צריכה לקבל אותו מכיוון שהיא מכריעה את השפה.

נחזור על הטיעון עבור המקרה השני. אם מניחים כי המחרוזת אינה בשפה, $\langle M_{D}\rangle \notin {\overline {L_{D}}}$, אזי המכונה $M_{D}$ צריכה לדחות את הקלט $\langle M_{D}\rangle$. מכאן ש־$M_{D}$ אינה מקבלת את המחרוזת של עצמה, ולכן היא שייכת ל־${\overline {L_{D}}}$, או באופן יותר מדוייק, הקידוד שלה נמצא בשפה זו, $\langle M_{D}\rangle \in {\overline {L_{D}}}$ וזו סתירה להנחה.

נשים לב ש־$R$ סגורה למשלים. לפיכך, מכיוון ש־${\overline {L_{D}}}\notin R$, כך גם השפה המשלימה $L_{D}\notin R$.

כעת נראה ששאר השפות שראינו בפרק כריעות למחצה חיובית אינן כריעות.

1. אי כריעות השפה האוניברסלית – ראינו מקודם שמתקיים $L_{D}\leq L_{U}$. ממשפט הרדוקציה ההפכי, נובע שבגלל ש־$L_{D}\notin R$ אז גם $L_{U}\notin R$.
2. אי כריעות שפת בעיית העצירה – ראינו מקודם שמתקיים $L_{U}\leq L_{\text{HP}}$. ממשפט הרדוקציה ההפכי, נובע שבגלל ש־$L_{U}\notin R$ אז גם $L_{\text{HP}}\notin R$.

תרגיל : סווג את השפות הבאות למחלקה המתאימה ($R,RE\smallsetminus R,coRE\smallsetminus R$ או מחוץ ל־$RE\cup coRE$): $L_{D},L_{U},L_{HP},{\overline {L_{D}}},{\overline {L_{U}}},{\overline {L_{\text{HP}}}}$
{{{פתרון}}}

כדאי לדעת: השווה בין ההוכחה ש־$L_{\text{HP}}\notin R$ כפי שהובאה בפרק קיום שפות שאינן כריעות לבין ההוכחה לעיל של שפת האלכסון, בתוספת שרשרת הרדוקציות משפת האלכסון אל $L_{\text{HP}}$. ההוכחה ה"ישירה" למעשה מכילה את שרשרת הרדוקציות באופן אינהרנטי, ומבצעת את הליכסון המוביל לסתירה על המכונה שמוגדרת ע״י שרשרת הרדוקציות.

שפה שאינה כריעה למחצה

לסיום, נראה שימוש ברדוקציה כדי להראות שפה ספציפית שאינה ב־$RE\cup coRE$:

טענה: נגדיר $L_{\Sigma ^{*}}=\{\langle M\rangle \mid L(M)=\Sigma ^{*}\}$, אוסף כל המכונות שמקבלות כל מילה אפשרית ב־$\Sigma ^{*}$. אזי מתקיים           $L_{\Sigma ^{*}}\notin RE\cup coRE$

נוכיח טענה זו ע״י שימוש ברדוקציה ובמשפט הרדוקציה ההפכי. אם נוכל להראות רדוקציה אל $L_{\Sigma ^{*}}$ משפה שאינה ב־RE, וגם משפה (אחרת) שאינה ב־coRE, אז ישתמע ש$L_{\Sigma ^{*}}$ אינה ב־RE וגם אינה ב־coRE, כנדרש. להלן עיקרי הרדוקציות. הפרטים המלאים נשארים כתרגיל לקורא.

• $HP\leq L_{\Sigma ^{*}}$: בעזרת הקלט $(\langle M\rangle ,x)$ נבנה מכונה חדשה $M_{x}$, כך שאם $M$ עוצרת על x אז $M_{x}$ מקבלת כל קלט שלה, ואחרת, $M_{x}$ אינה עוצרת.
• ${\overline {HP}}\leq L_{\Sigma ^{*}}$: בעזרת הקלט $(\langle M\rangle ,x)$ נבנה מכונה $M_{x}$ שעל הקלט w מבצעת כלהלן: מריצה את $M$ על x למשך $|w|$ צעדים. אם $M$ עצרה, $M_{x}$ דוחה. קל לראות שאם M לא עוצרת על x, אז $M_{x}$ מקבלת כל מילה ב־$\Sigma ^{*}$.

הפרק הקודם: קיום שפות שאינן כריעות

רדוקציה חישובית

הפרק הבא: משפט רייס