בתשובה לתוהה, 14/12/06 18:45
ההוכחה הזאת פשוט דבילית 424568
גדי אלכסנדרוביץ' • בתשובה לתוהה יום ה', 14/12/2006, 20:21
נסה לכתוב בצורה קצת יותר מסודרת את ההוכחה שלך ותראה שאתה נתקע כבר בהתחלה: אם אתה מתחיל מאלגוריתם מסויים c ורוצה להוכיח ש*רק עבורו* לא קיים a שמבצע את הבדיקה, בפרט אתה לא יכול להחליט שאתה משנה פתאום את c לאלגוריתם אחר, שמשתמש ב-a שאת קיומו אנחנו מניחים.

כל העניין בבעיית העצירה (ובבעיות דומות לה - הבעיה של בדיקת המשתנה שאתה מדבר עליה היא גם כן לא כריעה, ומראה את זה משפט רייס) הוא שיש אלגוריתם שמתיימר לדעת את התשובה עבור *כל* האלגוריתמים האפשריים. כלומר, אנחנו לא מתחילים מ-c, אלא דווקא מ-a.
ההוכחה הזאת פשוט דבילית 424577
תוהה • בתשובה לגדי אלכסנדרוביץ' יום ה', 14/12/2006, 20:40
C לא משתנה, C משתמש בA כדי להחליט מה לעשות.

אתה יכול להגיד שהיא לא כריעה, עובדתית כן ניתן לעשות בדיקות כאלה תחת ההנחה המתאימה (שהתוכנה לא פועלת בהתאם לתוצאת הבדיקה). כלומר היא דווקא כן כריעה תחת ההנחה המוקדמת הזאת, וזה בעצם מה שמענין אותנו, מה שמענין אותי זה אם קומפיילר יוכל להגיד לי אם יש בתוכנה שלי לולאה אינסופית או לא, לא מענין אותי שאני יוכל ליצור תוכנות שמשתמשות בתכונה הזאת כדי ליצור בה את ה"באג" שכל פעם שהקומפיילר יגיד כן הם יעשו לא וכל פעם שיגיד לא הן יעשו כן.
ההוכחה הזאת פשוט דבילית 424579
גדי אלכסנדרוביץ' • בתשובה לתוהה יום ה', 14/12/2006, 20:47
אבל שים לב שאם נוקטים בגישה שלך, מדברים על A עוד לפני ש-C נכנס למשחק. אם כך, איך A יכול להשתמש בו? שוב, אני מציע לך לנסות ולכתוב את ההוכחה שלך בצורה מסודרת, ותראה די מהר את הבעיה.

בוודאי שניתן לעשות בדיקות כאלו בפועל. בפועל אין מכונות טיורינג אלא רק תוכנות שרצות על מחשבים סופיים. לא קשה להוכיח שניתן להכריע את בעיית העצירה על כל התוכניות שיש חסם על כמות הזיכרון שבה הן משתמשות - ובעולם האמיתי, אלו כל התוכניות. כמובן שזה עדיין לא אומר שניתן לבצע את הבדיקות הללו ב*יעילות*, אבל על זה ידובר רק במאמר ההמשך, אם יהיה.
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות