טיורמיט

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה לניווט קפיצה לחיפוש
טיורמיט בעל 2 צבעים ו-2 מצבים על רשת רבועית. כאשר מתחילים עם רשת ריקה, לאחר 8342 צעדים טיורמיט (הריבוע האדום) הציג שני שלבי התנועה כאוטית וקבועים.

טיורמיט אנגלית: turmite) הוא הלחם של "טרמיט" ו"מכונת טיורינג" (Turing machine termites).

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

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

היסטוריה[עריכת קוד מקור | עריכה]

הנמלה של לנגטון הומצאה בשנת 1986 והוכרזה כ-"שוות ערך למכונות טיורינג". באופן עצמאי, בשנת 1988, אלן בריידי חשב על הרעיון של מכונות טיורינג דו ממדיות עם אוריינטציה וכינה אותן "מכונות טיורנינג" (TurNing machines).

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

טיורמיט מוחלט לעומת טיורמיט יחסי[עריכת קוד מקור | עריכה]

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

פרוט[עריכת קוד מקור | עריכה]

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

כמו בנמלה של לנגטון, הטיורמיט מבצע את הפעולות הבאות בכל צעד:

  1. פונה על הריבוע (בכפולה כלשהי של 90°).
  2. משנה את הצבע של הריבוע.
  3. נע קדימה צעד אחד.

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

צבע נוכחי של הריבוע
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 מצבים שצעד 371 צעדים לפני הפסקה, ואחרים שצעדו 121 צעדים לפני הפסקה. הוא גם בנה טיורמיטים שנמצאים על רשת משולשת, ומצא כמה בונים עסוקים גם כאן.

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

סריגים אחרים[עריכת קוד מקור | עריכה]

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

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]