טיורמיט
טיורמיט (באנגלית: turmite) הוא הלחם של "טרמיט" ו"מכונת טיורינג" (Turing machine termites).
במדעי מחשב, טיורמיט הוא מכונת טיורינג המורכבת מכיוון ומצב ו"סריג" שמורכב מרשת דו ממדית אינסופית של תאים. המונח נמלה משמש גם כן לתיאור הטיורמיט. הנמלה של לנגטון היא סוג ידוע של טיורמיט המוגדר על התאים של רשת רבועה. התולעים של פטרסון הם סוג נוסף של טיורמיט המוגדר בשולי רשת איזומטרית.
הוכח שטיורמיטים הם שווי ערך למכונות טיורינג חד-ממדיות עם רצועה אינסופית, וכמו כן הם יכול לדמות אותן.
היסטוריה
הנמלה של לנגטון הומצאה בשנת 1986 והוכרזה כ-"שוות ערך למכונות טיורינג". באופן עצמאי, בשנת 1988, אלן בריידי חשב על הרעיון של מכונות טיורינג דו ממדיות עם אוריינטציה וכינה אותן "מכונות טיורנינג" (TurNing machines).
ככל הנראה באופן עצמאי משני אלה, גרג טורק חקר את אותו סוג של מערכת וכתב לא"ק דיודני עליהם. א"ק דיודני נתן להם את השם "טיור-מיט" בטורו "בילויי מחשב" בסיינטיפיק אמריקן בשנת 1989.
טיורמיט מוחלט לעומת טיורמיט יחסי
טיורמיט יכול להיות מסווג או כיחסי או כמוחלט. לטיורמיט יחסי, שלעיתים מכונה "מכונת טיורמיט", יש נטייה פנימית. הנמלה של לנגטון היא דוגמה כזאת. טיורמיטים יחסיים הם, בהגדרה, איזוטרופיים; כלומר, כיוון הטיורינג אינו משפיע על תוצאות ההתקדמות. טיורמיטים יחסיים נקראים כך משום שהכיוונים מקודדים ביחס לנטייה הנוכחית, שווה ערך לשימוש במילים "שמאלה" או "אחורה". טיורמיט מוחלט מקודד את הכיוונים שלו במונחים מוחלטים: הוראה מסוימת רשאית להורות לטיורמיט לנוע "צפונה". טיורמיטים מוחלטים הם אנלוגיות דו-ממדיות של מכונות טיורינג קונבנציונליות, ולעיתים מכונים בפשוט "מכונות טיורינג דו ממדיות". שארית ערך זה תעסוק במקרה היחסי.
פרוט
הפירוט הבא מתייחס לטיורמיט יחסי, הנמצא על רשת ריבועית דו-ממדית, והוא הסוג הנחקר ביותר של טיורמיט. ניתן להגדיר טיורמט ברשתות אחרות באופן דומה.
כמו בנמלה של לנגטון, הטיורמיט מבצע את הפעולות הבאות בכל צעד:
- פונה על הריבוע (בכפולה כלשהי של 90°).
- משנה את הצבע של הריבוע.
- נע קדימה צעד אחד.
כמו במכונות טיורינג, הפעולות משתנות בהתאם למצב של הטיורמיט ולמצב של הריבוע שעליו הטיורמיט נמצא. לדוגמה, הטיורמיט שמוצג בתמונה בחלק העליון של דף זה פועל על פי הטבלה הבאה:
| צבע נוכחי של הריבוע | |||||||
|---|---|---|---|---|---|---|---|
| 0 | 1 | ||||||
| צבע נוכחי של הטיורמיט | המצב הבא של הריבוע | פנייה | המצב הבא של הטיורמיט | המצב הבא של הריבוע | פנייה | המצב הבא של הטיורמיט | |
| 0 | 1 | R | 0 | 1 | R | 1 | |
| 1 | 0 | N | 0 | 0 | N | 1 | |
הסימונים לכיוונים של הפנייה הם:L (פנייה שמאלה ב90°), R (פנייה שמאלה ב90°), N (ללא פניה), U (סיבוב ב-180°).
דוגמאות
- דוגמאות של טיורמיט בעל 2 צבע ו-2 מצבים על רשת רבועה, כל הדוגמאות החלו מתצורה ריקה:
צמיחה ספרלית
ייצור של כביש לאחר תקופה של צמיחה כאוטית.
צמיחה של תוהו ובוהו עם מרקם ייחודי.
צמיחה עם מרקם ייחודי תוך כדי הרחבת המסגרת.
בניית ספירלת פיבונאצ'י.
החל מרשת ריקה או תצורות אחרות, ההתנהגויות הנפוצות ביותר שנצפו הן צמיחה של תוהו ובוהו, צמיחת ספירלה ובניית "כביש". דוגמאות נדירות הפכו מחזוריות לאחר מספר מסוים של צעדים.
טיורמיטים ומשחק הבונה עסוק
אלן ה' בריידי חיפש סיום לטיורמיטים (המקבילה של בונים עסוקים) ומצא טיורמיט בעל 2 צבעים ו-2 מצבים שצעד 371 צעדים לפני הפסקה, ואחרים שצעדו 121 צעדים לפני הפסקה. הוא גם בנה טיורמיטים שנמצאים על רשת משולשת, ומצא כמה בונים עסוקים גם כאן.
אד פג' ג'וניור ניגש בגישה אחרת למשחק הבונה עסוק. הוא הציע טיורמיטים שיכולים לדוגמה לפנות ימינה ושמאלה באותו זמן ולהתפצל לשתיים. טיורמיטים שיפגשו לאחר מכן ישמידו אחד את השני. במערכת זו, בונה עסוק הוא טיורמיט שבדפוס התחלה מסוים נמשך הכי ארוך לפני שכל הטיורמיטים ישמידו אחד את השני.
סריגים אחרים
בעקבות העבודה הראשונית של אלן ה' בריידי של טיורמיטים על רשת משולשת, נחקרו גם טיורמיטים על רשת משושים. חלק גדול מעבודה זה עשה טים האטון. הוא גם בנה טיורמיטים בשלושה ממדים, וקיבל כמה תוצאות ראשוניות. גם אלן בריידי חקר טיורמיטים יחסיים חד-ממדיים על הסריג השלם, אשר בריידי כינה סנפירים. (טיורמיט חד-ממדי מוחלט ידוע בפשוטות כמכונות טיורינג.)