תורת החישוביות/כריעות שפות/רדוקציה חישובית/ארגז חול

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

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

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

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 )$. נוכיח כי זו רדוקציה בהתאם להגדרה: f אכן פונקציה מלאה, לכל מחרוזת קלט מוגדרת מחרוזת פלט שהיא שכפול של מחרוזת הקלט. f ניתנת לחישוב במ״ט – כל שהמכונה צריכה לעשות הוא לשכפל את הקלט על סרט הזיכרון. הרדוקציה תקפה: אם $\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}$ ניתנת לרדוקציה לבעיית העצירה $HP$, כלומר $L_{U}\leq 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 {\text{HP}}$. מצד שני כאשר $(\langle M\rangle ,x)\notin L_{U}$ אזי M או דוחה את x או לא עוצרת עליו. בשני המקרים A לא עוצרת על x ומתקיים $(\langle A\rangle ,x)\notin {\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}$

1. אם 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}$ אל אותן השפות. בד״כ ביצוע רדוקציה היא פעולה פשוטה בהרבה מאשר הוכחה ישירה ששפה אינה כריעה.

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

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

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

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

-

ארגז חול

-