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

מה שכן, תיאורטית הוא כן יכול לעשות את זה, אם מניחים שגודל הקלט לתוכנית חסום, אבל אני לא רואה דרך יעילה לעשות את זה במקרה הכללי יותר מאשר להריץ את התוכנית על כל הקלטים האפשריים.
ההוכחה הזאת פשוט דבילית 424585
גם אם הוא יודע מה הקלט. כל עוד התוכנית לא עוצרת, יכול להיות שבאיטרציה הבאה פתאום היא כן תשתמש במשתנה סוף-סוף.
ההוכחה הזאת פשוט דבילית 424587
נכון, אבל חשבתי שיש הסכמה ש''בעולם האמיתי'' תמיד אפשר לדעת אם תוכנית עוצרת או לא (כל עוד לא אכפת לנו מאיכות הביצועים של הקומפיילר - מה שהופך את כל זה למאוד לא אמיתי, כמובן).
ההוכחה הזאת פשוט דבילית 424594
תלוי מה זה ''בעולם האמיתי'', זאת-אומרת באיזה סוג תוכנית מדובר. תוכנות שמבצעות חישובים מורכבים דומות למודל שלנו. אצל הרבה שרתים, למשל, הקלט ממילא אינסופי, וצריך לטעון שהתכונה עובדת עבור כל קלט.
ההוכחה הזאת פשוט דבילית 424597
תחת מגבלות הגיוניות (הקצב שבו התוכנה מסוגלת לקלוט מידע הוא מיליארד ג'יגה-בייט לשנייה; אנו מניחים שהתוכנה תרוץ לכל היותר מיליארד שנים) מקבלים חסם למספר הקלטים.

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

חזרה לעמוד הראשי המאמר המלא

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים