آلة تورنج

آلة تورنج هي عبارة عن نموذج نظري بسيط يحاكي طريقة عمل الحاسوب. سميت بهذا الإسم نسبة لعالم الرياضيات الانجليزي الان تورنج الذي أوجد هذا النموذج سنة 1936م. هذا النموذج يعطي تعريف رياضي دقيق للمصطلح خوارزم, حيث أنه قادر على تنفيذ أي خوارزم.

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

تقوم آلة التورينغ في الحركة الواحدة واعتماداً على رمز الدخل المقروء من شريط الدخل وحالة التحكم المنتهي بالعمليات التالية: • تغيير حالة التحكم المنتهي. • كتابة رمز شريط في الخلية المقروءة. • التحرك خلية واحدة إلى اليسار أو إلى اليمين.

النموذج الأساسي لآلة تورينغ:

التعريف الصوري لآلة تورينغ

آلة تورينغ هي سباعية (Q,∑,r,d,q0,B,F)M= حيث: • Q هي مجموعة منتهية من الحالات. • r هي أبجدية منتهية من رموز "الشريط" المتاحة. • E هي أبجدية منتهية من رموز الدخل. • d هو تابع حركة الانتقال. • q0 هي الحالة الابتدائية للآلة. • B هو الرمز الفارغ. • F هي مجموعة الحالات النهائية.

الوضع الآني لآلة التورينغ

لتكن (Q,∑,r,d,q0,B,F)M= آلة تورينغ نسمي السلسلة a1qa2 المحتواة في المجموعةr* X Q X r* الوضع الآني لM حيث: • a1a2 سلسلة في r* تمثل محتويات شريط الدخل حتى أقصى خلية يمينية غير فارغة. • q تمثل الحالة الراهنة ل M.

حركة انتقال آلة تورينغ لتكن (Q,∑,r,d,q0,B,F)M= آلة تورينغ نرمز إلى حركة انتقال الآلة M من

وضع آني إلى وضع آني آخر بالعلاقة M | المعرفة على المجموعة: r* X Q X r* كما يلي: X1X2…Xi-1qXi…Xn | M X1X2…pXi-2pXi-1YXi+1…Xn

If i>1 and d(q,x1)=(p,Y,L)

If n=i-1 then Xi=B

If i=1 then no next ID اللغة المقبولة بآلة تورينغ

تعرف اللغة المقبولة من آلة تورينغ (Q,∑,r,d,q0,B,F)M= بأنها اللغة L التي تحقق: L(M)={w |w €∑* and q0w |M a1pa2: p € F; a1,a2 € F*}

نقول إن آلة تورينغ تتوقف عند قبول سلسلة الدخل أي أنه لم يعد هناك أي حركة انتقال أخرى.

قد لاتتوقف آلة تورينغ أبداً من أجل بعض سلاسل الدخل غير المقبولة.

مثال: لتصميم آلة تورينغ M تقبل اللغة L: L= {0^n1^n|n≥1} نقوم بالخطوات التالية: • توجد السلسلة w=0^n1^n على شريط الدخل للآلة M في الحالة البتدائية ومتبوعة بعدد غير منتتهي من الفراغات.

• تبدل الآلة M تكرارياً بالرمز0 في أقصى اليسار للرمز X ثم تتحرك يميناً إلى أقصى رمز يساري مساوياً 1 لتبدله بالرمز Y ثم تعود يساراً إلى الرمز الذي يلي آخر X وهكذا حتى لايبقى أصفار أو واحدات.

• إذا وجدت الآلة عند البحث عن 1 الرمز B تتوقف بدون قبول السلسلة w في حين بعد تعةيض 1 ب Y والعودة إلى اليسار بدون وجود أصفار تقبل السلسلة w في حالة عدم وجود واحدات على الشريط.

لتكن (Q,∑,r,d,q0,B,F)M= آلة تورينغ المطلوبة نجد أن: Q={q0,q1,q2,q3,q4}; ∑={0,1}; r={0,1,X,Y,B}; F={q4}

كل حالة من Q تمثل فرضية أو مجموعة من الفرضيات في البرنامج: • تمثل q0 الحالة الابتدائيةوهي تسبق أي عملية تبديل للرمز 0 الموجود في أقصى اليسار.

• تستخدم الحالة q1 للبحث يميناً متجاوزة الرموز Y,0 وصولاً إلى أول رمز يساري يساوي 1.

• تستخدم الحالة q2 للبحث يساراً 0 وصولاً إلى أول رمز يساوي X وتنتقل إلى الحالة q0 ثم تذهب إلى الرمز 0 الموجود في أقصى اليسار.

• إذا كانت الآلة في الحالة q0 وقرأت الرمز Y فإنها تدخل الحالة q3.

• تستخدم الحالة q3 لتجاوز الرموز Y والتحقق من عدم بقاء واحدات على الشريط.

• تدخل الآلة الحالة q4 عند وجود الرمز B على يمين الرمز Y وتقبل السلسلة عندئذ في حين ترفض السلساة فيما عدا ذلك.

يوضح الشكل التالي قيم التابع d:

المصدر: مدخل إلى الأتومات واللغاتالصورية