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

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


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

עריכה

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

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

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

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

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

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

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

עריכה
 
רדוקציה: כל הקלטים ב־  ממופים לקלטים של  , ואילו קלטים שאינם ב־  ממופים לקלטים שאינם ב־ 


הגדרה:

תהיינה   שפות מעל א"ב  . הפונקציה   נקראת רדוקציה מ־  ל־  אם מתקיים:

  1. f היא פונקציה מלאה.
  2. f ניתנת לחישוב.
  3. הרדוקציה תקפה:   אם״ם  .

נאמר ששפה   ניתנת לרדוקציה ל־  אם קיימת רדוקציה מ־  ל־ , ונסמן:  .

המשמעות היא שניתן להמיר קלט עבור הבעיה   לקלט מתאים עבור השפה  . אם יש לנו "כלי" שמכריע את השפה  , אותו כלי יכול לשמש להכרעת  .


דוגמאות

עריכה

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

עריכה

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

נגדיר את פונקצית הרדוקציה  . נוכיח כי זו רדוקציה בהתאם להגדרה:

  1. f אכן פונקציה מלאה, לכל מחרוזת קלט מוגדרת מחרוזת פלט שהיא שכפול של מחרוזת הקלט.
  2. f ניתנת לחישוב במ״ט – כל שהמכונה צריכה לעשות הוא לשכפל את הקלט על סרט הזיכרון.
  3. הרדוקציה תקפה:
    • אם   אזי מהגדרת   נובע ש־ , כלומר המכונה M מקבלת את המחרוזת  . מכאן נובע   לפי הגדרת השפה  .
    • הכיוון השני מוכח באופן זהה:
 
  שימו לב: טענת אם״ם מוכיחים ע״י הוכחת שני הכיוונים: כיוון ה"אם" וכיוון ה"ורק אם"..

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

עריכה

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

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

  • M ו־A מתקדמות באופן זהה פרט לכך שאם M מנסה לדחות, A נכנסת ללולאה:
    • אם M לא עוצרת ← A לא עוצרת
    • אם M דוחה ← A לא עוצרת
    • אם M מקבלת ← A מקבלת
  • לכן, אם  , כלומר, M מקבלת את הקלט x אזי A מקבלת את הקלט x, ובפרט עוצרת עליו, ומתקיים  .
  • מצד שני כאשר   אזי M או דוחה את x או לא עוצרת עליו. בשני המקרים A לא עוצרת על x ומתקיים  .
  • משני אלו נובעת התקפות של הרדוקציה. קל לראות שזו פונקציה מלאה וניתנת לחישוב ע״י מ״ט (כל שהמכונה נדרשת לעשות הוא החלפת הקידוד של מעבר ל־  במעבר אחר).

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

עריכה
  1. לכל שפה L, מתקיים   ע״י פונקציית הזהות.
  2. אם f היא רדוקציה מ־  ל־ , ו־g היא רדוקציה מ־  ל־ , אזי ההרכבה   היא רדוקציה מ־  ל־ . (זוהי תכונת טרנזיטיביות)
     
  3. אם f היא רדוקציה מ־  ל־  אז אותה הפונקציה f היא גם רדוקציה מ־  ל־ . (נובע מהגדרת הרדוקציה)

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

עריכה

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

אם   שפות מעל   כך שקיימת רדוקציה   אזי:    

  1.  
  2.  
  3.  


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

הוכחה: נניח שקיימת רדוקציה f מ־  ל־  והיא ניתנת לחישוב ע״י מ״ט  .

  אזי קיימת מ״ט   המכריעה את  . נבנה מ״ט   המכריעה את  :

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

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

 

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

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


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

נניח   אזי,

  1.  
  2.  
  3.  


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

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

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

עריכה

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

טענה:

           

נראה, בשיטת הלכסון כי השפה  . כזכור,

 

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

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

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

נשים לב ש־  סגורה למשלים. לפיכך, מכיוון ש־ , כך גם השפה המשלימה  .

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

  1. אי כריעות השפה האוניברסלית – ראינו מקודם שמתקיים  . ממשפט הרדוקציה ההפכי, נובע שבגלל ש־  אז גם  .
  2. אי כריעות שפת בעיית העצירה – ראינו מקודם שמתקיים  . ממשפט הרדוקציה ההפכי, נובע שבגלל ש־  אז גם  .



 

כדאי לדעת:

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

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

עריכה

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

טענה:

נגדיר  , אוסף כל המכונות שמקבלות כל מילה אפשרית ב־ . אזי מתקיים          


 

 

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

  •  : בעזרת הקלט   נבנה מכונה חדשה  , כך שאם   עוצרת על x אז   מקבלת כל קלט שלה, ואחרת,   אינה עוצרת.
  •  : בעזרת הקלט   נבנה מכונה   שעל הקלט w מבצעת כלהלן: מריצה את   על x למשך   צעדים. אם   עצרה,   דוחה. קל לראות שאם M לא עוצרת על x, אז   מקבלת כל מילה ב־ .


הפרק הקודם:
קיום שפות שאינן כריעות
רדוקציה חישובית הפרק הבא:
משפט רייס