משפט רייס

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

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

$$L_{S}=\{\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$ נתון מחשב פונקציה בעלת תכונה לא טריוויאלית שהפונקציה הריקה לא מקיימת.

קישורים חיצוניים

• גדי אלכסנדרוביץ', על הבעיה הלא טריוויאלית של זיהוי תכונה לא טריוויאלית, באתר "לא מדויק", 9 באוקטובר 2007
• גדי אלכסנדרוביץ', משפט רייס – הגרסה המלאה, באתר "לא מדויק", 18 במאי 2011
• משפט רייס, באתר MathWorld (באנגלית)

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

34176378משפט רייס