תורת החישוביות/משפט הרקורסיה: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←משפט הרקורסיה: הגהה |
|||
שורה 59:
==משפט הרקורסיה==
הדוגמא לעיל של מכונה המדפיסה את הקידוד של עצמה מעלה מספר שאלות: האם קיימות מכונות נוספות שיודעות את הקידוד שלהן? (בהנחה שכן) האם מי מהן מבצעת פעולה "מעניינת"? משפט הרקורסיה פותר את הסוגיה וקובע ש'''לכל''' פונקציה ברת־חישוב <math>f</math> קיימת מ״ט שמחשבת את <math>f</math> וגם יודעת את הקידוד של עצמה.
{{משפט|שם=משפט הרקורסיה|תוכן=לכל מ״ט <math>M</math> קיימת מ״ט <math>M^*</math> כך שמתקיים:
#<math>L(M) = L(M^*)</math>, כלומר, <math>M</math> ו־<math>M^*</math> מכריעות את אותה השפה (מחשבות את אותה הפונקציה)
שורה 72:
תחשב את אותה הפונקציה כמו <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>. כמו מקודם, נוכל לקבוע את המחרוזת <math>x</math> לכל מחרוזת קבועה שנרצה. נקבע <math>x= \langle A\rangle \langle C\rangle</math> ונקבל שלאחר הרצת המכונות <math>B_{ \langle A\rangle \langle C\rangle}A</math>, הסרט יכיל את
<center><math>w \; \stackrel{B_{ \langle A\rangle \langle C\rangle}}{\Longrightarrow}\; \langle A\rangle \langle C\rangle, w\; \stackrel{A}{\Longrightarrow}\; \langle B_{ \langle A\rangle \langle C\rangle}\rangle \langle A\rangle \langle C\rangle, w</math></center>
כעת, הרצת <math>C</math> על סרט הזיכרון תחשב את <math>M</math> על w, כנדרש.
| |||