תורת החישוביות/משפט הרקורסיה: הבדלים בין גרסאות בדף

תוכן שנמחק תוכן שנוסף
Gran (שיחה | תרומות)
Gran (שיחה | תרומות)
שורה 57:
#הרץ את המכונה A (על סרט הזיכרון הנוכחי).
לאחר השלב הראשון סרט הזיכרון יכיל את המחרוזת <math>\langle A\rangle</math>. בשלב השני המכונה A מופעלת על המחרוזת <math>\langle A\rangle</math> (שזו מבחינתה מחרוזת סתמית לכל דבר), ומייצרת על הסרט את הקידוד <math>B_{\langle A \rangle}</math>, ושמה אותו על הסרט לפני המחרוזת הקיימת שם. בסוף התהליך הסרט יכיל את המחרוזת <math>\langle B_{\langle A\rangle} \rangle \langle A\rangle = \langle M\rangle</math>.
 
==משפט הרקורסיה==
הדוגמא לעיל של מכונה המדפיסה את הקידוד של עצמה מעלה מספר שאלות: האם קיימות מכונות נוספות שיודעות את הקידוד שלהן? (בהנחה שכן) האם מי מהן מבצעת פעולה "מעניינת"? משפט הרקורסיה פותר את הסוגיה וקובע ש'''לכל''' פונקציה ברת־חישוב <math>f</math> קיימת מ״ט שמחשבת את f וגם יודעת את הקידוד של עצמה.
 
{{משפט|שם=משפט הרקורסיה|תוכן=לכל מ״ט <math>M</math> קיימת מ״ט <math>M^*</math> כך שמתקיים:
#<math>L(M) = L(M^*)</math>, כלומר, <math>M</math> ו־<math>M^*</math> מכריעות את אותה השפה (מחשבות את אותה הפונקציה)
# <math>M^*</math> יודעת את הקידוד של עצמה, כלומר, עם הפעלתה <math>M^*</math> רושמת את <math>\langle M^* \rangle</math> על סרט הזיכרון (נניח, מייד לאחר הקלט שניתן למכונה)}}
כעת נוכיח את המשפט. נניח שנתונה מכונה <math>M</math> ונראה כיצד לבנות את המכונה <math>M^*</math> בעזרת <math>M</math> ובעזרת המכונות<math>A, B</math> שהגדרנו לעיל.
 
נתחיל בנסיון פשוט לבנות את המכונה: ראשית היא אמורה לכתוב את הקידוד של עצמה על הזיכרון, ולאחר מכן לבצע את הפעולה של M. נבחן את הפתרון <math>M^*=B_xAM</math>, כלומר קודם מריצה את B אח״כ את A ואח״כ את M. לפתרון זה שתי בעיות. ראשית, הפעלת B ואחריו A כותבת על הסרט את הקידוד <math>\langle B \rangle\langle A\rangle</math>, ולא את <math>\langle M^*\rangle</math>. שנית, אם נפעיל את <math>M</math> על הסרט אחרי שכתבנו עליו את הקידוד – התוצאה עלולה להיות לא נכונה, מכיוון ש־<math>M</math> מניחה שכל מה שרשום על הסרט הוא הקלט שלה.
 
ראשית נפתור את הבעיה השניה. נגדיר מכונה C שמבצעת את אותה פעולה כמו M, אבל "מתעלמת" מהחלק הראשון של הקלט שלה. כלומר, אם הקלט של C הוא <math>(x,y)</math>, המכונה מריצה את M על המחרוזת <math>y</math> בלבד. באופן פורמלי <math>C(x,y)=M(y)</math>. קל לבנות מכונה כנ״ל מתוך הקידוד של <math>M</math>. כעת ברור שאם <math>M^*=BAC</math>, והחלק <math>BA</math> יכתוב את <math>\langle M^* \rangle</math> על הסרט ('''לפני הקלט w שכבר רשום על הסרט בתחילת הריצה!''') אז המכונה <math>M^*</math>
תחשב את אותה הפונקציה כמו <math>M</math>, <math>L(M)=L(M^*)</math>.
 
נותר לנו לפתור את הבעיה הראשונה, דהיינו, לגרום לכך שהפעלת המכונות <math>BA</math> תייצר את הקידוד של <math>M^*</math>. נשים לב שלפי הגדרת <math>M^*</math> הקידוד שלה נתון ע״י <math>\langle M^*\rangle = \langle B_x\rangle\langle A\rangle\langle C\rangle</math>. כמו מקודם, נוכל לקבוע את המחרוזת x לכל מחרוזת קבועה שנרצה. במקרה זה אם נקבע <math>x= \langle A\rangle \langle C\rangle</math> נקבל שלאחר הרצת המכונות <math>B_{ \langle A\rangle \langle C\rangle}A</math>, הסרט יכיל את מחרוזת <math> \langle B_{ \langle A\rangle \langle C\rangle}\rangle \langle A\rangle \langle C\rangle, w</math> והרצת <math>C</math> לאחר מכן תחשב את <math>M</math> על w, כנדרש.
{{הערה|בהוכחה הנ"ל קיים אי־דיוק: נצטרך להגדיר את A,B מחדש כך שהן מתעלמות מהקלט w.. אבל קל לראות שפעולה זו אינה משנה את נכונות ההוכחה}}
 
==לקריאה נוספת==
* [[w:en:Quine (computing)|Quine (computing)]]{{D}}, ויקיפדיה באנגלית.
* דאגלס הופשטטר, '''Gödel, Escher, Bach: an Eternal Golden Braid'''‏ , 1979.
*
 
[[קטגוריה:תורת החישוביות]]