تورميت

في علم الحاسوب ، تُعرف آلة تورينغ باسم "التورميت" ، وهي آلة لها اتجاه بالإضافة إلى حالة حالية و"شريط" يتكون من شبكة ثنائية الأبعاد لا نهائية من الخلايا. ويُستخدم مصطلحا "النملة" و "الدودة" أيضًا. تُعد نملة لانغتون نوعًا معروفًا من التورميت، وهي مُعرّفة على خلايا شبكة مربعة. أما ديدان باترسون فهي نوع من التورميت، وهي مُعرّفة على حواف تبليط مثلثي .

لقد ثبت أن التورميتات بشكل عام تعادل تمامًا في قوتها آلات تورينج أحادية البعد ذات الشريط اللانهائي، حيث يمكن لأي منهما محاكاة الآخر.

تم اختراع نمل لانغتون عام 1986، ووُصف بأنه "مكافئ لآلات تورينغ". ^{[ 1 ]} وبشكل مستقل، في عام 1988، تناول ألين هـ. برادي فكرة آلات تورينغ ثنائية الأبعاد ذات اتجاه، وأطلق عليها اسم "آلات تورنينغ". ^{[ 2 ] [ 3 ]}

على ما يبدو، وبشكل مستقل عن كليهما، ^{[ 4 ]} قام غريغ تورك بالتحقيق في نفس نوع النظام وكتب إلى إيه كيه ديودني بشأنه. أطلق إيه كيه ديودني عليها اسم "تورمايتس" في عموده "ترفيه الحاسوب" في مجلة ساينتفك أمريكان عام 1989. ^{[ 5 ]} يروي رودي روكر القصة على النحو التالي:

يذكر ديودني أنه أثناء بحثه عن اسم لمخلوقات تورك، فكر: "حسنًا، إنها آلات تورينج التي درسها تورك، لذا يجب أن يكون اسمها تور-شيء ما. وهي تشبه الحشرات الصغيرة، أو العث، لذا سأسميها تور-مايتس! وهذا يشبه اسم النمل الأبيض!" وبإذن كريم من تورك وديودني، سأحذف الواصلة، وسأسميها تورمايتس.

يمكن تصنيف التورميتات إلى نوعين: نسبية ومطلقة . التورميتات النسبية، والمعروفة أيضًا باسم "آلات الدوران"، لها اتجاه داخلي. نملة لانغتون مثال على ذلك. التورميتات النسبية، بحكم تعريفها، متناحية الخواص ؛ أي أن تدوير التورميت لا يؤثر على نتيجته. سُميت التورميتات النسبية بهذا الاسم لأن الاتجاهات مُشفّرة بالنسبة للاتجاه الحالي، وهو ما يُعادل استخدام كلمتي "يسار" أو "خلف". أما التورميتات المطلقة، على النقيض، فتُشفّر اتجاهاتها بشكل مطلق: فقد تُوجّه تعليمات مُحددة التورميت للتحرك "شمالًا". التورميتات المطلقة هي نظائر ثنائية الأبعاد لآلات تورينغ التقليدية، ولذلك يُشار إليها أحيانًا ببساطة باسم "آلات تورينغ ثنائية الأبعاد". يُركز الجزء المتبقي من هذه المقالة على الحالة النسبية.

المواصفات التالية خاصة بالتورميت على شبكة مربعة ثنائية الأبعاد، وهو النوع الأكثر دراسة من التورميت. ويمكن تحديد مواصفات التورميت على شبكات أخرى بطريقة مماثلة.

كما هو الحال مع نملة لانغتون، تقوم النملات البيضاء بالعمليات التالية في كل خطوة زمنية:

1. استدر في مكانك (بمضاعفات معينة للزاوية 90 درجة)
2. غيّر لون المربع
3. تحرك للأمام مربعًا واحدًا.

كما هو الحال مع آلات تورينج، تُحدد الإجراءات بواسطة جدول انتقال الحالة الذي يسرد الحالة الداخلية الحالية للتورميت ولون الخلية التي يقف عليها حاليًا. على سبيل المثال، يتم تحديد التورميت الموضح في الصورة أعلى هذه الصفحة بواسطة الجدول التالي:

اتجاه الانعطاف هو واحد من L (90 درجة لليسار)، R (90 درجة لليمين)، N (لا انعطاف) و U ( انعطاف U بزاوية 180 درجة ).

