 |
יותר משזו בעיה, זה "אתגר" - תוכיח לי שלא קיים אלגוריתם Q שפותר את בעית העצירה עם הקלטים M, x תחת ההנחה שאם אלגוריתם S כלשהו משתמש ב-Q הוא מעביר לו כקלט גם את המידע על עצמו ועל הקלט שהוא עצמו קיבל.
את כל זה אי אפשר לנסח בצורה משביעת רצון שאני רואה בלשון של מכונות טיורינג. התוהה השתמש בצורה חזקה מאוד בכך שיש איזו מכונה שלישית, שמריצה גם את Q וגם את S, ומוודאת ש-S באמת מעבירה את הקלט הזה ולא משקרת.
בהתחלה התוהה הציג גרסה פשוטה יותר של האתגר: להוכיח שלא ניתן לפתור את בעיית העצירה גם אם מגבילים את הקלטים להיות מהצורה M,x כאשר M שונה מ-x. אפשר להוכיח באופן ישיר שגם אלגוריתם לפתרון הבעיה הזו לא קיים (הראיתי איך קודם), אבל גם רדוקציה מבעיית העצירה לבעיה הזו (שים לב: לא בכיוון ההפוך) קל להדגים: אם קיבלת M ו-x תעביר אותם לאלגוריתם הפלאי אם M שונה מ-x. אחרת, שנה את M בצורה שתחזיר מכונה שקולה (למשל, תוסיף עוד מצב פנימי שלא מגיעים אליו אף פעם) ואז תעביר את הקלט לאלגוריתם הפלאי.
|
 |
RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש