משפט גודל
- פותח הנושא atheist22
- פורסם בתאריך
איגור קרסיק
New member
כן
אני מכיר רק טענה 1: השערת הרצף. היא טוענת שלא קיימת עצמה שקטנה ממש מ-c וגדולה ממש מאלף אפס. והוכח לגביה שלא ניתן להוכיח ולהפריך אותה.
אני מכיר רק טענה 1: השערת הרצף. היא טוענת שלא קיימת עצמה שקטנה ממש מ-c וגדולה ממש מאלף אפס. והוכח לגביה שלא ניתן להוכיח ולהפריך אותה.
לא בדיוק...
טיורינג הוכיח שלא ניתן לקבוע א-פריורי (מראש) שטענה היא מסוג הטענות של גדל (אני חושב שקוראים את זה Gedel למרות שכותבים Godel). אם אני לא טועה, הוא הוכיח את זה באמצעות מכונות טיורינג ובעיית העצירה (ניתן להמיר "הוכחה" ב"מכונת טיורינג", אם אני לא טועה). השערת הרצף היא מיוחדת. עד כמה שאני מבין, היא לא מקרה של משפט גדל (וגם לא ניתן למצוא מקרה של משפט גדל - ראה למעלה). פעם שאלתי את איתי הראבן על איך זה מסתדר ומה שהוא ענה לי היה משהו כמו: אהד שלום, בקיצור נמרץ - השערת הרצף אכן אינה תלויה בשאר האקסיומות - וכמובן אין לנו אפשרות לומר שהיא נכונה: אם היינו יודעים שבמובן מסוים השערת הרצף "נכונה" למרות שאינה יכיחה, היינו מצרפים אותה או את הטענות שבזכותן היא נכונה למערכת האקסיומות. זה אינו המצב. בכל מקרה, ה"נכונות" שמדובר עליה היא נכונות במודל מסוים. מציע לך ללמוד על כך בקורס "לוגיקה" ובקורס "תורת הקבוצות". לא תגיע שם ממש לתשובה לשאלה שלך - אך תקבל כלים לחשוב עליה. אף אחד משני הקורסים הללו לא עוסק במודלים של תורת הקבוצות עצמה - תחום זה שייך לקורס מתקדם בתורת הקבוצות, הנקרא לעתים "תורת הקבוצות האקסיומטית". כמדומני שמואל ברגר יכול להדריך קורס קריאה / מתקדם בנושא זה. אך זה אחרי שתלמד את שני הקורסים הללו. ולמעוניינים: בעיית העצירה: (טיפה קשור למדעי המחשב, אבל לא נורא - מדעי המחשב זה תת-תחום של מתמטיקה) הוכח שלא קיים אלגוריתם A שמקבל כקלט אלגוריתם X וקלט עבורו - Y ומחזיר תשובה אם האלגוריתם X עוצר כאשר הוא מקבל את הקלט Y. לדוגמה: האלגוריתם X="בצע לולאה אינסופית" לא יעצור על אף קלט, לכן A(X,Y) = false לכל קלט Y. האלגוריתם X="חבר 1+y" יעצור לכל קלט, לכן A(X,y)=true לכל קלט (מספר) y. כמובן שעבור אלגוריתמים מסובכים החישובים יהיו יותר מסובכים. הפתרון חביב ביותר ודורש "בנייה מחוכמת". אם אף אחד לא יביא פתרון (שלו או שהוא מכיר) אני אשים את הפתרון רק למען השלמות. אהד.
טיורינג הוכיח שלא ניתן לקבוע א-פריורי (מראש) שטענה היא מסוג הטענות של גדל (אני חושב שקוראים את זה Gedel למרות שכותבים Godel). אם אני לא טועה, הוא הוכיח את זה באמצעות מכונות טיורינג ובעיית העצירה (ניתן להמיר "הוכחה" ב"מכונת טיורינג", אם אני לא טועה). השערת הרצף היא מיוחדת. עד כמה שאני מבין, היא לא מקרה של משפט גדל (וגם לא ניתן למצוא מקרה של משפט גדל - ראה למעלה). פעם שאלתי את איתי הראבן על איך זה מסתדר ומה שהוא ענה לי היה משהו כמו: אהד שלום, בקיצור נמרץ - השערת הרצף אכן אינה תלויה בשאר האקסיומות - וכמובן אין לנו אפשרות לומר שהיא נכונה: אם היינו יודעים שבמובן מסוים השערת הרצף "נכונה" למרות שאינה יכיחה, היינו מצרפים אותה או את הטענות שבזכותן היא נכונה למערכת האקסיומות. זה אינו המצב. בכל מקרה, ה"נכונות" שמדובר עליה היא נכונות במודל מסוים. מציע לך ללמוד על כך בקורס "לוגיקה" ובקורס "תורת הקבוצות". לא תגיע שם ממש לתשובה לשאלה שלך - אך תקבל כלים לחשוב עליה. אף אחד משני הקורסים הללו לא עוסק במודלים של תורת הקבוצות עצמה - תחום זה שייך לקורס מתקדם בתורת הקבוצות, הנקרא לעתים "תורת הקבוצות האקסיומטית". כמדומני שמואל ברגר יכול להדריך קורס קריאה / מתקדם בנושא זה. אך זה אחרי שתלמד את שני הקורסים הללו. ולמעוניינים: בעיית העצירה: (טיפה קשור למדעי המחשב, אבל לא נורא - מדעי המחשב זה תת-תחום של מתמטיקה) הוכח שלא קיים אלגוריתם A שמקבל כקלט אלגוריתם X וקלט עבורו - Y ומחזיר תשובה אם האלגוריתם X עוצר כאשר הוא מקבל את הקלט Y. לדוגמה: האלגוריתם X="בצע לולאה אינסופית" לא יעצור על אף קלט, לכן A(X,Y) = false לכל קלט Y. האלגוריתם X="חבר 1+y" יעצור לכל קלט, לכן A(X,y)=true לכל קלט (מספר) y. כמובן שעבור אלגוריתמים מסובכים החישובים יהיו יותר מסובכים. הפתרון חביב ביותר ודורש "בנייה מחוכמת". אם אף אחד לא יביא פתרון (שלו או שהוא מכיר) אני אשים את הפתרון רק למען השלמות. אהד.
נסיון לפתרון (1,2,3,..) ../images/Emo8.gif
נניח בשלילה שאכן קיים אלגוריתם A כנ"ל. נבחר עבורו כקלט את: בתור אלגוריתם קלט X, את A עצמו. כלומר, X=A; בתור קלט לאלגוריתם הקלט, גם כן את A. כלומר, Y=A (מותר וחוקי כי למעשה הקלט של האלג´ A צריך להיות אלגוריתם). לפי ההנחה, A מחזיר תשובה (true\false) עבור הקלטים הנ"ל. מצד שני, כדי ש-A יחזיר תשובה (כלומר יסתיים), הוא צריך להריץ את עצמו אינסוף פעמים (בהתאם לקלטים שבחרנו לו), ולכן לעולם לא יסתיים, ולכן לעולם לא יחזיר תשובה. קיבלנו ש-A מחזיר ולא מחזיר תשובה בו-זמנית! זוהי סתירה, ולכן ההנחה שלנו לא נכונה, ואין אלג´ כזה.
נניח בשלילה שאכן קיים אלגוריתם A כנ"ל. נבחר עבורו כקלט את: בתור אלגוריתם קלט X, את A עצמו. כלומר, X=A; בתור קלט לאלגוריתם הקלט, גם כן את A. כלומר, Y=A (מותר וחוקי כי למעשה הקלט של האלג´ A צריך להיות אלגוריתם). לפי ההנחה, A מחזיר תשובה (true\false) עבור הקלטים הנ"ל. מצד שני, כדי ש-A יחזיר תשובה (כלומר יסתיים), הוא צריך להריץ את עצמו אינסוף פעמים (בהתאם לקלטים שבחרנו לו), ולכן לעולם לא יסתיים, ולכן לעולם לא יחזיר תשובה. קיבלנו ש-A מחזיר ולא מחזיר תשובה בו-זמנית! זוהי סתירה, ולכן ההנחה שלנו לא נכונה, ואין אלג´ כזה.
תגובה
ובכן, אני לא ידעתי שהשערת הרצף אינה מקרה של משפט גדל, כלומר, חשבתי כמו מר קרסיק הנכבד... אני אשמח לקבל טקסט בנושא (אינטרנטי, יהיה נחמד), כי אני לא מכיר את איתי הראבן... לא אומרים gedel וגם לא כותבים godel. הסיפור הוא כזה. זה שם גרמני, שכותבים אותו godel רק עם שתי נקודות מעל הo שעושות את כל ההבדל. איני גרמני, אבל הבנתי שצורת הביטוי הנכונה לתנועה הראשונה בשם היא שילוב בין o לe. נסו להעמיד את הפה\שפתיים\לשון שלכם בעמדה המתאימה להגיד o, ואימרו e. בכל אופן, ישראלים אומרים gedel, כדי להימנע מזה... פתרון בעיית העצירה: אני לא אקלקל לאחרים, למדתי אותו כבר שלוש פעמים (בגרות במדעי המחשב, קורס בחישוביות, קורס בתורת הריקורסיה), אז אני אתן לאחרים
ובכן, אני לא ידעתי שהשערת הרצף אינה מקרה של משפט גדל, כלומר, חשבתי כמו מר קרסיק הנכבד... אני אשמח לקבל טקסט בנושא (אינטרנטי, יהיה נחמד), כי אני לא מכיר את איתי הראבן... לא אומרים gedel וגם לא כותבים godel. הסיפור הוא כזה. זה שם גרמני, שכותבים אותו godel רק עם שתי נקודות מעל הo שעושות את כל ההבדל. איני גרמני, אבל הבנתי שצורת הביטוי הנכונה לתנועה הראשונה בשם היא שילוב בין o לe. נסו להעמיד את הפה\שפתיים\לשון שלכם בעמדה המתאימה להגיד o, ואימרו e. בכל אופן, ישראלים אומרים gedel, כדי להימנע מזה... פתרון בעיית העצירה: אני לא אקלקל לאחרים, למדתי אותו כבר שלוש פעמים (בגרות במדעי המחשב, קורס בחישוביות, קורס בתורת הריקורסיה), אז אני אתן לאחרים
yossibockchil
New member
איך הוגים את שמו של ה-איש (גדל)
שלום רב, לא יכולתי להתעלם מהדיון בדבר הגיית שמו של ה-איש (לפי דעתי בין הגדולים לפחות... וכך גם היסטורית...) קורט גדל, הלוגיקאי האוסטרי. שמו כתוב: Godel כאשר ישנם 2 נקודות אופקיות (כן אפשר להעביר דרכן קו ישר אחד ), מעל ה o הוגים את שמו גא-דל gedel כפי שצויין כאן לא מכבר. זהו , ערב טוב, ואכן דיון מעניין.
שלום רב, לא יכולתי להתעלם מהדיון בדבר הגיית שמו של ה-איש (לפי דעתי בין הגדולים לפחות... וכך גם היסטורית...) קורט גדל, הלוגיקאי האוסטרי. שמו כתוב: Godel כאשר ישנם 2 נקודות אופקיות (כן אפשר להעביר דרכן קו ישר אחד
), מעל ה o הוגים את שמו גא-דל gedel כפי שצויין כאן לא מכבר. זהו , ערב טוב, ואכן דיון מעניין.yossibockchil
New member
רק טעות תיקון... סמנטית
2 נקודות אופיות, כוונתי הייתה ל . . ולא ל : אנכיות (גם המילים אנכיות ואופקיות לא מקומן עם נקודות אלא עם ישרים...אבל... הדבר נעשה רק להמחשה) עמכם הסליחה.
2 נקודות אופיות, כוונתי הייתה ל . . ולא ל : אנכיות (גם המילים אנכיות ואופקיות לא מקומן עם נקודות אלא עם ישרים...אבל... הדבר נעשה רק להמחשה) עמכם הסליחה
.Copyright©1996-2021,Tapuz Media Ltd. Forum software by XenForo® © 2010-2020 XenForo Ltd.