اخترع وانغ هاو البلاط (الدومينو) من قبل هاو وانغ في عام 1961 لمشاكل رياضية ، ولكن كانت تستخدم على نطاق واسع في الألعاب لإنشاء رسومات البلاط. بفضلهم ، لا تبدو النتائج متكررة ، سواء في القياسات ثنائية الأبعاد أو في النماذج ثلاثية الأبعاد مع التجانب.
يبدو أن بلاط Van قادر أيضًا على تنفيذ آلات Turing ، وبالتالي ، فهو Turing-full ، مما يعني أنه يمكنهم تنفيذ أي برنامج.
هذا بيان مذهل وغير مفهوم ، لذلك في هذا المنشور سأبحث عن هذه المشكلة قليلاً.
لفترة وجيزة عن فان البلاط
بلاطات Van عبارة عن بلاطات مستطيلة لا يمكن لكل من الأوجه أن تتوافق إلا مع الأوجه المعينة الأخرى ، ولكن بالنسبة لأي وجه معين ، هناك عدة بلاطات يمكن أن تتوافق مع هذا الوجه. عن طريق مطابقة الوجوه ، أعني أنها تتواصل بسلاسة دون إنشاء أي آثار بصرية أو علامات التماس بين البلاط.
هذه الخاصية مفيدة للرسومات ، لأنها تتيح لك إنشاء رسومات بلاطة غير ملحومة ، ولكن يمكن تكوين عشوائية موقع البلاط بشكل كامل ، شريطة أن تكون جميع الوجوه متوافقة مع بعضها البعض. والنتيجة هي الرسومات المتجانبة ، والتي لا تشبه على الإطلاق الرسومات المكررة ، لأن الأنماط المرئية تصبح أقل وضوحًا بكثير من الرسومات المتجانبة التقليدية.
يمكن العثور على أمثلة رسومية ومزيد من المعلومات التفصيلية وروابط إلى Shadertoy هنا:
Wang Tiling .
هنا مثال قمت بإنشائه. رسوماتي هي "مبرمج فني" ، لكنني آمل أن تكون الفكرة واضحة. يتكون الرسم من 16 بلاطًا ، ولكل وجه نوعان مختلفان من الوجوه.
لفترة وجيزة حول تورينج الآلات
تم اختراع آلات تورينج في عام 1936 من قبل آلان تورينج كجهاز كمبيوتر معمم ، والتي ثبت أنها قادرة على تنفيذ أي خوارزمية.
تتكون آلة تورينج من عدة مكونات رئيسية: أشرطة الذاكرة ، رؤوس القراءة / الكتابة ، وأجهزة الحالة.
يحتوي شريط الذاكرة على طول غير محدود ، أي أنه يحتوي على سعة تخزين لا نهائية ، وفي البداية يتم تهيئته باستخدام الأصفار.
يبدأ رأس القراءة / الكتابة من موضع معين من الشريط ويمكنه قراءة / كتابة القيم ، وكذلك التحرك يسارًا ويمينًا على طول الشريط.
يتحكم جهاز الحالة في رأس القراءة / الكتابة.
يعرف جهاز الحالة الحالة التي يوجد فيها ، وله قواعد بشأن ما يجب القيام به في كل ولاية عندما يقرأ قيمة من الشريط.
على سبيل المثال ، في الحالة A ، إذا تمت قراءة 0 من الشريط ، فيمكن أن تكون القاعدة هي الكتابة 1 إلى الموضع الحالي للشريط ، أو تحريك رأس القراءة / الكتابة إلى اليمين ، أو الانتقال إلى الحالة B. يمكن أن تحتوي الولاية B على منطق مختلف تمامًا ويمكن أن تقوم إما بعملية النقل العودة إلى الحالة A ، أو البقاء في الحالة B ، أو الانتقال إلى حالة مختلفة تمامًا.
باستخدام مثل هذا المنطق البسيط للانتقال بين الحالات ، يمكن تنفيذ أي خوارزمية كمبيوتر.
قد تحتوي آلة تورينج أيضًا على "حالة توقف" ، وهذا يعني أن البرنامج قد أتم التنفيذ وقد تم حساب الاستجابة.
تبحث عن بعض البرامج. يمكن رؤيتها بسهولة. مع مرور الوقت ، سوف تنتهي أو ستكون في حلقة لا نهائية ولن تتوقف أبدًا. توجد بعض البرامج بينها ، فهي معقدة وليس من السهل تحديد ما إذا كانت ستتوقف في أي وقت. أثبت Turing أنه لا يوجد حل عام لتحديد ما إذا كانت آلة Turing ستتوقف (إنه برنامج كمبيوتر) ، وهذا ما يسمى
مشكلة التوقف . بشكل عام ، الطريقة الوحيدة لمعرفة ما إذا كان توقف البرنامج هي الانتظار. هذا هو ، في الواقع ، في الحالة العامة ، الإجابات على هذا السؤال هي إما "نعم" أو "ليس بعد" ، ومع ذلك ، في حالة العديد من البرامج المحددة ، يمكنك أن ترى أنه بعد الإطلاق ستنتهي مع مرور الوقت.
حسابات بلاط وانغ
اتضح أن بلاط Wang يمكن أن يحاكي آلة Turing ، أي أنها Turing-Complete ، مما يعني أنه يمكنهم تنفيذ أي خوارزمية كمبيوتر.
لتحقيق ذلك ، نحتاج إلى عمود من بلاطات Van يشير إلى حالة ماكينة Turing في وقت معين ، بدءًا من الوقت 0 في العمود الموجود في أقصى اليسار. سنضع مربعات في العمود على اليمين مع كل قواعد الوجوه ، ثم ننشئ عمودًا على يمينه ، وهكذا ، إلى أن ينتهي البرنامج (أو سنفعل ذلك إلى الأبد إذا لم ينتهي). إذا قمت بتحديد المجموعة الصحيحة للبلاطات ، فسيكون التحقق من الامتثال لقواعد الوجوه في عملية ترتيب البلاط كافياً لإكمال آلة Turing.
دعونا نلقي نظرة على مثال بسيط يحتوي على قواعد منطق آلة الحالة التالية:
- عندما تكون الآلة في الحالة A ، ثم في حالة القراءة 0 ، نكتب 1 ، وننقل رأس القراءة / الكتابة لأسفل ونذهب إلى الحالة B.
- عندما يكون الجهاز في الحالة "أ" ، في حالة القراءة 1 ، يتوقف البرنامج (ينتقل إلى الحالة النهائية).
- عندما تكون الآلة في الحالة B ، في حالة القراءة 0 ، نكتب 1 ، وننقل رأس القراءة والكتابة لأعلى ونذهب إلى الحالة A.
- عندما تكون الآلة في الحالة B ، في حالة القراءة 1 ، يتوقف البرنامج (يذهب إلى الحالة النهائية)
محرك الشريط
بادئ ذي بدء ، نحن بحاجة إلى تخزين دائم للشريط. للقيام بذلك ، نحن بحاجة إلى اثنين من البلاط التالية:
لاختبار عملهم ، يمكننا إعداد جزء من الشريط مع بعض القيم (إنشاء عمود من بلاطات Van) والتأكد من أن بلاطات Van المناسبة الوحيدة الموجودة بجانب العمود الأولي هي بلاطات تنقل القيمتين 0 و 1 للأمام في الوقت المناسب دون تغيير منهم.
في الرسم البياني أدناه ، نقوم بتهيئة الشريط بقيمة 0101 في العمود الموجود في أقصى اليسار (الوقت 0). وجود مربعات ذات وجوه متوافقة فقط ، نرى أن القيم في الذاكرة مخزنة إلى الأبد. قمنا بتنفيذ محرك ذاكرة!
سنبدأ في عرض مثالنا بالذاكرة التي تمت تهيئتها إلى 0 ، والشكل أعلاه يوضح ببساطة استمرار الذاكرة.
قراءة والكتابة آلة الدولة الرأس
يتم تقديم رأس القراءة / الكتابة لجهاز تورينج كجزء من معلومات الوجه. وبالتالي ، بالإضافة إلى تخزين الوجه 0 أو 1 ، إذا كان رأس القراءة / الكتابة فيه ، فسيخزن أيضًا حالة جهاز الحالة.
في المثال الخاص بنا ، يتم استخدام حالتين (لا تشمل الحالة النهائية): A و B. إذا تمت قراءة 1 ، فإن البرنامج ينتهي في أي من الحالات (A أو B).
للتعامل مع هذا ، نحتاج إلى البلاط التالي:
الآن بعد أن أصبحت لدينا قواعد للانتقال إلى الحالة النهائية (القاعدتان 2 و 4) ، نحتاج إلى فهم كيفية تنفيذ القواعد التي تتحكم في التبديل من حالة إلى أخرى (القاعدتان 1 و 3).
تحريك رأس القراءة / الكتابة
تنص القاعدة 1 على أننا إذا كنا في الحالة "أ" وقرأنا "0" ، يجب أن نكتب "1" ، وأنقل رأس القراءة / الكتابة لأسفل وانتقل إلى "الحالة ب".
نحتاج إلى قراءة هذا المربع في الحالة "أ" ، وكتابة الرقم 1 كإخراج ، وأمر التجانب أدناه بالانتقال إلى الحالة "ب".
يمكن أن يكون للبلاط الموجود أسفل اللوح الحالي قيمة 0 أو 1 ؛ دون معرفة قيمة محددة ، يجب أن نحفظها ، لكن نقبل رأس القراءة / الكتابة ونكون في الحالة "ب". لهذا ، نحتاج إلى مربعين - أحدهما مقابل 0 على الشريط في هذا الموضع ، والآخر للواحد على الشريط.
تنص القاعدة 3 على أننا إذا كنا في الحالة B وقرأنا 0 ، يجب أن نكتب 1 ، وننقل رأس القراءة والكتابة لأعلى ونذهب إلى الحالة A.
للقيام بذلك ، نحتاج إلى إنشاء مشابه للبناء للقاعدة 1 ، لكننا لا نتحرك ، بل للأعلى. ستحصل البلاطات الثلاثة التالية على النتيجة المرجوة:
بلاط العمود الأولي
سوف ندرك حدود منطقة المحاكاة كما لو كان لها وجه "x".
هذا يعني أنه لإنشاء العمود الأولي (آلة تورينج في الوقت 0) نحتاج إلى اثنين من البلاط الخاص. هناك حاجة إلى تجانب واحد لتخزين القيمة 0 على الشريط ، الذي يقوم بتهيئة الشريط ، وتجانب آخر - لتخزين موضع رأس القراءة / الكتابة في الحالة A ، وهي حالتنا الأولية.
هذه اثنين من البلاط هي:
مجموعة جاهزة من البلاط
فيما يلي المجموعة الكاملة المكونة من 12 مربعًا التي سنستخدمها:
محاكاة كاملة
هنا هو التصميم الأصلي لآلة تورينج لدينا في الوقت 0. لاحظ أن هذه واحدة من الحالات الأولية المحتملة ، ولكن هذه هي الحالة التي اخترناها. نحن لا نترك فرصة لاختيار أين يبدأ رأس القراءة / الكتابة ووجوده أيضًا. إذا اتبعنا فقط قواعد الوجوه ، فيمكننا الحصول على 4 أو 0 رأس للقراءة والكتابة ، أو أي رقم بينهما.
من هنا ، لإنشاء العمود الثاني ، نبدأ من الأعلى ونتحرك لأسفل ، ونختار البلاط الذي يطابق قيود الوجه التي يلمسها. في هذه الخطوة الأولى ، يقرأ الرأس 0 ، يكتب 1 ، يتحرك لأسفل ويذهب إلى الحالة ب.
هذه هي الخطوة الثانية ، حيث يقرأ الرأس 0 ، يكتب 1 ، يتحرك للأعلى ويدخل في الحالة A.
هذه هي الخطوة الأخيرة التي يقرأ فيها الرأس 1 ويدخل الحالة النهائية ، مما يشير إلى أن البرنامج قد اكتمل.
انتهى البرنامج وأعطانا قيمة إخراج قدرها 0110 أو 6. وهذه القيم ليست مهمة بشكل خاص ، لكن البرامج الأخرى يمكن أن تنتج مخرجات كبيرة. على سبيل المثال ، يمكننا إجبار آلة تورينج على إضافة رقمين ، وسيكون الناتج هو مجموع هذين الرقمين.
تفاصيل مهمة
هنا يجب أن نذكر التفاصيل المهمة التي لم نأخذها في الاعتبار أعلاه ، والتي لم يتم ذكرها في معظم تفسيرات ماكينات Turing على ألواح Van.
عند وضع التجانب الثاني للوقت 2 ، فإن التقييد الوحيد على الوجوه هو أنه يجب أن يكون للبلاط x في الأعلى و 1 على اليسار. في الواقع ، بسبب هذا ، يصبح الموقف غامضًا ، لأنه ليس من الواضح أي من المربعات الموضحة أدناه يجب تحديده.
ثم كيف نختار الصحيح؟
الجواب هو أننا مجرد افتراض واختيار واحد منهم. إذا تم اختيار التجانب الخاطئ في هذه الحالة ، فعندما ننتقل إلى التجانب التالي ، سوف نبحث عن بلاطة مع x في الأعلى و B0 على اليسار. مثل هذا البلاط غير موجود ، لذلك لا يمكننا وضع البلاط. عندما يحدث هذا ، نحتاج إلى العودة إلى التجانب الأخير وتجربة أحد الخيارات الأخرى.
هذا ، لسوء الحظ ، عند محاكاة آلات Turing باستخدام بلاط Wang ، هناك حرفيًا عملية تجريبية وخطأ ، لكن على الأقل يمكن التحكم فيها تمامًا. إنها تعقد العمليات الحسابية قليلاً في تظليل البكسل (أو في الأجهزة الأخرى ذات التوازي العالي) ، لكن التكاليف ليست أكثر من ذلك بكثير.
الخلاصة والروابط
تناقش بعض الروابط أدناه بلاط وانج وآلات تورينج ، ولكن لا يبدو أن المناقشات تلتزم تمامًا بآلات تورينج. على سبيل المثال ، قد تلاحظ أنه في بعض الأمثلة ، يُسمح للبيانات بإرجاع "إلى الوراء في الوقت المناسب" - عند انتهاء البرنامج ، تكون الإجابة على الشريط في وقت 0 من جهاز Turing ، على الرغم من أن هذه البيانات لم تكن موجودة في الوقت المناسب 0. هذا يدل على أن بلاط Wang يمكنه إجراء العمليات الحسابية الخاصة به ، وليس فقط محاكاة آلات Turing ، لكنني لا أعرف بالضبط ما ستسمى هذه التقنية.
بالإضافة إلى ذلك ، إذا كنت مهتمًا بمعرفة ما هو مفيد في الحوسبة باستخدام مربعات Wang ، فأنا شخصياً لا أستطيع أن أتخيل حالات تطبيقها العملي. ومع ذلك ، يبدو أن العلماء اكتشفوا أن الحمض النووي يمكن أن يتصرف بنفس الطريقة التي يعمل بها بلاطات فان ، بمعنى أن الروابط تتم فقط بين الوجوه المتوافقة. بفضل هذا ، يتم الآن البحث عن الحسابات القائمة على الحمض النووي استنادًا إلى عملية الحوسبة باستخدام بلاط وانج. موضوع مثير جدا للاهتمام!
إليك تنفيذ حساب الأعداد الأولية باستخدام مربعات Wang في Shadertoy في تظليل بكسل WebGL:
شاديتوي: WangTiles: PrimeGeneratorفيما يلي بعض مقاطع الفيديو الرائعة عن سيارات Turing ومشكلة التوقف:
شرح تورينج الآلات - Computerphileتورينج ووقف المشكلة - Computerphileوهنا بعض الروابط الأخرى:
الحوسبة مع البلاطويكيبيديا: فان البلاطوانغ البلاط وآلات تورينجوانغ بلاط - 1إليك بعض المقالات العلمية:
الحوسبة مع البلاطحوسبة البلاط