מה זה אוטומט תאי
אוטומט תאי הוא לוח של משבצות, שכל אחת מהן במצב מסוים (כאן: חיה או מתה), והוא משתנה בצעדים שנקראים דורות. בכל צעד כל המשבצות מתעדכנות בו זמנית לפי אותו כלל, שמסתכל רק על שמונת השכנים שמקיפים כל משבצת.
במשחק החיים אי אפשר לנצח או להפסיד: אתם בוחרים את המצב ההתחלתי והחוקים עושים את השאר. מה שמעניין הוא שמחוקים כל כך פשוטים נולדת התנהגות מורכבת מאוד ובלתי צפויה, ולכן לומדים אותה במתמטיקה, במדעי המחשב ואפילו בביולוגיה.
החוקים, בשפה פשוטה
סופרים את מספר השכנים החיים של כל משבצת (שמונת אלה שמקיפים אותה, כולל האלכסונים) ומפעילים את החוקים האלה בו זמנית בכל הלוח:
- תא חי עם פחות משני שכנים חיים מת מבדידות.
- תא חי עם שניים או שלושה שכנים חיים נשאר חי.
- תא חי עם יותר משלושה שכנים חיים מת מצפיפות יתר.
- משבצת מתה עם בדיוק שלושה שכנים חיים נולדת.
הסימון המקוצר לחוקים האלה הוא B3/S23: B (מהמילה birth, לידה) 3 אומר שנולדים עם 3 שכנים, ו-S (מהמילה survival, הישרדות) 23 אומר ששורדים עם 2 או 3. הכללים החלופיים בכלי משתמשים באותו סימון, למשל HighLife הוא B36/S23 וזרעים הוא B2/S.
דור אחד שמחושב ביד
קחו את המהבהב: שלושה תאים חיים בשורה אופקית. לתא שבאמצע יש 2 שכנים חיים, ולכן הוא שורד. לתאים בקצוות יש שכן אחד בלבד, ולכן הם מתים. למשבצות שממש מעל האמצע וממש מתחתיו יש 3 שכנים חיים (שלושת התאים בשורה), ולכן הן נולדות. התוצאה: שורה אנכית של שלושה תאים.
בדור הבא התהליך חוזר והשורה שוב נעשית אופקית. לכן המהבהב הוא מתנד בעל מחזור 2. נסו אותו דבר עם הבלוק, ריבוע של 2 × 2: לכל תא יש 3 שכנים, ולכן כולם שורדים, ולאף משבצת ריקה אין 3 שכנים חיים. הוא אף פעם לא משתנה, ולכן קוראים לו טבע דומם.
היסטוריה: קונוויי, גרדנר והמגזין
המתמטיקאי הבריטי ג'ון קונוויי המציא את המשחק ב-1970. מרטין גרדנר הפיץ אותו בטור המשחקים המתמטיים שלו ב-Scientific American, בגיליון אוקטובר 1970, ומאז נוצרה קהילה ענקית של חובבים שמחפשים ומקטלגים תבניות.
עם הזמן הוכח שהמשחק שלם טיורינג: עם הצורות הנכונות הוא יכול, באופן עקרוני, לחשב כל מה שמחשב מחשב. זו אחת הסיבות לכך שהוא עדיין מפורסם: מורכבות בלתי מוגבלת מחוקים מינימליים.
משפחות תבניות ואילו לנסות
מסווגים תבניות לפי ההתנהגות שלהן. כולן נמצאות בתפריט «תבנית» בכלי, בשמות האלה:
| משפחה | תבנית | מה היא עושה |
|---|---|---|
| טבע דומם | בלוק (Block), כוורת (Beehive) | אף פעם לא משתנה: 4 תאים בבלוק, 6 בכוורת |
| מתנד | מהבהב (Blinker), קרפדה (Toad), משואה (Beacon) | מחזור 2: חוזרת להתחלה כל 2 דורות |
| מתנד | פולסר (Pulsar) | מחזור 3, 48 תאים בשלב ההתחלתי |
| מתנד | Pentadecathlon | מחזור 15 |
| ספינה | גלשן (Glider) | 5 תאים; מתקדם משבצת אחת באלכסון כל 4 דורות |
| ספינה | ספינה קלה | חוצה את הלוח בקו ישר, מחזור 4 |
| תותח | תותח הגלשנים של גוספר (Gosper) | פולט גלשן חדש כל 30 דורות |
| כאוס התחלתי | R-pentomino | 5 תאים שנדרשים להם 1,103 דורות להתייצב במישור אינסופי |
את תותח גוספר מצא ביל גוספר ב-1970, והוא היה ההוכחה הראשונה לכך שאוכלוסייה יכולה לגדול בלי גבול. מלבד אלה, הכלי כולל את בלוט (Acorn) ו-Diehard, שתי תבניות קטנות שלוקח להן המון זמן להתייצב.
איך משתמשים בכלי משחק החיים
- לחצו או גררו על הלוח כדי לצייר תאים חיים (לחצו שוב על משבצת חיה כדי להסיר אותה), או בחרו תבנית מהתפריט «תבנית».
- לחצו על «התחלה». עם «דור אחד» מתקדמים צעד אחד כדי לעקוב אחרי ההתפתחות ברוגע, ועם «השהיה» עוצרים הכול. אפשר להשתמש גם במקלדת כשהלוח נבחר: רווח מתחיל או משהה, N מקדם צעד, R ממלא באקראי ו-C מנקה.
- כווננו את «מהירות», «גודל הלוח» ו«כלל», ונסו «אקראי» (עם «צפיפות המילוי האקראי») כדי להתחיל עם לוח מלא בתאים. «ניקוי» משאיר את הלוח ריק.
- הפעילו את «צביעה לפי גיל כל תא» כדי לראות אילו אזורים יציבים הכי הרבה זמן. למעלה מוצגים הדור והתאים החיים, והכלי מודיע כשהלוח מתייצב, נכנס למחזור או נשאר בלי חיים.
הכול מחושב במכשיר שלכם ושום דבר לא נשלח לשרת. הכלי שומר בדפדפן את ההגדרות (גודל, מהירות, כלל), אבל לא את הציור.
ניסויים לעשות
- טענו את הגלשן וספרו כמה דורות לוקח לו לזוז משבצת אחת באלכסון: 4. כשהקצוות מחוברים, הוא עושה סיבוב סביב הלוח וחוזר מהצד השני.
- הציבו שני גלשנים במסלול התנגשות וראו איך זה מסתיים: תלוי באופן שבו הם מגיעים, הם יכולים להשמיד זה את זה או להשאיר טבע דומם.
- טענו את תותח גוספר בלוח של לפחות 48 × 48 וספרו כמה זמן לוקח לו לשגר כל גלשן: 30 דורות.
- טענו את ה-R-pentomino בלוח גדול והשוו עם קצוות מחוברים ובלעדיהם. במישור אינסופי הוא מתייצב אחרי 1,103 דורות, אבל בלוח סופי התוצאה משתנה.
- החליפו את הכלל עם אותו ציור. עם זרעים (B2/S) כל תא מת בכל דור ונשארות רק לידות, ולכן הציור מתפשט החוצה; עם מבוך (B3/S12345) מופיעים מבנים דמויי מסדרונות.
מגבלות הלוח הסופי
המשחק המקורי מתרחש במישור אינסופי. הלוח בכלי הוא בגודל קבוע, ולכן מה שמגיע לקצה מתנהג אחרת: כשהקצוות מחוברים הוא נכנס שוב מהצד ההפוך (הלוח הופך למעין סופגנייה), וכשהם לא מחוברים הוא כבה אל מול קיר.
לכן תבניות גדולות צריכות מקום (תותח גוספר דורש לפחות 48 × 48) וחלק מהן, כמו ה-R-pentomino, עלולות להסתיים אחרת ממה שרואים במישור בלתי מוגבל. אם התבנית לא נכנסת, הכלי מבקש לוח גדול יותר.
שאלות נפוצות
מהם החוקים של משחק החיים של קונוויי?
תא חי עם 2 או 3 שכנים חיים נשאר חי; עם פחות מ-2 הוא מת מבדידות ועם יותר מ-3 מצפיפות יתר. משבצת מתה עם בדיוק 3 שכנים חיים נולדת. מסכמים זאת כ-B3/S23.
מה זה B3/S23?
B היא לידה (birth) ו-S היא הישרדות (survival). B3 אומר שנולד תא עם 3 שכנים חיים ו-S23 אומר ששורד תא שיש לו 2 או 3.
מה זה גלשן?
זו צורה של חמישה תאים שנעה באלכסון, משבצת אחת כל 4 דורות. זו התבנית המפורסמת ביותר במשחק.
מי המציא את משחק החיים?
המתמטיקאי הבריטי ג'ון קונוויי, ב-1970. מרטין גרדנר הפיץ אותו באותה שנה במגזין Scientific American.
למה הציור שלי נעלם או נשאר במקום?
זה הדבר הנפוץ ביותר: הרבה צורות קטנות נכחדות או מתייצבות אחרי מעט דורות. נסו נקודת פתיחה אחרת, לוח גדול יותר או «אקראי».