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

בתשובה לתוהה, 14/12/06 17:45

לא דבילית בכלל.

424547

צבי • בתשובה לתוהה

יום ה', 14/12/2006, 18:23

ההוכחה מראה שלא קיים אלגוריתם שבהינתן אלגוריתם כקלט יקבע נכונה האם אלגוריתם הקלט עוצר. כדי להראות זאת מספיק לתת דוגמה אחת.

תנסה להפעיל את המוח קצת לשם שינוי

424549

תוהה • בתשובה לצבי

יום ה', 14/12/2006, 18:30

בהנחה שהאלגוריתם אותו בודקים לא יכול להשתמש בתוצאת האלגוריתם שבודק אותו כדי לשנות את ההתנהגות הזאת ההוכחה הזאת לא שווה כלום.

כלומר אין הוכחה שאי אפשר לבנות אלגוריתם שיבדוק אם אלגוריתם אחר יעצור בהנחה שהאלגוריתם האחר לא יכול להשתמש באלגוריתם שבודק אותו (שזה בעצם מה שמענין והשאר זה סתם משחק בלוגיקה ברמה של ילדים בכיתה ו')

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

המאמר המלא

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