תורת החישוביות/משפט הרקורסיה: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←משפט הרקורסיה: עיצוב, הגהה |
|||
שורה 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>, הסרט יכיל את מחרוזת <math> \langle B_{ \langle A\rangle \langle C\rangle}\rangle \langle A\rangle \langle C\rangle, w</math>, כאשר <math>w</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, כנדרש.
| |||