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

תוכן שנמחק תוכן שנוסף
Gran (שיחה | תרומות)
Gran (שיחה | תרומות)
שורה 24:
:"הדפס כפלט את המחרוזת הבאה פעמיים, כאשר הפעם השניה בתוך מרכאות".
</code>
 
כעת ננסה לבצע את אותו רעיון בעזרת מכונות־טיורינג.
===מכונת־טיורניג מייצרת עצמה===
בשפה הפורמלית שפיתחנו עד כה, אין "קוד של תוכנה" אלא יש מכונת־טיורינג <math>M</math>, שמכילה מצבים, מעברים וכו'. ראינו, שלכל מכונה יש '''קידוד''' <math>\langle M \rangle</math> שמתאר את המ״ט באופן חד-חד ערכי. לכן השאלה שלנו היא, האם (ואיך) ניתן לבנות מכונה <math>M</math> שכאשר מפעילים אותה, על סרט ריק, עוצרת כאשר על סרט הזיכרון מופיעה המחרוזת <math>\langle M \rangle</math>.
 
נביט על הפעולה <code>"הדפס כפלט את המחרוזת הבאה"</code>. עבור מ״ט ה"מחרוזת הבאה" יכולה להופיע בשני מקומות: או שהיא מופיעה על הסרט או שהיא מקודדת כחלק ממצבי המכונה <math>Q</math>. ברור שאם המחרוזת כבר נמצאת על הסרט, אז המצב די פשוט, אבל איך המחרוזת הגיעה לסרט הזיכרון מלכתחילה (הרי המכונה מתחילה כשהסרט ריק)? כלומר, ברור שההתחלה חייבת להיות הדפסת מחרוזת כלשהי על הסרט, כאשר המחרוזת ראשית מקודדת במצבים והמעברים של המכונה.
 
נזכיר שלכל מחרוזת קבועה <math>x</math> אנחנו יכולים להגדיר מכונה <math>B_x</math> שכל מה שהיא עושה הוא לכתוב את x על הסרט. מכיוון שהמחרוזת x קבועה, המכונה מוגדרת היטב. למשל, המכונה <math>B_{010}</math> יכולה להכיל 4 מצבים שכותבים "010" על הסרט ועוצרים את פעולת המכונה.
 
האם מכונה B היא הפתרון שרצינו? כדי שמכונה זו תהווה את הפתרון, אנחנו בעצם רוצים לבנות את <math>B_{\langle B \rangle}</math>, שמדפיסה את הקידוד של עצמה, <math>\langle B \rangle</math>. ושוב נתקלנו בלולאה העצמית, שהרי הקידוד של <math>B</math> תלוי בפלט שהיא כותבת, ואם זו אינה מחרוזת קבועה x, אנחנו בבעיה.
 
כעת נביט שוב בפתרון הפסאודו־קוד שלעיל. המחרוזת שאנחנו כותבים שם '''אינה הקוד''' אלא רק מחצית הקוד, אותו יש לרשום פעמיים. בעצם יש לנו שתי פעולות שמבוצעות שם:
* הראשונה: יצירת המחרוזת x על הסרט (בפסאודו־קוד x="הדפס כפלט את המחרוזת הבאה פעמיים, כאשר הפעם השניה בתוך מרכאות")
*השנייה: בהינתנן שהמחרוזת x כבר נתונה לנו, צריך לרשום אותה "פעמיים"
הפעולה הראשונה מוסברת ע״י המכונה <math>B</math> שהגדרנו (כרגע, עוד בלי לדעת מהו x המתאים). כעת ננסה להגדיר מ״ט <math>A</math> שתבצע את הפעולה השניה.
 
המכונה <math>A</math> מתחילה כאשר המחרוזת x כבר קיימת על הסרט. איך x הגיעה לסרט? ע״י המכונה <math>B_x</math>. כלומר, אנחנו בונים בעצם מכונה שקודם מריצה את B ואח"כ את A. נקרא למכונה זו <math>M</math> ונסמן <math>\langle M\rangle = \langle B_x\rangle \langle A\rangle </math> לציין שהקידוד של המכונה שמריצה את B ואח״כ את A הוא הקידוד של B ולאחריו הקידוד של A.
 
הפעולה של מכונה A היא פשוטה: היא לוקחת את המחרוזת x וכותבת אותה "פעמים" על הסרט. כלומר, אחרי הרצת המכונה M, סרט הזיכרון יכיל את התוכן <math>xx</math>:
<center><math>(empty) \Longrightarrow_{B_{x}} x \Longrightarrow_{A} xx</math></center>
אבל זה לא בדיוק מה שרצינו. הבדל אחד, למשל, הוא שהקידוד של M מכיל בהתחלה את <math>\langle B_x \rangle</math> ולא את x ישירות.
קל לתקן את ההבדל הנ״ל: נשנה את A כך שבמקום להדפיס את x פעמיים, תדפיס את <math>B_x</math> (ולאחריו תשאיר את המחרוזת x שגבר נמצאת בזיכרון). כפי שראינו לעיל, אם x היא מחרוזת קבועה אז קל לבנות את <math>B_x</math>: לכל אות ב־x בונים מצב ומעבר מתאים של <math>B_x</math>.
{{אתגר|בנה מ״ט שעל הקלט x משנה את סרט הזיכרון כך שיופיע הקידוד של <math>B_x</math> המתאימה}}.
נריץ את המכונה M שבנינו עד כה ונראה שמתקבל הפלט
<center><math>(empty) \Longrightarrow_{B_{x}} x \Longrightarrow_{A} \langle B_x\rangle x </math></center>
 
נותר צעד אחרון - להגדיר מהי המחרוזת הקבועה x ?{{ש}}
הפלט שקיבלנו עד כה הוא <math>\langle B_x \rangle \langle A\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>B_{\langle A\rangle}</math>
#הרץ את המכונה 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>.
 
==לקריאה נוספת==