בתשובה לעוזי ו., 28/09/05 20:51
 |
|
 |
||
|
||||
 |
מה דעתך על ההגדרה הזו למרכיב: x הוא מרכיב של y אם הוא איבר של y או איבר של מרכיב של y. בפרט, האם ההגדרה הזו "חזקה יותר" (כלומר, מאפשרת סדרה לא סופית) ואם כן, האם זה רע/לא תואם את מה שדורון מדבר עליו? בקשר ל-1, תוכל להסביר את כיוון המחשבה שלך? אם בונים בצורה פורמלית את כל הקבוצות בעזרת הקבוצה הריקה, נראה לי שהיא כן תהיה מרכיב בכל קבוצה. |
 |
 |
 |
|
|
|
||
|
||||
|
(הדגמה לזה שמתמטיקאים מתחמקים מעיסוק בהגדרות עקרוניות) זו לא הגדרה מוצלחת, כי היא רקורסיבית (אתה מגדיר "מרכיב" במונחי אותו מושג). בהקשרים מסויימים זה רעיון מצוין1, אבל בתור כלל אצבע, הייתי אומר שאפשר להשתמש בהגדרות כאלה רק כשברור שאפשר להסתדר גם בלעדיהן; מצד שני, אם *אפשר* להסתדר בלעדיהן, אז הגדרות רקורסיביות הן כלי מאד מוצלח ואלגנטי. בעצם אתה לא מגדיר את המושג "מרכיב" (רקורסיביות, כאמור), אלא נותן קריטריון, אילו יחסים נחשבים ל"יחסי מרכיבות": "יחס מרכיבות הוא יחס שבו x מתייחס ל- y אם ורק אם הוא איבר של y, או מתייחס לאיבר של y" (כאן אין שום רקורסיביות, כי היחס עומד "מחוץ" להגדרה). כעת אפשר להוכיח שחיתוך של אוסף יחסי מרכיבות גם הוא יחס מרכיבות, ואז אפשר להתבונן ביחס המרכיבות הקטן ביותר. הפלא ופלא - זה היחס "מרכיב" שאני הגדרתי... 1 למשל: הדוגמא הראשונה שהתגלתה לחבורה (נוצרת סופית) עם גידול2 שאיננו פולינומיאלי וגם איננו אקספוננציאלי, נראית בערך כך: זוהי החבורה שנוצרת על-ידי האיברים a,b,c,d, כאשר a=(1,b), b=(c,1), c=(d,d), d=(1,a). 2 חבורה היא הרי אוסף של מכפלות (תמיד סופיות) של ה"יוצרים" שלה, אלא שבדרך כלל יש כפילויות, למשל abab=baba. ב"גידול" הכוונה היא לשאלה כמה מהר גדלה הפונקציה (f(n שסופרת כמה איברים שונים יש מאורך n.
|
|
|
|
|
|
|
||
|
||||
|
לא הבנתי את כלל האצבע. יש כל מיני סדרות שמוגדרות רק ע"י הגדרה רקורסיבית. למשל: A(n) = 3A(n-1) + 1 .... for A(n-1) odd וכאן לא ידועה נוסחא לא רקורסיבית לאיבר ה n . ונניח שיצליחו להוכיח שבסדרה הזו (או סדרה דומה) לא קיימת נוסחא לא רקורסיבית לאיבר ה n. למה זה בעיה?
A(n) = 1/2 * A(n-1) .... for A(n-1) even |
|
|
|
|
|
|
||
|
||||
|
אתה מגדיר את (A(n לפי (A(n-1 - עם זה אין שום בעיה. (דיברתי על הגדרה של מושג או של אובייקט). (דוגמא להגדרה רקורסיבית: "A הוא המספר השלם הקטן ביותר שגדול מ- A/2+3"). |
|
|
|
|
|
|
||
|
||||
|
גם בדוגמא שלך, לא הבנתי למה הרקורסיביות היא בעייתית (אני מבין שזה רק כלל אצבע, אבל בכל זאת). נדמה לי שאפשר לנסח את ההגדרה הרקורסיבית הזו בתור שני אי שיוויונים - ואני לא רואה שום דבר בעייתי במערכת אי שיוויונים, אפילו אם אותו משתנה מופיע בשני האגפים. | |
|
|
|
|
|
||
|
||||
|
מצויין. למה שווה A? | |
|
|
|
|
|
||
|
||||
|
7, לא? אני לא כל כך מצליח לראות את הבעיה שבהגדרה הרקורסיבית שלי שהתחילה את הכל, רק בגלל שיש לה הפניה עצמית. הרי איך "משתמשים" בה? לא אומרים על דברים "זה מרכיב כי בא לי", אלא מסתכלים על הדברים שאנחנו בטוחים במאה אחוזים שהם מרכיב: כל האיברים של y. אחרי שיש לנו את המרכיבים ה"בטוחים" הללו אנחנו בודקים אילו עוד מרכיבים אנחנו מכירים - ועכשיו אנחנו יכולים לקחת את כל האיברים של המרכיבים ה"בטוחים", וכן הלאה וכן הלאה. להבדיל אלף אלפי הבדלות, אם אני זוכר נכון גם ההגדרה של קונווי למספר היא רקורסיבית, וגם הוא מתחיל את הבניה מהמקרה היחיד שבו הוא יודע שמשהו הוא מספר על בטוח - על ידי שימוש בשתי קבוצות ריקות של מספרים. |
|
|
|
|
|
|
||
|
||||
|
אולי 8? (זה באמת המספר השלם הקטן ביותר שגדול מ- 8/2+3). השיפוץ שאתה מציע עכשיו הוא בעצם להגדיר סדרה של יחסים (שייך, שייך לאיבר, שייך לאיבר של איבר, ...) ולהגדיר את "מרכיב" בתור האיחוד שלהם. זה בסדר, ו*לכן* במקרה הזה מותר להשתמש ב"הגדרה" שהצעת. היא באמת יותר אלגנטית (ושוב, אלגנטיות זה קריטריון מצוין, בתנאי שעומדים על קרקע יציבה). גם אצל קונווי, ההגדרה של משחק בתור זוג סדור של קבוצות של משחקים היא בחצי-קריצה. הוא לא היה משתמש בה אלמלא הפיגום של הסודרים שמאפשר להגדיר את כל המשחקים באינדוקציה טרנספיניטית, כאשר משחק מדור i+1 מוגדר בתור זוג סדור של קבוצות מדור קודם (עם הגדרה מתאימה לסודרים שאינם עוקבים). גם כאן, המושג "משחק" אינו בא לעולם עד שהגדרנו "משחק מדור 0", "משחק מדור 1", וכן הלאה. "משחק" *מוגדר* בתור "משחק מאיזשהו דור". |
|
|
|
|
|
|
||
|
||||
|
7/2+3 זה לא שש וחצי, שקטן משבע? שאר הדברים שלך מקובלים עלי, אבל איפה יש הגדרה שהיא רקורסיבית "ממש", בלי בסיס? הרי כבר בכיתה א' מלמדים אותנו שרקורסיה חייבת לבוא עם בסיס. |
|
|
|
|
|
|
||
|
||||
|
בדיוק: 7 הוא המספר השלם הקטן ביותר שגדול מ7/2+3. שים לב גם שאתה שאלת את עוזי (בהקשר של ההגדרה הרקורסיבית של קונוויי) על מספרים והוא ענה לך על משחקים. |
|
|
|
|
|
|
||
|
||||
|
זה בסדר, כי אצל קונווי ההגדרה של ''מספר'' היא מקרה פרטי של ''משחק'', שמוגדר כמו מספר רק עם פחות מגבלות. לך תבין. | |
|
|
|
|
|
||
|
||||
|
זהו, שאין. ''הגדרה רקורסיבית'' זה אוקסימורון, אלא אם היא בת-תיקון, שאז זה קיצור ל''תאור אלגנטי שבא במקום ההגדרה (אותה אפשר להבין מתוך ההקשר)''. | |
|
|
|
|
|
||
|
||||
|
רקורסיה, אם לא נקבע אחרת, מתחילה מפשטות מירבית ופשטות מירבית מוסברת בקצרה בתגובה 333996 |
|
|
|
|
|
|
||
|
||||
|
לא הבנתי למה זה רלוונטי מהו A. אם הייתי מגדיר את A בתור A=A+1 לא היה שום A שעונה על המשוואה - ועדיין אני לא רואה כאן מה הבעיה. |
|
|
|
|
|
|
||
|
||||
|
הבעיה היא שהכביכול-הגדרה הזו משאירה אותנו בחוסר ודאות לגבי A שאותו היא מבקשת להגדיר במדוייק. עוזי הביא את זה כדוגמא לבעייתיות בהגדרות רקורסיביות כמו זו היפה שגדי הציע. | |
|
|
|
|
|
||
|
||||
|
אוקי, הבנתי. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |