בתשובה לגדי אלכסנדרוביץ', 19/06/05 17:20
 |
|
 |
||
|
||||
 |
קשה. הסתכלתי על בעיות שאינן ניתנות להוכחה או הפרכה ועם כל אחת יש בעיה אחרת שמונעת תרגום שלה לתוכנה. חלק פשוט מסובכות מדי בשבילי :-). חלק אחר בנוי בכוונה בצורה כזו שגם אם המשפט נכון וגם אם הוא שגוי, תוכנה שבודקת אותן לא תעצור - וזו הסיבה שהן לא-כריעות. יש לי הוכחה פשוטה אחרת שמשהו נמצא מעבר ליכולת האנושית - וזה כל מה שהוא ארוך מדי ומסובך מדי בשביל בנאדם להבין במהלך חייו. לדוגמא, האם בספר (הספר הארוך בעולם, שלוקח 2 מיליון שנה לקרוא) מופיע המשפט "אשכים של גרוזיני בבגט". אם אתה טוען שזוהי מגבלה טכנית גרידא, ולא עקרונית, אני מסכים. |
 |
 |
 |
|
|
|
||
|
||||
|
אני מסכים שיש המון דברים שאדם פשוט לא יוכל להתגבר עליהן בימי חייו (בשביל זה מספיקה בעיית העצירה - אני בטוח שיש מספיק תוכנות שלא משנה כמה אדם יעבוד עליהן, הוא לא יספיק להגיע למסקנה אם הן תמיד עוצרות או לא). הבעיה היא שזה לא פוסל את האפשרות שיש דברים פשוטים יחסית שמכונות טיורינג לא יכולות לעשות והאדם כן. אל תבקש ממני לתת אחת כי אין לי מושג, אבל אולי יש אחד כזו ואני פשוט לא מכיר. | |
|
|
|
|
|
||
|
||||
|
האדם יכול לחרבן ובאופן פשוט למדי (אצל רוב אנשים). לעומת זאת, למכונות טיורינג אין תחת ובפרט אין חור תחת :-). אם נסתכל מהכיוון השני, דברים שמכונות טיורינג לא יכולות לעשות נוטים1 להיות בלתי אפשריים גם עבור אדם וזאת מטעמי גודל הקלט. 1. בעיית העצירה: תוכנית מספיק ארוכה - אין לבנאדם סיכוי להבין אותה בזמן חייו. 2. בעיית הריצוף: ניתן לקודד צורה כ"כ מורכבת, שאין לבנאדם סיכוי בכלל לקלוט אותה במבט אחד, שלא לדבר על לבדוק האם ניתן לרצף איתה את המישור. 3. בעיית ה post-correspondence : איזשהי שאלה על זוגות של מחרוזות מעל אלף-בית סופי. אבל, הקלט יכול להיות גם מחרוזות ארוכות מאד מאד מאד.. 1 האמירה "נוטים" היא על סמך בדיקה של מספר דוגמאות קטן מאד. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |