הגדרה וגודל של מספר גרהם

2024 מְחַבֵּר: Angel Austin | [email protected]. שונה לאחרונה: 2024-01-15 17:24

במילה "אינסוף" לכל אדם יש אסוציאציות משלו. רבים מציירים בדמיונם את הים שמעבר לאופק, בעוד שלאחרים יש תמונה של שמים זרועי כוכבים אינסופיים לנגד עיניהם. מתמטיקאים, שרגילים לפעול עם מספרים, מדמיינים את האינסוף בצורה אחרת לגמרי. במשך מאות שנים הם מנסים למצוא את הכמויות הפיזיות הגדולות ביותר הנדרשות למדידה. אחד מהם הוא מספר גרהם. כמה אפסים יש בו ולמה הוא משמש, מאמר זה יספר.

מספר גדול לאין שיעור

במתמטיקה, זה השם של משתנה כזה x , אם עבור מספר חיובי נתון M אפשר לציין מספר טבעי N כך שלכל המספרים n גדול מ-N אי השוויון |x _{| > M. עם זאת, לא, למשל, ניתן להתייחס למספר שלם Z גדול לאין שיעור, מכיוון שהוא תמיד יהיה קטן מ-(Z + 1).}

כמה מילים על "ענקים"

המספרים הגדולים ביותר שיש להם משמעות פיזית נחשבים:

