משפט רייס – הבדלי גרסאות
מ הוספת תבנית:MathWorld בקישורים חיצוניים (תג) (דיון) |
|||
שורה 32: | שורה 32: | ||
==קישורים חיצוניים== |
==קישורים חיצוניים== |
||
{{מיזמים|ויקיספר=תורת החישוביות/כריעות שפות/משפט רייס|שם ויקיספר=תורת החישוביות: משפט רייס}} |
{{מיזמים|ויקיספר=תורת החישוביות/כריעות שפות/משפט רייס|שם ויקיספר=תורת החישוביות: משפט רייס}} |
||
* {{לא מדויק| |
* {{לא מדויק|2007/10/09/rice_theorem/|על הבעיה הלא טריוויאלית של זיהוי תכונה לא טריוויאלית}} |
||
* {{לא מדויק| |
* {{לא מדויק|2011/05/18/rice_theorem_full_version/|משפט רייס – הגרסה המלאה}} |
||
* {{MathWorld}} |
* {{MathWorld}} |
||
גרסה מ־15:31, 1 בדצמבר 2019
משפט רייס הוא משפט מרכזי בתחום החישוביות, שעוסק ביכולת של אלגוריתמים לחקור אלגוריתמים אחרים. המשפט אומר שאין תוכנית מחשב שמקבלת כקלט תוכנית מחשב אחרת, ומכריעה האם הפונקציה שמחשבת תוכנית מחשב זו היא בעלת תכונה מסוימת "לא-טריוויאלית" או לא (כלומר, תכונות אשר מאפיינות חלק מהפונקציות שמחושבות בידי תוכנית מחשב, אך לא את כולן). יש לשים לב שהתכונה היא תכונה של הפונקציה, ולא של תוכנית המחשב עצמה. באופן אינטואיטיבי המשפט טוען שתוכנית מחשב אינה יכולה לדעת כמעט מאום על הפלטים של תוכניות מחשב הנתונות לה כקלט.
באופן פורמלי, השפה
הוכחת המשפט
הוכחת המשפט מפרידה בין שני מקרים, תוך שימוש בפונקציה הריקה. הפונקציה הריקה היא פונקציה שתחום ההגדרה שלה ריק. אלגוריתם מחשב את הפונקציה הריקה אם ורק אם הוא לא עוצר על אף קלט, כלומר נכנס תמיד ללולאה אינסופית או שערכי הביניים של האלגוריתם גדלים תמיד ללא הגבלה.
מקרה ראשון: הפונקציה הריקה אינה בעלת התכונה
נניח בשלילה שקיים אלגוריתם שמכריע האם הפונקציה שמחשב אלגוריתם נתון היא בעלת התכונה, ונראה כי ניתן לפתור בעזרתו את בעיית העצירה.
מכיוון שהתכונה לא טריוויאלית, קיים אלגוריתם כלשהו המחשב פונקציה שיש לה את התכונה הזו. בעזרת נבנה תוכנית שתפתור את בעיית העצירה. התוכנית מקבלת את הקלט הסטנדרטי עבור בעיית העצירה: אלגוריתם וקלט , ומטרתה לומר האם מסיים את ריצתו על או ממשיך לרוץ לנצח.
התוכנית שלנו תיצור מ- ו- אלגוריתם חדש, , שפועל בצורה הבאה על הקלט :
- הפעל את על הקלט (אם קיים פלט, נתעלם ממנו).
- הפעל את על הקלט והחזר את התוצאה כפלט.
כלומר, האלגוריתם מורכב משני שלבים שאינם קשורים זה בזה. החשיבות של השלב הראשון בכך שהוא מהווה אבן בוחן לשאלה האם עוצר על ; אם הוא אינו עוצר, לא יגיע לעולם לשלב השני.
בשל אופן הבנייה שלו, מחשב אחת משתי פונקציות: אם לא עוצר על , הרי ש- מחשב את הפונקציה הריקה - שכן ללא תלות בקלט , הוא פשוט רץ לנצח. אם לעומת זאת כן עוצר על , הרי שהוא יחשב בשלב הבא את פעולת הפונקציה של על הקלט .
מכיוון שהפונקציה הריקה אינה בעלת התכונה, ואילו כן בעלת התכונה, נובע מכך שהכרעה בשאלה האם מקיימת את התכונה מכריעה גם את השאלה האם עוצרת על . לכן כל מה שהתוכנית שלנו עושה כדי לפתור את בעיית העצירה הוא לבדוק באמצעות האם בעלת התכונה, ולענות כמוהו. כלומר, מצאנו פתרון לבעיית העצירה - וזה בלתי אפשרי, בסתירה להנחה הראשונה שקיים אלגוריתם שבודק את קיום התכונה.
מקרה שני: הפונקציה הריקה בעלת התכונה
נשים לב כי לכל תכונה ניתן לחשוב על התכונה ה"משלימה" לה, . פונקציה מקיימת את אם ורק אם היא אינה מקיימת את .
אם קיים אלגוריתם שמכריע האם הפונקציה שמחשב היא בעלת התכונה , אז ניתן ליצור בעזרתו אלגוריתם אחר שבודק האם היא בעלת התכונה - הוא פשוט מריץ את על ועונה הפוך ממנו.
אלא שהפונקציה הריקה אינה בעלת התכונה (שכן הנחנו שהיא כן בעלת התכונה ) ולכן הגענו לסתירה לתוצאה שהוכחנו בסעיף הקודם - הראינו כיצד ניתן להכריע האם אלגוריתם נתון מחשב פונקציה בעלת תכונה לא טריוויאלית שהפונקציה הריקה לא מקיימת.
קישורים חיצוניים
- גדי אלכסנדרוביץ', על הבעיה הלא טריוויאלית של זיהוי תכונה לא טריוויאלית, באתר "לא מדויק", 9 באוקטובר 2007
- גדי אלכסנדרוביץ', משפט רייס – הגרסה המלאה, באתר "לא מדויק", 18 במאי 2011
- משפט רייס, באתר MathWorld (באנגלית)