אוטומט תאי

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

הקדמה ורקע היסטורי

המצאת המחשב המודרני, באמצע המאה ה-20 אפשרה ביצוע סימולציות המדמות תופעות טבע שונות, בפיזיקה, בכימיה ולמעשה לכל רוחב מדעי הטבע. בבנייה של סימולציות, הדגש נמצא לרוב על בנייה של סימולציה הקרובה ככל הניתן למציאות, כך שניתן בעזרתה לקבל תוצאות כמותיות.  על שאלות כמותיות רבות ניתן לקבל תשובות טובות בעזרת סימולציות, כגון "האם ירד גשם מחר?", "איפה בדיוק יימצא כדור-הארץ בעוד 10 שנים?" וכדומה. לעומת זאת ישנה גישה הפוכה השואלת: מה המודל הפשוט ביותר שיכול לשחזר התנהגויות הנראות בטבע? במודלים אלו הדגש הוא על שחזור של התנהגויות איכותיות, ולא כמותיות, והרעיון הוא לגלות בעזרתם מהם הגורמים החשובים ביותר המאפשרים את ההתנהגויות הנצפות בטבע. מודלים כאלו נמצאו שימושיים למגוון רחב של תחומים כגון חקר תופעות המדבור, חקר מערכות אבולוציוניות ועוד. מחקרים אלו גם העלו את השאלה הבסיסית של איך מתנהגים האוטומטים התאיים הפשוטים ביותר (מבלי לקשר אותם למערכות הקיימות בטבע).  
המצאת האוטומט התאי הראשון מיוחסת למתמטיקאים ג'ון פון נוימן וסטניסלב אולם. פון נוימן, אחד המתמטיקאים החשובים של המאה הידוע בעיקר בזכות יצירת תורת המשחקים, ניסה  בשנות ה-40 של המאה ה-20 לבנות רובוטים המסוגלים לשכפל את עצמם. כאשר נתקל בקשיים רבים בפיתוח רעיון זה, הציע לו סטניסלב אולם להשתמש למטרה זו במודל מתמטי אבסטרקטי, של לוח משבצות, בדומה למאמצים שעשה אולם בחקר גדילה של גבישים. פון נוימן אכן הצליח לבנות אוטומט תאי, שבו כל משבצת יכולה להימצא באחד מ-29 מצבים. באוטומט שיצר קיים יצור שעם הזמן יוצר אין סוף עותקים של עצמו.  
המדען הראשון להפעיל סימולציה של אוטומט תאי על מחשב היה המתמטיקאי הנורווגי נילס אלס בריצ'לי ( Nils Aall Barricelli) בריצ'לי הוזמן על ידי פון נוימן בשנת 1953 לפרינסטון על מנת לעבוד על מחשב האניאק (אחד המחשבים הראשונים שנבנו, נבנה על ידי פון נוימן כחלק מפרויקט הגרעין האמריקאי במלחמת העולם השנייה).  בריצ'לי הריץ תוכנות מחשב המפתחות מצבים פשוטים בחיפוש אחר 'חיים מלאכותיים'.  
בשנת 1970 המציא המתמטיקאי ג'ון קונויי את האוטומט התאי המפורסם ביותר, לו קרא משחק החיים. משחק החיים זכה לפופולריות רבה מאוד בקרב מתמטיקאים, מתכנתים וחובבי שעשועי מתמטיקה, במידה רבה בזכות סדרת מאמרים מאת מרטין גרדנר אודותם, שפורסמה בירחון Scientific American. בין השאר התגלו באוטומט זה צורות המראות התנהגויות מורכבות ומענינות (כפי שיודגם בפיסקה הבאה), התגלה שהאוטומט שקול למכונת טיורינג, כלומר כל חישוב שניתן לבצע על מחשב כלשהו ניתן לביצוע בעזרת משחק החיים, ובנוסף הועלו השערות בקשר לשאלה האם אכן ניתן לייצר חיים, והאם ניתן לייצר יצורים חושבים בעזרת המשחק.
דחיפה נוספת לאוטומטים תאיים באה בזכות עבודותיו של סטיבן וולפרם. וולפרם פרסם בתחילת שנות ה-80 סדרה של מאמרים שבה הוא חקר אוטומטים תאיים חד-ממדיים, והראה שלמרות פשטותם הם מראים התנהגויות מורכבות. על מנת לחקור אוטומטים אלו הוא פיתח את תוכנת המחשב Mathematica שזכתה להצלחה מסחרית רבה. ההצלחה המסחרית של התוכנה ביססה אותו כלכלית וניתקה אותו מהצורך לנהל חיים אקדמיים רגילים. מסיבה זו לא פרסם באופן סדיר את תוצאות מחקריו הנמשכים אודות אוטומטים תאיים, אלא אגר אותן ולבסוף פרסם אותן כמקשה אחת בספרו: "A new kind of science".
דחיפה נוספת וחשובה לאוטומטים תאיים באה בדמות הצעה לפירוש דטרמיניסטי של תורת הקוונטים באמצעות אוטומטים תאיים של  זוכה פרס נובל בפיזיקה Gerard 't Hooft שפרסם שורת מאמרים בנושא שהתפתחו לאינטרפטציה חדשה לתורת הקוונטים