آلة تورينج TURING MACHINE

1 دقيقة

ما هي آلة تورينج؟

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

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

يحدد العمود الأول والثاني من الجدول التراكيب المختلفة لمدخلات آلة تورينج. فيما يحدد العمود الثالث والرابع والخامس العمليات التي ستؤديها على المدخلات. فعلى سبيل المثال إذا كانت الحالة الحالية “A” والرمز في الخلية تحت الرأس “0”، يجب أن تكتب الآلة الرمز “1” في تلك الخلية. ومن ثم يجب أن تُحرك الشريط إلى اليمين وتنتقل إلى الحالة “B”. تتابع الآلة كما في المثال السابق حسب التعليمات في الجدول، وبهذه الآلية البسيطة يمكنها محاكاة منطق أعقد الخوارزميات الحاسوبية.