טיורמיט
במדעי מחשב, טיורמיט (באנגלית: Turmite) הוא מכונת טיורינג בעלת אוריינטציה, מצב ו״סרט״ שמורכב מרשת דו־ממדית אינסופית של תאים. המונח נמלה משמש גם כן לתיאור הטיורמיט. הנמלה של לנגטון היא סוג ידוע של טיורמיט המוגדר על התאים של רשת רבועה. התולעים של פטרסון הם סוג נוסף של טיורמיט המוגדר בשולי רשת איזומטרית.
הוכח שטיורמיטים הם שקולים מבחינת כוח חישובי למכונות טיורינג חד־ממדיות עם סרט אינסופי, כיוון שמודל אחד יכול לדמות (״לסמלץ״) את המודל השני ולהפך.
השם ״טיורמיט״ הוא הלחם של המילים ״טיורינג״ ו״טרמיט״ (Turing machine termites).
היסטוריה[עריכת קוד מקור | עריכה]
הנמלה של לנגטון הומצאה בשנת 1986 והוכרזה כ"שקולה למכונות טיורינג". באופן בלתי תלוי, בשנת 1988, אלן בריידי חשב על הרעיון של מכונות טיורינג דו־ממדיות עם אוריינטציה וכינה אותן "מכונות טיורנינג" (TurNing machines).
ככל הנראה באופן עצמאי משני אלה, גרג טורק חקר את אותו סוג של מערכת וכתב לא"ק דיודני עליהם. א"ק דיודני נתן להם את השם "טיור-מיט" בטורו "Computer Recreations" בסיינטיפיק אמריקן בשנת 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°).
למשל, אם המצב הנוכחי של הטיורימיט הוא 0 והוא נמצא בריבוע שצבעו 0, הוא יפנה ימינה ב־90°, ישנה את צבע הריבוע הנוכחי ל־1 ויתקדם ריבוע אחד קדימה, ללא שינוי במצב הטיורימיט.
דוגמאות[עריכת קוד מקור | עריכה]
- דוגמאות של טיורמיט בעל 2 צבעים ו־2 מצבים על רשת ריבועית, כל הדוגמאות החלו מתצורה ריקה:
-
צמיחה ספירלית -
ייצור של כביש לאחר תקופה של צמיחה כאוטית. -
צמיחה כאוטית עם מרקם ייחודי. -
צמיחה עם מרקם ייחודי תוך כדי הרחבת המסגרת. -
בניית ספירלת פיבונאצ'י.
החל מרשת ריקה או תצורות אחרות, ההתנהגויות הנפוצות ביותר שנצפו הן צמיחה כאוטית, צמיחת ספירלה ובניית "כביש". דוגמאות נדירות הפכו מחזוריות לאחר מספר מסוים של צעדים.
טיורמיטים ומשחק הבונה העסוק[עריכת קוד מקור | עריכה]
אלן ה' בריידי חיפש טיורמיטים שעוצרים לאחר מספר סופי של צעדים (המקבילה של בונים עסוקים) ומצא טיורמיט בעל 2 צבעים ו־2 מצבים שהדפיס את הספרה ״1״ 37 פעמים לפני עצירה, ואחרים שצעדו 121 צעדים לפני עצירה. הוא גם בנה טיורמיטים שנמצאים על רשת משולשת, וגם במקרה זה מצא כמה בונים עסוקים.
אד פג' ג'וניור נקט בגישה אחרת למשחק הבונה העסוק. הוא הציע טיורמיטים שיכולים לדוגמה לפנות ימינה ושמאלה בו־זמנית ולהתפצל לשניים. טיורמיטים שייפגשו לאחר מכן ישמידו אחד את השני. במערכת זו, בונה עסוק הוא כזה שמתחיל מדפוס התחלה כלשהו בעל טיורימיט יחיד, ורץ למשך הזמן הארוך ביותר לפני שכל הטיורימיטים משמידים זה את זה.
סריגים אחרים[עריכת קוד מקור | עריכה]
בעקבות העבודה הראשונית של אלן ה' בריידי של טיורמיטים על רשת משולשת, נחקרו גם טיורמיטים על רשת משושים. חלק גדול מעבודה זה עשה טים האטון. הוא גם בנה טיורמיטים בשלושה ממדים, וקיבל כמה תוצאות ראשוניות. אלן בריידי חקר גם טיורמיטים יחסיים חד־ממדיים על הסריג השלם, אשר בריידי כינה flippers. (טיורמיט חד־ממדי מוחלט הוא פשוט מכונת טיורינג.)
