معلومات عن ” آلة تورنج “

تعد آلة تورنج هي من أهم النماذج النظرية البسيطة وهي التي تحكي بطريقة عمل الحاسوب وهي التي تم تسميتها بهذا الاسم نسبة إلى عالم الرياضيات الأنجليزي

آلان تورنج

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

آلة تورنج

يتم فحص العديد من العمليات الرياضية من خلال آلة تورنج وهي التي يتم استخدامها بشكل واسع النطاق وفي مجال الدراسة وهي ذات القدرة الخاصة بالحاسوب والعمليات والتي من الممكن أو لا يمكنه  تنفيذها.

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

وهو الذي يكون من النموذج الرئيسي لآلة التورينج من التحكم ومنه وشريط يدخل منته ومن ناحية أخري هي جهة اليسار وغير منته من جهة اليمين وهو الذي يتم تقسيمه إلى العديد من الخلايا والتي منها ما يحمل رمزاً واحداً من مجموعة منتهية وهي التي يتم إطلاق عليها أسم “رمز الشريط” ورأس يسمى رأس القراءة و

الكتابة

وهي التي تمر في كل مرة على خلية واحدة من الشريط وهي تحتوي على الخلايا الـ اليسارية من شريط الدخل n عدد منته وفي الحالة الأولية تكون رموز الدخلفي حين تشمل على الخلايا المتبقية من الشريط رمزاً فارغاً.

أنواع آلات تورنج

توجد العديد من الأنواع الخاصة بالالات تورنج أو الالات الشبيهة ولكن بالرغم من من هذا فإنه قد يظهر أن آلة ترنج عمومية وهذا ما يكفي لما تشمل هذه الأنواع من الآلات الخاصة بالنظرة التي تتبناها تورنج تشرتش في اطرحتهما المعروفة إذا أنهما فرضاً إن كان تعريف إلى مصطلح

الخوارزمية

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

طريقة عمل ألة تورنج

يمكن اعتبار {\displaystyle \delta }  “برنامج” الآلة وهو يحدد , لكل زوج من الحالة الحالية {\displaystyle q\in K}  والرمز الحالي {\displaystyle \sigma \in \Sigma }  , ثلاثي أي : {\displaystyle \delta (q,\sigma )=(p,\rho ,D)}  حيث أنَّ p هو الحال التالية و- {\displaystyle \rho }  هو الرمز الذي تم استبداله مع {\displaystyle \sigma }  . و- {\displaystyle D\in \{\to ,\gets ,-\}}  هو اتجاه تحرك المؤشر . وعند الرمز {\displaystyle \vartriangleright }  إذا {\displaystyle \delta (q,\vartriangleright )=(p,\rho ,D)}  حينها {\displaystyle \rho =\vartriangleright }  و- {\displaystyle D=\to }  أي انه {\displaystyle \vartriangleright }  دائما يوجه المؤشر إلى اليمين ولا يمحى ابدا .

صورة آلة تورنغ

بشكل عام لوصف الفعالية لالات تورنغ نستخدم بشكل عام مصطلح “صورة”(Configuration) . وبشكل غير دقيق صورة آلة تورنغ في لحظة مُعينة تحوي كل الحسابات التي قامت بها الآلة في تلك اللحظة , أي انه صورة آلة تورنغ M هي ثلاثي : {\displaystyle (q,w,u)}  حيث أن {\displaystyle q\in K}  هو الحال الحالي , و- {\displaystyle w,u\in \Sigma ^{*}}  هما سلسلتان اللتين تصفان ما على يمين المؤشر (الذي قد يكون فارغا) وما على يساره . نقول أن الصورة {\displaystyle (q,w,u)}  تنتج الصورة {\displaystyle (q’,w’,u’)}  في خطوة واحدة نرمز لها ب- {\displaystyle (q,w,u){\overset {\underset {\mathrm {M} }{}}{\to }}(q’,w’,u’)}  إذا خطوة الآلة بعد الصورة {\displaystyle (q,w,u)}  نرى الصورة {\displaystyle (q’,w’,u’)}  أي انه : فلنفرض أنَّ {\displaystyle \sigma }  هو الرمز الأخير في السلسلة {\displaystyle w}  ولنفرض أن {\displaystyle \delta (q,\sigma )=(p,\rho ,D)}  حينها {\displaystyle q’=p}  , اما بالنسبة ل-D فعندنا ثلاث حالات :

إذا {\displaystyle D=\to }  حينها ‘w هي w غير أن الرمز الأخير في w الذي كان {\displaystyle \sigma }  بدلناه ليكون {\displaystyle \rho }  وأول رمز في u هو الرمز الحالي أي انَّ ‘u هو u غير أن الرمز الأول في u قد حذف .

إذا {\displaystyle D=\gets }  حينها ‘w هي w غير أن الرمز الأخير في w حُذف , و ‘u هو u غير أننا اضفنا {\displaystyle \rho }  لبدايته .

إذا {\displaystyle D=-}  حينها ‘w هي w غير أن الرمز الأخير في w الذي كان {\displaystyle \sigma }  بدلناه ليكون {\displaystyle \rho }  ولكن {\displaystyle u’=u}

بشكل مشابه يمكن القول أن الصورة {\displaystyle (q,w,u)}  تنتج الصورة {\displaystyle (q’,w’,u’)}  خلال k خطوات نرمز لها ب-{\displaystyle (q,w,u){\overset {\underset {\mathrm {M^{k}} }{}}{\to }}(q’,w’,u’)}  , ونقول أنَّ الصورة {\displaystyle (q,w,u)}  تنتج الصورة {\display style (q’,w’,u’)}  ونرمز لهذا ب- {\displaystyle (q,w,u){\overset {\underset {\mathrm {M^{*}} }{}}{\to }}(q’,w’,u’)}  إذا يوجد {\displaystyle k\geq 0}  بحيث يتحقق : {\displaystyle (q,w,u){\overset {\underset {\mathrm {M^{k}} }{}}{\to }}(q’,w’,u’)}  .