בתשובה לגדי אלכסנדרוביץ', 19/06/05 20:21
אפילו יותר פשוטה 310207
אח של אייל • בתשובה לגדי אלכסנדרוביץ' יום ב', 20/6/2005, 0:59
האדם יכול לחרבן ובאופן פשוט למדי (אצל רוב אנשים). לעומת זאת, למכונות טיורינג אין תחת ובפרט אין חור תחת :-).

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

1. בעיית העצירה: תוכנית מספיק ארוכה - אין לבנאדם סיכוי להבין אותה בזמן חייו.
2. בעיית הריצוף: ניתן לקודד צורה כ"כ מורכבת, שאין לבנאדם סיכוי בכלל לקלוט אותה במבט אחד, שלא לדבר על לבדוק האם ניתן לרצף איתה את המישור.
3. בעיית ה post-correspondence : איזשהי שאלה על זוגות של מחרוזות מעל אלף-בית סופי. אבל, הקלט יכול להיות גם מחרוזות ארוכות מאד מאד מאד..

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