Game of Life

משחק החיים, המכונה גם פשוט חיים, הוא אוטומט סלולרי שהמציא המתמטיקאי הבריטי ג'ון הורטון קונווי בשנת 1970.

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

חוקים

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

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

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


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

הנעה על ידי שאלות בלוגיקה מתמטית ובחלקה על ידי עבודה על משחקי סימולציה של Ulam, בין השאר, ג'ון קונווי החל לבצע ניסויים בשנת 1968 עם מגוון כללי אוטומטיים דו-מימדיים סלולריים שונים. [3] המטרה הראשונית של קונווי הייתה להגדיר אוטומט תא מעניין ובלתי ניתן לחיזוי. לפיכך, הוא רצה שכמה תצורות יימשכו זמן רב לפני מותן, תצורות אחרות יימשכו לנצח מבלי לאפשר מחזורים וכו '. זה היה אתגר משמעותי ובעיה פתוחה במשך שנים עד שמומחים לאוטומטים סלולריים הצליחו להוכיח שאכן, משחק החיים של קונווי הודה בתצורה שהייתה חיה במובן של סיפוק שתי הדרישות הכלליות של פון נוימן. בעוד שההגדרות שלפני חייו של קונווי היו מוכווני הוכחה, הבנייה של קונווי כוונה לפשטות מבלי שקודם לכן סיפקה הוכחה שהאוטומט היה חי.

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

1. לא צריך להיות גידול מתפרץ.
2. צריך להתקיים דפוסים ראשוניים קטנים עם תוצאות כאוטיות בלתי צפויות.
3. צריך להיות פוטנציאלי עבור קונסטרוקטורים אוניברסליים של פון נוימן.
4. הכללים צריכים להיות פשוטים ככל האפשר תוך הקפדה על אילוצים לעיל.

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