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

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

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

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