תורת החישוביות/משפט הרקורסיה: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ הפסקת שימוש בתבנית הפניה לויקיפדיה |
מ ←מכונת־טיורניג מייצרת עצמה: תיקון |
||
שורה 33:
נביט על הפעולה <code>"הדפס כפלט את המחרוזת הבאה"</code>. עבור מ״ט ה"מחרוזת הבאה" יכולה להופיע בשני מקומות: או שהיא מופיעה על הסרט או שהיא מקודדת כחלק ממצבי המכונה <math>Q</math> ומפונקציה המעברים <math>\delta</math>. ברור שאם המחרוזת כבר נמצאת על הסרט, אז המצב די פשוט, אבל איך המחרוזת הגיעה לסרט הזיכרון מלכתחילה (הרי המכונה מתחילה כשהסרט ריק)? כלומר, ברור שההתחלה חייבת להיות הדפסת מחרוזת כלשהי על הסרט, כאשר המחרוזת ראשית מקודדת במצבים והמעברים של המכונה.
נזכיר שלכל מחרוזת קבועה x אנחנו יכולים להגדיר מכונה <math>B_x</math> שכל מה שהיא עושה הוא לכתוב את x על הסרט. מכיוון שהמחרוזת x קבועה, המכונה מוגדרת היטב. למשל, המכונה <math>B_{010}</math> יכולה להכיל 4 מצבים שכותבים "010" על הסרט ועוצרים את פעולת המכונה. באופן כללי, בעזרת <math>Q=|x|+1</math> מצבים ניתן לבנות מ״ט כנ״ל לכל מחרוזת <math>x</math> נתונה.
האם המכונה <math>B</math> היא הפתרון שרצינו? כדי שמכונה זו תהווה את הפתרון, אנחנו בעצם רוצים לבנות את <math>B_{\langle B \rangle}</math>, שמדפיסה את הקידוד של עצמה, <math>\langle B \rangle</math>. ושוב נתקלנו בלולאה העצמית, שהרי הקידוד של <math>B</math> תלוי בפלט שהיא כותבת, ואם זו אינה מחרוזת קבועה x, אנחנו בבעיה.
| |||