תורת החישוביות/משפט הרקורסיה: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
. |
|||
שורה 47:
<center><math>(empty) \;\stackrel{B_{x}}{\Longrightarrow}\; x \;\stackrel{A}{\Longrightarrow}\; xx</math></center>
אבל זה לא בדיוק מה שרצינו. הבדל אחד, למשל, הוא שהקידוד של <math>M</math> מכיל בהתחלה את <math>\langle B_x \rangle</math> ולא את x ישירות.
קל לתקן את ההבדל הנ״ל: נשנה את <math>A</math> כך שבמקום להדפיס את x פעמיים, תדפיס את <math>B_x</math> (ולאחריו תשאיר את המחרוזת x
{{אתגר|בנה מ״ט שעל הקלט x משנה את סרט הזיכרון כך שיופיע הקידוד של <math>B_x</math> המתאימה{{רווח קשיח|2}}}}
נריץ את המכונה M שבנינו עד כה ונראה שמתקבל הפלט <math> \langle B_x\rangle\ x</math> (מאד דומה למה שרצינו!):
| |||