משפט רייס

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

באופן פורמלי, השפה

L= \{ \langle M\rangle \mid  L(M) \in S\}

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

הוכחת המשפט[עריכת קוד מקור | עריכה]

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

מקרה ראשון: הפונקציה הריקה אינה בעלת התכונה[עריכת קוד מקור | עריכה]

נניח בשלילה שקיים אלגוריתם \ Q שמכריע האם הפונקציה שמחשב אלגוריתם נתון היא בעלת התכונה, ונראה כי ניתן לפתור בעזרתו את בעיית העצירה.

מכיוון שהתכונה לא טריוויאלית, קיים אלגוריתם כלשהו \ A המחשב פונקציה שיש לה את התכונה הזו. בעזרת \ A נבנה תוכנית שתפתור את בעיית העצירה. התוכנית מקבלת את הקלט הסטנדרטי עבור בעיית העצירה: אלגוריתם \ M וקלט \ x, ומטרתה לומר האם \ M מסיים את ריצתו על \ x או ממשיך לרוץ לנצח.

התוכנית שלנו תיצור מ-\ M ו-\ x אלגוריתם חדש, \ M_x, שפועל בצורה הבאה על הקלט \ w:

  1. הפעל את \ M על הקלט \ x (אם קיים פלט, נתעלם ממנו).
  2. הפעל את \ A על הקלט \ w והחזר את התוצאה כפלט.

כלומר, האלגוריתם \ M_x מורכב משני שלבים שאינם קשורים זה בזה. החשיבות של השלב הראשון בכך שהוא מהווה אבן בוחן לשאלה האם \ M עוצר על \ x; אם הוא אינו עוצר, \ M_x לא יגיע לעולם לשלב השני.

בשל אופן הבנייה שלו, \ M_x מחשב אחת משתי פונקציות: אם \ M לא עוצר על \ x, הרי ש-\ M_x מחשב את הפונקציה הריקה - שכן ללא תלות בקלט \ w, הוא פשוט רץ לנצח. אם לעומת זאת \ M_x כן עוצר על \ x, הרי שהוא יחשב בשלב הבא את פעולת הפונקציה של \ A על הקלט \ w.

מכיוון שהפונקציה הריקה אינה בעלת התכונה, ואילו \ A כן בעלת התכונה, נובע מכך שהכרעה בשאלה האם \ M_x מקיימת את התכונה מכריעה גם את השאלה האם \ M_x עוצרת על \ x. לכן כל מה שהתוכנית שלנו עושה כדי לפתור את בעיית העצירה הוא לבדוק באמצעות \ Q האם \ M_x בעלת התכונה, ולענות כמוהו. כלומר, מצאנו פתרון לבעיית העצירה - וזה בלתי אפשרי, בסתירה להנחה הראשונה שקיים אלגוריתם שבודק את קיום התכונה.

מקרה שני: הפונקציה הריקה בעלת התכונה[עריכת קוד מקור | עריכה]

נשים לב כי לכל תכונה \ X ניתן לחשוב על התכונה ה"משלימה" לה, \ \overline{X}. פונקציה מקיימת את \ \overline{X} אם ורק אם היא אינה מקיימת את \ X.

אם קיים אלגוריתם \ Q שמכריע האם הפונקציה שמחשב \ A היא בעלת התכונה \ X, אז ניתן ליצור בעזרתו אלגוריתם אחר שבודק האם \ A היא בעלת התכונה \ \overline{X} - הוא פשוט מריץ את \ Q על \ A ועונה הפוך ממנו.

אלא שהפונקציה הריקה אינה בעלת התכונה \ \overline{X} (שכן הנחנו שהיא כן בעלת התכונה \ X) ולכן הגענו לסתירה לתוצאה שהוכחנו בסעיף הקודם - הראינו כיצד ניתן להכריע האם אלגוריתם \ A נתון מחשב פונקציה בעלת תכונה לא טריוויאלית שהפונקציה הריקה לא מקיימת.

קישורים חיצוניים[עריכת קוד מקור | עריכה]