• 1080. מספר זה, אשר נהוג לכנותו quinquavigintillion, משמש לציון המספר המשוער של קווארקים ולפטונים (החלקיקים הקטנים ביותר) ביקום.
• 1 Google. מספר כזה במערכת העשרונית נכתב כיחידה עם 100 אפסים. על פי כמה מודלים מתמטיים, מזמן המפץ הגדול ועד פיצוץ החור השחור המסיבי ביותר, אמורות לעבור בין 1 ל-1.5 שנות גוגול, שלאחריהן יעבור היקום שלנו לשלב האחרון של קיומו, כלומר, אנו יכולים נניח שלמספר הזה יש משמעות פיזית מסוימת.
• 8, 5 x 10¹⁸⁵. הקבוע של פלאנק הוא 1.616199 x 10^-35 m, כלומר בסימון עשרוני זה נראה כמו 0.0000000000000000000000000000000616199 מ'. יש בערך 1 של אורך גוגול פלאנק באינץ'. ההערכה היא שאורכים של כ-8.5 x 10^{185 Planck יכולים להתאים לכל היקום שלנו.}
• 2^{77 232 917} – 1. זהו המספר הראשוני הגדול ביותר הידוע. אם לסימון הבינארי שלו יש צורה קומפקטית למדי, אז כדי לתאר אותו בצורה עשרונית, הוא ייקח לא פחות מ-13 מיליון תווים. הוא נמצא ב-2017 כחלק מפרויקט לחיפוש מספרי מרסן. אם חובבים ימשיכו לעבוד בכיוון זה, אז ברמת הפיתוח הנוכחית של טכנולוגיית המחשב, בעתיד הקרוב לא סביר שהם יוכלו למצוא מספר מרסן בסדר גודל גדול מ-2^{77 232 917- 1, אם כי כזההזוכה המאושר יקבל 150,000 דולר ארה"ב.}
• Hugoplex. כאן אנחנו פשוט לוקחים 1 ומוסיפים אחריו אפסים בכמות של 1 googol. אתה יכול לכתוב את המספר הזה בתור 10^10^100. אי אפשר לייצג את זה בצורה עשרונית, כי אם כל החלל של היקום מלא בפיסות נייר, שעל כל אחת מהן ייכתב 0 עם גודל גופן "Word" של 10, אז במקרה זה רק מחצית כל ה-0 אחרי 1 יתקבלו עבור מספר הגוגולפלקס.
• 10^10^10^10^10^1.1. זהו מספר המראה את מספר השנים שאחריהם, לפי משפט פואנקרה, היקום שלנו, כתוצאה מתנודות קוונטיות אקראיות, יחזור למצב הקרוב להיום.

איך הגיעו המספרים של גרהם

בשנת 1977 פרסם הפופולארי הידוע של המדע מרטין גרדנר מאמר ב-Scientific American בנוגע להוכחתו של גרהם לאחת הבעיות של התיאוריה של ראמז. בו, הוא כינה את הגבול שקבע המדען המספר הגדול ביותר שאי פעם נעשה בו שימוש בהיגיון מתמטי רציני.

מי זה רונלד לואיס גרהם

המדען, כיום בשנות ה-80 לחייו, נולד בקליפורניה. ב-1962 קיבל תואר דוקטור במתמטיקה מאוניברסיטת ברקלי. הוא עבד ב-Bell Labs במשך 37 שנים ולאחר מכן עבר ל-AT&T Labs. המדען שיתף פעולה באופן פעיל עם אחד מגדולי המתמטיקאים של המאה ה-20, Pal Erdős, והוא זוכה בפרסים יוקרתיים רבים. הביבליוגרפיה המדעית של גרהם מכילה יותר מ-320 מאמרים מדעיים.

באמצע שנות ה-70, המדען התעניין בבעיה הקשורה לתיאוריהרמזי. בהוכחתו, נקבע הגבול העליון של הפתרון, שהוא מספר גדול מאוד, שנקרא לאחר מכן על שמו של רונלד גרהם.

בעיית היפרקוביות

כדי להבין את המהות של מספר גרהם, תחילה עליך להבין כיצד הוא הושג.

המדען ועמיתו ברוס רוטשילד פתרו את הבעיה הבאה:

יש היפרקוביית n-ממדית. כל זוגות הקודקודים שלו מחוברים בצורה כזו שמתקבל גרף שלם עם 2קודקודים. כל אחד מהקצוות שלו בצבע כחול או אדום. נדרש למצוא את המספר המינימלי של קודקודים שייפרקוביה צריכה להיות כך שכל צביעה כזו תכיל תת-גרף מונוכרומטי שלם עם 4 קודקודים השוכבים באותו מישור.

Decision

גרהם ורוטשילד הוכיחו שלבעיה יש פתרון N' העומד בתנאי 6 ⩽ N' ⩽N שבו N הוא מספר מוגדר היטב, גדול מאוד.

הגבול התחתון של N שוכלל לאחר מכן על ידי מדענים אחרים, שהוכיחו ש-N חייב להיות גדול מ-13 או שווה ל-13. כך, הביטוי עבור המספר הקטן ביותר של קודקודים של היפרקוביה העומד בתנאים שהוצגו לעיל הפך 13 ⩽ N'⩽ N.

סימון החץ של Knoth

לפני הגדרת מספר גרהם, עליך להכיר את שיטת הייצוג הסמלי שלו, שכן לא תווי עשרוני או בינארי מתאים לחלוטין לכך.

כיום, סימון החץ של Knuth משמש לייצוג כמות זו. לדבריה:

ab="חץ למעלה" ב.

לפעולה של אקספונציה מרובה, הערך הוצג:

a "חץ למעלה" "חץ למעלה" b=ab="מגדל המורכב מ-a בכמות של b חלקים."

ולפניה, כלומר ייעוד סמלי של הרחקה חוזרת ונשנית של האופרטור הקודם, Knuth כבר השתמש ב-3 חצים.

בשימוש בסימון זה עבור מספר גרהם, יש לנו רצפי "חץ" מקוננים זה בזה, בכמות של 64 יח'.

סולם

המספר המפורסם שלהם, שמלהיב את הדמיון ומרחיב את גבולות התודעה האנושית, מוציא אותה אל מעבר לגבולות היקום, גרהם ועמיתיו השיגו אותו כגבול עליון למספר N בהוכחת ההיפרקוביה בעיה שהוצגה לעיל. קשה מאוד לאדם רגיל לדמיין כמה גדול קנה המידה שלו.

שאלת מספר התווים, או כפי שנאמר לפעמים בטעות, אפסים במספר של גרהם, מעניינת כמעט את כל מי ששומע על הערך הזה בפעם הראשונה.

די לומר שיש לנו עסק ברצף שצומח במהירות המורכב מ-64 חברים. אפילו את המונח הראשון שלו אי אפשר לדמיין, מכיוון שהוא מורכב מ-n "מגדלים", המורכבים מ-3-to. כבר "הקומה התחתונה" שלה של 3 משולשות שווה ל-7,625,597,484,987, כלומר היא עולה על 7 מיליארד, כלומר על הקומה ה-64 (לא חבר!). לפיכך, כרגע אי אפשר לומר בדיוק מהו מספר גרהם, שכן לא מספיק לחשב אותו.הכוח המשולב של כל המחשבים הקיימים על פני כדור הארץ היום.

שיא נשבר?

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

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

מאוחר יותר, הארווי פרידמן צמצם במידת מה את הבעיה הזו על ידי התחשבות רק בגרפים (עצים) א-ציקליים כאלה שעבור אחד מסוים עם מקדם i יש לכל היותר (i + k) קודקודים. הוא החליט לברר מה צריך להיות מספר הגרפים הא-ציקליים, כדי שבשיטה זו של משימתם יהיה אפשר תמיד למצוא תת-עץ שיוטמע בעץ אחר.

כתוצאה ממחקר בנושא זה, נמצא ש-N, בהתאם ל-k, גדל במהירות אדירה. בפרט, אם k=1, אז N=3. עם זאת, ב-k=2, N כבר מגיע ל-11. הדבר המעניין ביותר מתחיל כאשר k=3. במקרה זה, N "ממריא" במהירות ומגיע לערך ש גדול פי כמה ממספר גרהם. כדי לדמיין כמה הוא גדול, מספיק לרשום את המספר שחישב על ידי רונלד גרהם בצורה של G64 (3). אז הערך של פרידמן-קרוסקאל (הכובד FinKraskal(3)), יהיה בסדר גודל של G(G(187196)). במילים אחרות, מתקבל מגה-ערך, שהוא גדול לאין שיעורמספר גרהם גדול בצורה בלתי נתפסת. יחד עם זאת, אפילו זה יהיה פחות מאינסוף במספר עצום של פעמים. הגיוני לדבר על המושג הזה ביתר פירוט.

Infinity

עכשיו, לאחר שהסברנו מהו מספר גרהם על האצבעות, עלינו להבין את המשמעות שהושקעה ומושקעת במושג פילוסופי זה. אחרי הכל, "אינסוף" ו"מספר גדול לאין שיעור" יכולים להיחשב זהים בהקשר מסוים.

התרומה הגדולה ביותר לחקר סוגיה זו נעשתה על ידי אריסטו. ההוגה הדגול של העת העתיקה חילק את האינסוף לפוטנציאל וממשי. באחרון הוא התכוון למציאות קיומם של דברים אינסופיים.

לפי אריסטו, מקורות הרעיונות לגבי מושג יסוד זה הם:

• time;
• הפרדת ערכים;
• מושג הגבול וקיומו של משהו מעבר לו;
• הבלתי נדלה של הטבע היצירתי;
• לחשוב שאין לו גבולות.

בפירוש המודרני של אינסוף, לא ניתן לציין מידה כמותית, כך שהחיפוש אחר המספר הגדול ביותר יכול להימשך לנצח.

מסקנה

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

כמו כן, אין לו מאפיינים של מספר אינסופי, כגון:

• ∞ + 1=∞;
• יש מספר אינסופי של מספרים אי-זוגיים וזוגיים;
• ∞ - 1=∞;
• מספר המספרים האי-זוגיים הוא בדיוק מחצית מכל המספרים;
• ∞ + ∞=∞;
• ∞/2=∞.

לסיכום: המספר של גרהם הוא המספר הגדול ביותר בתרגול של הוכחה מתמטית, לפי ספר השיאים של גינס. עם זאת, ישנם מספרים הגדולים פי כמה מהערך הזה.

ככל הנראה, בעתיד יהיה צורך ב"ענקים" גדולים עוד יותר, במיוחד אם אדם חורג ממערכת השמש שלנו או ממציא משהו בלתי נתפס ברמה הנוכחית של התודעה שלנו.