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

נביט על הפעולה <code>"הדפס כפלט את המחרוזת הבאה"</code>. עבור מ״ט ה"מחרוזת הבאה" יכולה להופיע בשני מקומות: או שהיא מופיעה על הסרט או שהיא מקודדת כחלק ממצבי המכונה <math>Q</math> ומפונקציה המעברים <math>\delta</math>. ברור שאם המחרוזת כבר נמצאת על הסרט, אז המצב די פשוט, אבל איך המחרוזת הגיעה לסרט הזיכרון מלכתחילה (הרי המכונה מתחילה כשהסרט ריק)? כלומר, ברור שההתחלה חייבת להיות הדפסת מחרוזת כלשהי על הסרט, כאשר המחרוזת ראשית מקודדת במצבים והמעברים של המכונה.

נזכיר שלכל מחרוזת קבועה <math>x</math> אנחנו יכולים להגדיר מכונה <math>B_x</math> שכל מה שהיא עושה הוא לכתוב את x על הסרט. מכיוון שהמחרוזת x קבועה, המכונה מוגדרת היטב. למשל, המכונה <math>B_{010}</math> יכולה להכיל 4 מצבים שכותבים "010" על הסרט ועוצרים את פעולת המכונה. באופן כללי, בעזרת <math>Q=|x|</math> מצבים ניתן לבנות מ״ט כנ״ל לכל מחרוזת <math>x</math> נתונה.

האם מכונההמכונה <math>B</math> היא הפתרון שרצינו? כדי שמכונה זו תהווה את הפתרון, אנחנו בעצם רוצים לבנות את <math>B_{\langle B \rangle}</math>, שמדפיסה את הקידוד של עצמה, <math>\langle B \rangle</math>. ושוב נתקלנו בלולאה העצמית, שהרי הקידוד של <math>B</math> תלוי בפלט שהיא כותבת, ואם זו אינה מחרוזת קבועה x, אנחנו בבעיה.

הפעולה של מכונה <math>A</math> היא פשוטה: היא לוקחת את המחרוזת x וכותבת אותה "פעמים" על הסרט. כלומר, אחרי הרצת המכונה <math>M</math>, סרט הזיכרון יכיל את התוכן <math>xx</math>:

<center><math>(empty) \Longrightarrow_;\stackrel{B_{x}}{\Longrightarrow}\; x \Longrightarrow_;\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>: לכל אות ב־x בונים מצב ומעבר מתאים של <math>B_x</math>.

{{אתגר|בנה מ״ט שעל הקלט x משנה את סרט הזיכרון כך שיופיע הקידוד של <math>B_x</math> המתאימה{{רווח קשיח|2}}}}.

נריץ את המכונה M שבנינו עד כה ונראה שמתקבל הפלט <math> \langle B_x\rangle\ x</math> (מאד דומה למה שרצינו!):

<center><math>(empty) \Longrightarrow_;\stackrel{B_{x}}{\Longrightarrow}\; x \Longrightarrow_;\stackrel{A}{\Longrightarrow} \;\langle B_x\rangle x </math></center>

הפלט שקיבלנו עד כה הוא <math>\langle B_x \rangle \langle Ax\rangle</math>, ואילו הפלט שנחנושאנחנו רוצים הוא <math>\langle B_x\rangle \langle A\rangle</math>. מכאן ברור שהמחרוזת x היא לא אחרת מאשר הקידוד של המכונה A, <math>x=\langle A\rangle</math>. נשים לב ש'''זו מחרוזת קבועה''', מדובר סה״כ במ״ט שמקבלת קלט כלשהו w וכותבת על הסרט את הקידוד של המכונה <math>B_w</math> עבור אותו פלט שקיבלה. מכונה זו מוגדרת היטב, ויש לה קידוד מסויים <math>\langle A \rangle</math> שלא קשה להגדיר (ראה אתגר לעיל).

לסיכום, נגדיר מ״ט שמייצרת את הקידוד של עצמה. המכונה <math>M</math> על קלט כלשהו w:

לאחר השלב הראשון סרט הזיכרון יכיל את המחרוזת <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>.