השערת קולאץ
בלוגיקה מדברים על השערת הרצף. למי שלא מכיר עוצמות, הטיעון מההתחלה ובקצרה עובד בערך ככה: יש אין סוף מספרים שלמים, נכון? אבל אם נתחיל לספור אותם, אפשר לספור ועם מספיק זמן (אין סוף ממנו) נוכל לספר את כולם בלי לפספס. לקבוצת המספרים השלמים (וגם הטבעיים) יש גודל אין סופי בן מנייה ולכן עוצמה שנקראת “אלף-אפס”.
ואז, כמה מספרים ממשיים יש? ממשיים זה השלמים והשברים והעשרוניים וכולם חוץ מהמדומים. גם מהם יש אין סוף. אבל אם תנסו לספור אותם, על כל צעד שתעשו, אפשר למצוא את מי פיספסתם. אי אפשר למנות אותם. לקבוצת הממשיים יש גודל אין סופי שאינו בן מנייה ולכן עוצמה שנקרא “2 בחזקת אלף-אפס” או פשוט “אלף”.
השערת הרצף אומרת שאין עוד עוצמה בין אלף-אפס לאלף, שאם קבוצה גדולה ממש מקבוצה בעוצמת אלף אפס אז היא בעוצמה של אלף או יותר. אבל זאת רק השערה ועדיין לא הוכיחו או הפריכו אותה.
בואו לא נשבור את הראש ונדבר על השערה אחרת: השערת קולאץ.
בחרו במספר שלם גדול מאפס ותתחילו לעבוד עליו לפי השלבים הבאים:
— אם הוא זוגי, חלקו אותו בשתיים.
— אם הוא אי זוגי, הכפילו אותו בשלוש והוסיפו אחד.
ההשערה היא שמכל מספר שבחרנו בהתחלה אפשר להגיע בסוף לאחד, או שכל הדרכים בסוף מובילות לאחד.
אחד בשם פול ארדוס אמר ש”המתמטיקה עדיין אינה מוכנה לשאות כאלו מבלבלות, מטרידות וקשות” וגם הציע פרס כספי מרשים תמורת מי שפותר את הבעיה.
שני חוקרים אחרים מצאו לפני כמה שנים שגרסה יותר כללית של הבעיה הזאת אינה ניתנת להכרעה (שאי אפשר לבנות אלגוריתם פתירה שתמיד יביא לאותו פתרון).
כשהראיתי את זה היום לחבר הוא טען שהוא יכול להוכיח את זה באינדוקציה. מי רוצה להריץ כמה ניסויים?
Posted in Memes and Stuff, No Category, Philosophy, Thinking Out Loud by Eran with 6 comments.
Comments
Pingbacks & Trackbacks
-
[…] לבדוק את זה וכי רציתי בעצמי לבדוק כמה מסובך יהיה לכתוב דבר כזה ב-Prolog (ממש לא מסובך, בדיוק כמו שחשבתי), אז כתבתי פרדיקט […]
2501=>7504=>3752=>1876=>938=>469=>1408=>704=>352=>176=>88=>
44=>22=>11=>34=>17=>52=>26=>13=>40=>20=>10=>5=>16=>8=>4=>
2=>1 :)
511654=> 255827=> 767482=> 383741=> 1151224=> 575612=> 287806=> 143903=> 431710=> 215855=> 647566=> 323783=> 971350=> 485675=> 1456026=> 728513=> 2185540=> 1092770=> 546385=> 1639156=> 819578=> 409789=> 1229368=> 614684=> 307342=> 153671=> 461014=> 230507=> 691522=> 345761=> 1037284=> 518642=> 259321=> 777964=> 388982=> 194491=> 583474=> 291737=> 875212=> 437606=> 218803=> 656410=> 328205=> 984616=> 492308=> 246154=> 123077=> 369232=> 184616=> 92308=> 46154=> 23077=> 69232=> 34616=> 17308=> 8654=> 4327=> 12982=> 6491=> 19474=> 9737=> 29212=> 14606=> 7303=> 21910=> 10955=> 32866=> 16433=> 49300=> 24650=> 12325=> 36976=> 18488=> 9244=> 4622=> 2311=> 6934=> 3467=> 10402=> 5201=> 15604=> 7802=> 3901=> 11704=> 5852=> 2926=> 1463=> 4390=> 2195=> 6586=> 3293=> 9880=> 4940=> 2470=> 1235=> 3706=> 1853=> 5560=> 2780=> 1390=> 695=> 2086=> 1043=> 3130=> 1565=> 4696=> 2348=> 1174=> 587=> 1762=> 881=> 2644=> 1322=> 661=> 1984=> 992=> 496=> 248=> 124=> 62=> 31=> 94=> 47=> 142=> 71=> 214=> 107=> 322=> 161=> 484=> 242=> 121=> 364=> 182=> 91=> 274=> 137=> 412=> 206=> 103=> 310=> 155=> 466=> 233=> 700=> 350=> 175=> 526=> 263=> 790=> 395=> 1186=> 593=> 1780=> 890=> 445=> 1336=> 668=> 334=> 167=> 502=> 251=> 754=> 377=> 1132=> 566=> 283=> 850=> 425=> 1276=> 638=> 319=> 958=> 479=> 1438=> 719=> 2158=> 1079=> 3238=> 1619=> 4858=> 2429=> 7288=> 3644=> 1822=> 911=> 2734=> 1367=> 4102=> 2051=> 6154=> 3077=> 9232=> 4616=> 2308=> 1154=> 577=> 1732=> 866=> 433=> 1300=> 650=> 325=> 976=> 488=> 244=> 122=> 61=> 184=> 92=> הצילו זה כבר 200 מהלכים! => 46=> 23=> 70=> 35=> 106=> 53=> 160=> 80=> 40=> 20=> 10=> 5=> 16=> 8=> 4=> 2=> 1 :)
למה?
למה זה טוב?
מה עושים עם זה?
איך זה משפר את איכות החיים היקום וכל השאר?
למה זה נחשב יותר חשוב בחיים ממשחק שש בש למשל?
למה מי שבוחר לבזבז\להשקיע את הזמן על להמציא את הדבר הזה נחשב יותר בחברה מאשר מי שיכול להוביל raid של 40 איש בWOW בהצלחה?
הצלחת להוכיח שמתמטיקה היא משחק בעל קשר חלש יותר למציאות מאשר שש בש או wow…
אני לא מכיר את החבר שלך, אבל אתה יכול להגיד לו שהוא טועה – אי אפשר להוכיח את זה באינדוקציה מכיוון שהאלגוריתם אינו יציב.
טוב, מצאתי את זה דרך Futility Closet…
למען האמת, קורט גדל ופול כהן הראו שלא ניתן להוכיח (או להפריך) את השערת הרצף, מהאקסיומות הסטנדרטיות של תורת הקבוצות.