בתשובה לתוהה, 14/12/06 18:45
 |
|
 |
||
|
||||
 |
נסה לכתוב בצורה קצת יותר מסודרת את ההוכחה שלך ותראה שאתה נתקע כבר בהתחלה: אם אתה מתחיל מאלגוריתם מסויים c ורוצה להוכיח ש*רק עבורו* לא קיים a שמבצע את הבדיקה, בפרט אתה לא יכול להחליט שאתה משנה פתאום את c לאלגוריתם אחר, שמשתמש ב-a שאת קיומו אנחנו מניחים. כל העניין בבעיית העצירה (ובבעיות דומות לה - הבעיה של בדיקת המשתנה שאתה מדבר עליה היא גם כן לא כריעה, ומראה את זה משפט רייס) הוא שיש אלגוריתם שמתיימר לדעת את התשובה עבור *כל* האלגוריתמים האפשריים. כלומר, אנחנו לא מתחילים מ-c, אלא דווקא מ-a. |
 |
 |
 |
|
|
|
||
|
||||
|
C לא משתנה, C משתמש בA כדי להחליט מה לעשות. אתה יכול להגיד שהיא לא כריעה, עובדתית כן ניתן לעשות בדיקות כאלה תחת ההנחה המתאימה (שהתוכנה לא פועלת בהתאם לתוצאת הבדיקה). כלומר היא דווקא כן כריעה תחת ההנחה המוקדמת הזאת, וזה בעצם מה שמענין אותנו, מה שמענין אותי זה אם קומפיילר יוכל להגיד לי אם יש בתוכנה שלי לולאה אינסופית או לא, לא מענין אותי שאני יוכל ליצור תוכנות שמשתמשות בתכונה הזאת כדי ליצור בה את ה"באג" שכל פעם שהקומפיילר יגיד כן הם יעשו לא וכל פעם שיגיד לא הן יעשו כן. |
|
|
|
|
|
|
||
|
||||
|
אבל שים לב שאם נוקטים בגישה שלך, מדברים על A עוד לפני ש-C נכנס למשחק. אם כך, איך A יכול להשתמש בו? שוב, אני מציע לך לנסות ולכתוב את ההוכחה שלך בצורה מסודרת, ותראה די מהר את הבעיה. בוודאי שניתן לעשות בדיקות כאלו בפועל. בפועל אין מכונות טיורינג אלא רק תוכנות שרצות על מחשבים סופיים. לא קשה להוכיח שניתן להכריע את בעיית העצירה על כל התוכניות שיש חסם על כמות הזיכרון שבה הן משתמשות - ובעולם האמיתי, אלו כל התוכניות. כמובן שזה עדיין לא אומר שניתן לבצע את הבדיקות הללו ב*יעילות*, אבל על זה ידובר רק במאמר ההמשך, אם יהיה. |
|
|
|
| חזרה לעמוד הראשי |  |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |