משפט רייס

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

באופן פורמלי, שפת הקידודים למכונות הטיורינג, שהשפה שלהן ב-S L_S= \{ \langle M\rangle \mid L(M) \in S\} היא שפה **[[כריעות|בלתי כריעה]]** אם \ S היא קבוצה **לא-טריוויאלית** של שפות.

בנוסף, אם מתקיים כי **<math>\varnothing \in S</math>** אזי השפה אינה כריעה למחצה.

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

## הוכחת המשפט

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

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

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

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

התוכנית שלנו תיצור מ-\ M ו-\ x אלגוריתם חדש, \ M_x, שפועל בצורה הבאה על הקלט \ w:
:#הפעל את \ M על הקלט \ x (אם קיים פלט, נתעלם ממנו).
:#הפעל את \ 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 נתון מחשב פונקציה בעלת תכונה לא טריוויאלית שהפונקציה הריקה לא מקיימת.

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

* 
* 
* 

קטגוריה:חישוביות
רייס
קטגוריה:הוכחות
קטגוריה:בעיות שאינן ניתנות לחישוב