מה לא יכול המחשב לעשות

בתשובה לגדי אלכסנדרוביץ', 14/12/06 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 מאמרים \| כתבו למערכת \| אודות האתר \| טרם התעדכנת \| ארכיון \| חיפוש \| עזרה \| תנאי שימוש	© כל הזכויות שמורות