בתשובה לתוהה, 15/12/06 22:59
 |
|
 |
||
|
||||
 |
אפשר לצאת מהשאלה של התוהה ולהגיע לשאלה "מעניינת". למשל, נניח שאנו מסתכלים על קבוצת כל המ"ט הקיימות ועל כל הקלטים שאורכם קטן מאורך נתון כלשהו (X תווים). האם אז קיים אלגוריתם שפותר את בעיית העצירה? (שימו לב שלא הגבלתי את אורך התכנית אלא את אורך הקלט). הסיבה שהשאלה הזאת נראית מעניינת בעיני היא שאז באמת ההוכחה של טיורינג לא עובדת (נראה לי) כי הקלט לא יכול להיות זהה או שקול לתוכנה. |
 |
 |
 |
|
|
|
||
|
||||
|
אפשר להראות משהו הרבה יותר חזק: אפילו לגבי הקלט 0 בלבד אי אפשר להכריע באופן כללי אם M עוצרת עליו או לא. למה? בוא נניח שאפשר (יש אלגוריתם Q שעושה את זה), אז אני אראה לך איך לפתור את בעיית העצירה. אתה נותן לי M וקלט x, ואני בונה מכונה חדשה, M_x, שמה שהיא עושה הוא זה: היא *מתעלמת* מהקלט שלה, ובמקום זה כותבת את x על סרט הקלט, חוזרת לתחילתו, ומכאן ואילך מתנהגת כמו M. כלומר, M_x היא פשוט דרך להריץ את M על x בלי ש-x יתקבל כקלט. עכשיו, ברור ש-M_x עוצרת על 0 (או כל קלט אחר) אם ורק אם M עוצרת על x. אז פשוט נחזיר את התשובה ש-Q מחזיר - פתרנו את בעית העצירה. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |