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

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

آلة تورنج

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

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

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

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

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

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

يمكن اعتبار `برنامج` الآلة، وهو يحدد لكل زوج من الحالة الحالية والرمز الحالي ثلاثيا، حيث يكون `برنامج` معرفا بالشكل التالي: عندما تكون الحالة الحالية هي `q` والرمز الحالي هو `σ`، فإن `برنامج` يحدد الحالة التالية `p` والرمز `ρ` الذي يتم استبداله بالرمز `σ`. ويشير `D` إلى اتجاه حركة المؤشر ويمكن أن يكون إما `→` أو `←` أو `-`. عندما يكون الرمز `▷`، يكون `برنامج` على النحو التالي: عندما تكون الحالة `q` والرمز `▷`، فإن `برنامج` يحدد الحالة التالية `p` والرمز `ρ` يكون `▷` ويتجه المؤشر دائما إلى اليمين `→` ولا يتم محوه أبدا .

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

بشكل عام لوصف الفعالية لالات تورنغ نستخدم بشكل عام مصطلح “صورة”(Configuration). وبشكل غير دقيق صورة آلة تورنغ في لحظة معينة تحوي كل الحسابات التي قامت بها الآلة في تلك اللحظة، أي أنها تحتوي على الحالة الحالية والسلاسل التي تصف ما على يمين المؤشر وما على يساره. نقول إن الصورة (q, w, u) تنتج الصورة (q`, w`, u`) في خطوة واحدة إذا كانت الآلة تنتقل من الحالة q إلى الحالة q` وتقوم بتحديث السلاسل w و u وفقا للحركة D. يوجد ثلاث حالات ممكنة للحركة D:

إذا كانت السلسلة D تحتوي على النمط ‘w’، فإن ‘w’ يمكن أن يكون أي سلسلة، ولكن يمكن استبدال الرمز الأخير في ‘w’ الذي كان يحمل القيمة ‘sigma’ بالرمز الذي يحمل القيمة ‘rho’، ويمكن حذف الرمز الأول في السلسلة u .

إذا D= ، في هذه الحالة `w هو w ولكن الحرف الأخير في w تم حذفه، و`u هو u ولكن قمنا بإضافة ρ في البداية .

إذا كان {displaystyle D=-} ، فإن w هي w غير، ولكن تم استبدال الرمز الأخير في w الذي كان {displaystyle sigma} بـ {displaystyle
ho} ، ولكن {displaystyle u’=u}

بنفس الطريقة يمكننا أن نقول أن الصورة (q، w، u) تنتج الصورة (q`، w`، u`) في k خطوات ترمز إليها بـ (q، w، u) -> M^k -> (q`، w`، u`)، ونقول أن الصورة (q، w، u) تنتج الصورة (q`، w`، u`) ونرمز لها بـ (q، w، u) -> M^* -> (q`، w`، u`) إذا كان هناك k ≥ 0 حيث يتحقق: (q، w، u) -> M^k -> (q`، w`، u`)  .