בתשובה לגדי אלכסנדרוביץ', 19/06/05 16:45
אפילו יותר פשוטה 310095
תגובה 310021
אפילו יותר פשוטה 310099
ראיתי, לא שוכנעתי. טרם הוכיחו שהשערת גולדבך אינה ניתנת להוכחה או להפרכה, וזה ש''רבים וטובים ניסו ולא הצליחו'' לא אומר שזה מעבר ליכולת בני האדם - גם עם משפט פרמה הסתבכנו. כמובן, אני מקבל את האפשרות שיש המון משפטים שלא ניתנים להוכחה או להפרכה במערכת אקסיומות מסויימת - אתה מוזמן להביא לי אחד ולהסביר לי איך בנוייה התוכנה שלא ניתן לדעת אם תעצור או לא.
אפילו יותר פשוטה 310145
קשה. הסתכלתי על בעיות שאינן ניתנות להוכחה או הפרכה ועם כל אחת יש בעיה אחרת שמונעת תרגום שלה לתוכנה.
חלק פשוט מסובכות מדי בשבילי :-). חלק אחר בנוי בכוונה בצורה כזו שגם אם המשפט נכון וגם אם הוא שגוי, תוכנה שבודקת אותן לא תעצור - וזו הסיבה שהן לא-כריעות.

יש לי הוכחה פשוטה אחרת שמשהו נמצא מעבר ליכולת האנושית - וזה כל מה שהוא ארוך מדי ומסובך מדי בשביל בנאדם להבין במהלך חייו. לדוגמא, האם בספר (הספר הארוך בעולם, שלוקח 2 מיליון שנה לקרוא) מופיע המשפט "אשכים של גרוזיני בבגט". אם אתה טוען שזוהי מגבלה טכנית גרידא, ולא עקרונית, אני מסכים.
אפילו יותר פשוטה 310149
אני מסכים שיש המון דברים שאדם פשוט לא יוכל להתגבר עליהן בימי חייו (בשביל זה מספיקה בעיית העצירה - אני בטוח שיש מספיק תוכנות שלא משנה כמה אדם יעבוד עליהן, הוא לא יספיק להגיע למסקנה אם הן תמיד עוצרות או לא). הבעיה היא שזה לא פוסל את האפשרות שיש דברים פשוטים יחסית שמכונות טיורינג לא יכולות לעשות והאדם כן. אל תבקש ממני לתת אחת כי אין לי מושג, אבל אולי יש אחד כזו ואני פשוט לא מכיר.
אפילו יותר פשוטה 310207
האדם יכול לחרבן ובאופן פשוט למדי (אצל רוב אנשים). לעומת זאת, למכונות טיורינג אין תחת ובפרט אין חור תחת :-).

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

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

1 האמירה "נוטים" היא על סמך בדיקה של מספר דוגמאות קטן מאד.

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

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים