הנמלה של לנגטון

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

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

חוקים

אנימציה של 200 הצעדים הראשונים של הנמלה של לנגטון.
  • בריבוע לבן הנמלה פונה 90° ימינה, מחליפה את הצבע של המשבצת שעליה היא עומדת ונעה משבצת אחת קדימה.
  • בריבוע שחור הנמלה פונה 90° שמאלה, מחליפה את הצבע של המשבצת שעליה היא עומדת ונעה משבצת אחת קדימה.

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

מצבי התנהגות

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

  1. פשטות. במהלך כמה מאות המהלכים הראשונים שלה הנמלה יוצרת דפוסים מאד פשוטים ולעיתים קרובות סימטריים.
  2. כאוס. לאחר כמה מאות מהלכים, דפוס גדול ולא סדיר של ריבועים שחורים ולבנים מופיע. מסלול הנמלה נראה לכאורה אקראי עד לכ-10,000 צעדים.
  3. סדר מתהווה. לבסוף הנמלה מתחילה לבנות דפוס חוזר ונשנה, המכונה "כביש", של 104 צעדים שחוזרים על עצמם זמן בלתי מוגבל.

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

גרסאות במספר רב של צבעים

גרג טורק וג'ים פרופן חשבו על הרחבה פשוטה של הנמלה של לנגטון. במקום שני צבעים ניתן לשים כל מספר של צבעים, כשסדר הצבעים מחזורי, ופיתחו שיטה פשוטה למתן שמות: לכל אחד מהצבעים ניתנת אות "L" או "R" שמסמלות את כיון התנועה של הנמלה. לפי שיטה זו הנמלה של לנגטון היא "RL". חלק מהנמלים של לנגטון בשיטה זו יוצרים דפוסים סימטריים פעם אחר פעם. אחת הדוגמאות הפשוטות לנמלה כזו היא הנמלה "RLLR". תנאי אחד היוצר מצב זה הוא שהשם של הנמלה נראה כרשימה מחזורית, כלומר שהוא מורכב מזוגות רצופים של "LL" או "RR".

טיורמיטים 

Postscript-viewer-shaded.png ערך מורחב – טיורמיט

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

גרסאות במספר רב של נמלים

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

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

ראו גם

קישורים חיצוניים

ויקישיתוף ראו מדיה וקבצים בנושא זה בוויקישיתוף.