בתשובה לעדי סתיו, 14/12/06 20:38
ההוכחה הזאת פשוט דבילית 424581
גדי אלכסנדרוביץ' • בתשובה לעדי סתיו יום ה', 14/12/2006, 20:52
הקומפיילר לא יכול להזהיר מפני זה, אבל זה לא בגלל בעיית העצירה - זה בגלל שהוא לא יודע מה הקלט.

מה שכן, תיאורטית הוא כן יכול לעשות את זה, אם מניחים שגודל הקלט לתוכנית חסום, אבל אני לא רואה דרך יעילה לעשות את זה במקרה הכללי יותר מאשר להריץ את התוכנית על כל הקלטים האפשריים.
ההוכחה הזאת פשוט דבילית 424585
עדי סתיו • בתשובה לגדי אלכסנדרוביץ' יום ה', 14/12/2006, 21:14
גם אם הוא יודע מה הקלט. כל עוד התוכנית לא עוצרת, יכול להיות שבאיטרציה הבאה פתאום היא כן תשתמש במשתנה סוף-סוף.
ההוכחה הזאת פשוט דבילית 424587
גדי אלכסנדרוביץ' • בתשובה לעדי סתיו יום ה', 14/12/2006, 21:21
נכון, אבל חשבתי שיש הסכמה ש''בעולם האמיתי'' תמיד אפשר לדעת אם תוכנית עוצרת או לא (כל עוד לא אכפת לנו מאיכות הביצועים של הקומפיילר - מה שהופך את כל זה למאוד לא אמיתי, כמובן).
ההוכחה הזאת פשוט דבילית 424594
עדי סתיו • בתשובה לגדי אלכסנדרוביץ' יום ה', 14/12/2006, 22:35
תלוי מה זה ''בעולם האמיתי'', זאת-אומרת באיזה סוג תוכנית מדובר. תוכנות שמבצעות חישובים מורכבים דומות למודל שלנו. אצל הרבה שרתים, למשל, הקלט ממילא אינסופי, וצריך לטעון שהתכונה עובדת עבור כל קלט.
ההוכחה הזאת פשוט דבילית 424597
גדי אלכסנדרוביץ' • בתשובה לעדי סתיו יום ה', 14/12/2006, 22:37
תחת מגבלות הגיוניות (הקצב שבו התוכנה מסוגלת לקלוט מידע הוא מיליארד ג'יגה-בייט לשנייה; אנו מניחים שהתוכנה תרוץ לכל היותר מיליארד שנים) מקבלים חסם למספר הקלטים.

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