'משחק החיים' של מתמטיקה חושף דפוסים שחוזרים על עצמם מזמן | מגזין קוונטה

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

1. לידה: תא מת עם שלושה שכנים חיים בדיוק הופך לחיים.
2. הישרדות: תא חי עם שניים או שלושה שכנים חיים נשאר בחיים.
3. מוות: תא חי עם פחות משניים או יותר משלושה שכנים חיים מת.

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

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

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

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

לאורך שנות ה-1970, מתמטיקאים וחובבים מילאו את התקופות הקצרות האחרות ומצאו מעט ארוכות יותר. בסופו של דבר, מתמטיקאים גילו דרך שיטתית לבנות מתנדים ארוכי תקופה. אבל מתנדים עם תקופות בין 15 ל-43 הוכיחו שקשה למצוא. "אנשים מנסים להבין את האמצע במשך שנים", אמר מאיה קרפוביץ', סטודנט לתואר שני באוניברסיטת מרילנד. מילוי החסר אילץ את החוקרים לחלום על שלל טכניקות חדשות שדחפו את הגבולות של מה שנחשב אפשרי עם אוטומטים סלולריים, כפי שמתמטיקאים מכנים רשתות מתפתחות כמו החיים.

כעת הכריזו קרפוביץ' ושישה מחברים שותפים ב-א הדפסה מוקדמת של דצמבר שהם מצאו את שתי התקופות החסרות האחרונות: 19 ו-41. עם הפערים האלה ממולאים, החיים ידועים כעת כ"אומני-מחזוריים" - שם מספר שלם חיובי, וקיים דפוס שחוזר על עצמו לאחר כל כך הרבה שלבים.

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

ניתן למצוא מתנדים עם תקופות קצרות מ-15 באופן ידני או עם אלגוריתמים ראשוניים המחפשים מתנדים תא אחד בכל פעם. אבל ככל שהתקופה גדלה, כך גם המורכבות גדלה, מה שהופך חיפושים בכוח גס להרבה פחות יעילים. "לתקופות קטנות, אתה יכול לחפש ישירות", אמר מתיאס מרזניץ', מחבר שותף במאמר החדש שגילה את מתנד period-31 הראשון ב-2010. "אבל אתה לא באמת יכול ללכת מעבר לזה. אתה לא יכול פשוט לבחור תקופה ולחפש אותה". (מרזניץ' קיבל את הדוקטורט שלו במתמטיקה מאוניברסיטת אורגון סטייט בשנת 2021, אך כיום עובד בחווה.)

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

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

עד תחילת המאה ה-21, רק תריסר תקופות עדיין היו יוצאות דופן. "נראה היה אפשרי מאוד לפתור את הבעיה הזו", אמר מרזניץ'. בשנת 2013, תגלית חדשה בשם לולאת Snark השתפרה על הטכניקה של בקינגהאם משנת 1996 והורידה את הסף שמעליו קל לבנות מתנדים מ-61 ל-43. זה הותיר רק חמש תקופות חסרות. אחד נוסף התגלה ב-2019, ועוד שניים ב-2022, ונותרו רק 19 ו-41 - שניהם ראשוניים. "פריימים קשים יותר מכיוון שאי אפשר להשתמש במתנדים בעלי תקופה קטנה כדי לבנות אותם", אמר מרזניץ'.

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

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

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

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

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

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

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

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