• أمثلة على التورميت ثنائي اللون ثنائي الحالة على شبكة مربعة ، تبدأ جميعها من تكوين فارغ:
• 
  النمو الحلزوني
• 
  إنتاج طريق سريع بعد فترة من النمو الفوضوي
• 
  نمو فوضوي ذو ملمس مميز
• 
  نمو ذو ملمس مميز داخل إطار متوسع
• 
  بناء حلزون فيبوناتشي
• 
  بناء ماسة متنامية

• أمثلة على التورميتات ذات الحالات والألوان المتعددة وعلى شبكات غير مربعة:
• 
  التورميت ثلاثي الحالات ثنائي اللون ينتج نمطًا كسريًا يشبه ندفة الثلج
• 
  تورميت ثلاثي الألوان ثلاثي الحالات على شبكة سداسية ، ينمو بشكل فوضوي بنسيج مميز قبل أن يعلق في حلقة دورية بعد حوالي 194150 خطوة

بدءاً من شبكة فارغة أو تكوينات أخرى، فإن أكثر السلوكيات شيوعاً هي النمو الفوضوي، والنمو الحلزوني، وبناء "الطرق السريعة". وتصبح الأمثلة النادرة دورية بعد عدد معين من الخطوات.

بحث ألين إتش. برادي عن آلات التورمايت التي تتوقف (ما يعادل القنادس المشغولة ) ووجد آلة ثنائية الحالة ثنائية اللون تطبع 37 رقم 1 قبل أن تتوقف، وأخرى استغرقت 121 خطوة قبل أن تتوقف. ^{[ 3 ]} كما درس آلات التورمايت التي تتحرك على شبكة مثلثة ، ووجد العديد من القنادس المشغولة هنا أيضًا.

ابتكر إد بيج الابن نهجًا آخر للعبة القندس النشيط. اقترح استخدام مخلوقات صغيرة (تورمايت) يمكنها الدوران، على سبيل المثال، يمينًا ويسارًا، ثم تنقسم إلى قسمين. تتحد هذه المخلوقات لاحقًا لتفني بعضها بعضًا. في هذا النظام، يُعتبر القندس النشيط هو القندس الذي يستمر أطول فترة ممكنة من نمط ابتدائي يتكون من مخلوق واحد قبل أن تفني جميع المخلوقات بعضها بعضًا. ^{[ 6 ]}

بعد العمل الأولي الذي قام به ألين إتش. برادي حول التورميت على شبكة مثلثية، تم استكشاف التبليطات السداسية أيضًا. ويعود الفضل في جزء كبير من هذا العمل إلى تيم هاتون، ونتائجه موجودة في مستودع جداول القواعد. كما درس هاتون التورميت في ثلاثة أبعاد، وجمع بعض النتائج الأولية. وقد بحث كل من ألين إتش. برادي وتيم هاتون أيضًا في التورميت النسبي أحادي البعد على شبكة الأعداد الصحيحة ، والذي أطلق عليه برادي اسم "القلابات" . (أما التورميت المطلق أحادي البعد، فيُعرف ببساطة باسم آلات تورينج).

• الأوتوماتا الخلوية – نموذج منفصل للحساب 
• نملة لانغتون – آلة تورينغ ثنائية الأبعاد ذات سلوك ناشئ 
• ديدان باترسون – عائلة من الأوتوماتا الخلوية لنمذجة سلوك التغذية 

• "صفحة ويب تعرض عدة أنواع من النمل الأبيض" . مؤرشفة من الأصل بتاريخ 21-12-2013.
• بيج الابن، محرر (7 يونيو 2004). "ألعاب الرياضيات: آلات تورينج ثنائية الأبعاد" . MAA Online. مؤرشف من الأصل بتاريخ 16 مايو 2013.
• بيج الابن، محرر (27 أكتوبر 2003). "ألعاب الرياضيات: إعادة النظر في ديدان باترسون" . MAA Online. مؤرشف من الأصل في 23 مارس 2004.
• تورمايت ، في عالم الرياضيات .
• نص برمجي رائع لتوليد النمل الأبيض بشكل عشوائي
• رسم بياني لحركة التورمايتس والقنادس المشغولة، المطلقة والنسبية، على شبكات مربعة ومكعبة ومثلثة وسداسية.