آلات تورينج
آلة تورينج هي جهاز تجريدي ذو تحكم محدود وشريط غير محدود، يجسد المفهوم البديهي للخوارزمية، ويعمل كنموذج مرجعي معياري لما هو قابل للحساب.
Definition
تتكون آلة تورينج من مجموعة محدودة من الحالات وشريط ثنائي الاتجاه لا نهائي من الخلايا؛ في كل خطوة تقرأ الرمز الموجود تحت رأسها، وتكتب رمزًا، وتتحرك يسارًا أو يمينًا، وتغير حالتها وفقًا لدالة انتقال، وتتوقف عندما تدخل حالة قبول أو رفض.
Scope
يغطي هذا الموضوع تعريف وتشغيل آلات تورينج، التكوينات والحسابات، متانة النموذج تحت المتغيرات مثل الأشرطة المتعددة واللا حتمية، آلة تورينج الشاملة التي يمكنها محاكاة أي آلة أخرى، وترميز الآلات كبيانات مما يجعل الحجج المرجعية الذاتية وعدم القابلية للتقرير ممكنة.
Core questions
- كيف يجسد جهاز قراءة-كتابة-تحريك بسيط المفهوم الكامل للخوارزمية؟
- لماذا تقوم العديد من المتغيرات للنموذج بحساب نفس الدوال بالضبط؟
- ما هي الآلة الشاملة، ولماذا يعتبر وجودها مهمًا؟
- كيف يمكّن ترميز الآلات كسلاسل من إثباتات حول سلوكها الخاص؟
Key theories
- الشمولية
- توجد آلة تورينج شاملة واحدة، تقوم، عند إعطائها ترميز أي آلة ومدخلاتها، بمحاكاة حساب تلك الآلة، مما ينبئ بالحاسوب ذي البرامج المخزنة حيث تكون البرامج نفسها بيانات.
- متانة النموذج
- إن إضافة أشرطة، أو رؤوس متعددة، أو أشرطة ثنائية الأبعاد، أو اللا حتمية لا يغير فئة الدوال القابلة للحساب، لذا فإن آلة تورينج تجسد مفهومًا للحساب غير حساس لمثل هذه التفاصيل.
Clinical relevance
تُعد آلة تورينج المعيار الذي تُقاس به قوة لغات البرمجة وهياكل الحاسوب، وتُعد الآلة الشاملة السلف المفاهيمي للحاسوب ذي البرامج المخزنة للأغراض العامة الذي تقوم عليه جميع الحوسبة الحديثة.
History
قدم تورينج آلاته في عام 1936 لتحديد ما يعنيه أن يكون الرقم قابلاً للحساب ولحل مشكلة القرار لهيلبرت. وقد أثرت فكرة الآلة الشاملة، التي يتحكم فيها وصف مخزن بجهاز عام، في تصميم فون نيومان للحاسوب ذي البرامج المخزنة بعد عقد من الزمان.
Key figures
- Alan Turing
- Emil Post
- John von Neumann
Related topics
Seminal works
- turing1937
- sipser2013
Frequently asked questions
- هل آلة تورينج حاسوب حقيقي؟
- لا، إنها تجريد رياضي بشريط غير محدود ولا تهتم بالسرعة أو تكلفة الذاكرة. قيمتها مفاهيمية: فهي تحدد بالضبط ما يمكن حسابه من حيث المبدأ، وأي مهمة يمكن للحاسوب الحقيقي أن يؤديها يمكن لآلة تورينج أيضًا أن تؤديها إذا توفر لها شريط ووقت كافيان.
- لماذا تعتبر آلة تورينج الشاملة مهمة؟
- إنها تظهر أن آلة ثابتة واحدة يمكنها تنفيذ سلوك أي آلة أخرى عند إعطائها وصف تلك الآلة كمدخل. هذا هو الأساس النظري للحاسوب القابل للبرمجة للأغراض العامة، حيث يكون البرنامج بيانات تُغذى لجهاز تفسير واحد بدلاً من إعادة التوصيل لكل مهمة.