آلة تورنغ

تعريف

من الناحية الرياضية آلة تورنغ هي رباعية  حيث أن  هي مجموعة نهائية من الحالات (states) ,  هي مجموعة نهائية من الرموز وعادة ما تُسمى هذه المجموعة أبجدية M . سنفرض أنَّ  ,  دائما يحتوي على رمزين خاصين هما رمز البداية () ورمز الفراغ (),  هي دالة الانتقال أي  في حين أنَّ h هو حالة التوقف و-"yes" هي حالة القبول و-"no" هي حالة الرفض . ومؤشرات الاتجاه  تعني تحرك يمينا و-  تحرك يسارا و-  معناه لا تتحرك وهذه المؤشرات ليست ضمن المجموعة :  .

طريقة عمل الآلة

يمكن اعتبار  "برنامج" الآلة وهو يحدد , لكل زوج من الحالة الحالية  والرمز الحالي  , ثلاثي أي :  حيث أنَّ p هو الحال التالية و-  هو الرمز الذي تم استبداله مع  . و-  هو اتجاه تحرك المؤشر . وعند الرمز  إذا  حينها  و-  أي انه  دائما يوجه المؤشر إلى اليمين ولا يمحى ابدا .
البرنامج يبدأ في الحالية الابتدائية  . السلسلة تُهيئ فيكون في أولها الرمز  ويتبعه سلسلة طولها نهائي :  ونسمي x مُدخل الآلة . في البداية المؤشر يؤشر على بداية المُدخل وبشكل عام هو  . من هذه الصورة (configuration) الأولية الآلة تتحرك حسب  وخلال هذا يتغير الحال وتطبع الآلة المُخرج وتحرك المؤشر وبعدها تتحرك خطوة أخرى وعلى هذا المنوال ...
كما ذكرنا سالفا بالنسبة  فانه لا يمكن للمؤشر ان "يقع يسارا" أي أنه دوما سيتحرك المؤشر ضمن نطاق تواجد سلسلة المُدخل . اما بالنسبة لليمين فان نهاية السلسلة تكون عندما يصل المؤشر إلى الرمز  حينها يمكنه إعادة كتابة المحتوى هكذا السلسلة تصبح أطول ولا يمكنها ان تصبح أقصر وهذه صفة مهمة لان الآلة مُعدة لتقوم بحسابات بشكل عام .
تتوقف الآلة عندما تصل إلى واحد من ثلاث حالات التوقف وهي "yes" , "no" , h والتي تم ذكرها انفا , عندما تصل إلى هذه الحالة نقول ان الآلة توقفت . ونقول ان الآلة "قبلت" المدخل إذا توقفت في الحال "yes" اما إذا توقفت على الحال "no" فاننا نقول ان الآلة "رفضت" المُدخل . نرمز للمُخرج الآلة  لذا فانه في حال قبلت أو رفضت الآلة المُدخل  حسب الجواب .
إذا دخلت الآلة حالة التوقف حينها السلسلة التي تبدأ من الرمز  حتى الرمز الفارغ نقول انها سلسلة المُخرج (أو باختصار المُخرج) نرمز لها ب-y حينها نكتب  للدلالة على أنها المُخرج , في بعض الأحيان قد لا تتوقف الآلة M عندما المُدخل يكون x وحينها نكتب :  .

مخطط الصور

فلتكن M آلة تورنغ , لكل  مخطط الصور,GM,x , هو مخطط الذي فيه كل رأس هو صورة آلة تورنغ M أثناء حساب x , ويوجد ضلع بين رأسين c₁ ,c₂ فقط إذا يمكن الوصول من c₁ إلى c₂ بخطوة حسابية واحدة .
لهذا المخطط أهمية كبيرة في نظرية التعقيد حيث أن له استخدامات عديدة من بينها في مبرهنة سافيتش , L⊆ NL , NL⊆ P , PSPACE ⊆EXP ...

مقاييس التعقيد

التعقيد هو تحديد أحد خصل الآلة لكل المُدخلات (مثل : الوقت أو كمية المساحة الاضافية) والتي نريد قياسها , كما في الخوارزميات كان هناك مقياس "النجاعة" هو وقت الخوارزمية ولعلنا أردنا في بعض المسائل تحديد كمية الوقت مثلا : في مسألة تصفيف الاعداد , يمكننا حل هذه المسألة بواسطة تصفيف الفقاعة بوقت (O(n² بهذا نكون قد حصرنا الوقت وهكذا فاننا نعلم أن كل مُدخل لن يلزمه أكثر من هذا الوقت , وقياس وقت آلة تورنغ يكون بعد عدد الخطوات حتى توقف الآلة وإخراج النتيجة . بشكل رياضي : لتكن  دالة , نقول أن آلة تورنغ تعمل خلال وقت  إذا لكل مُدخل  الوقت (عدد خطوات الحساب أو بشكل مكافئ عدد الصور حتى الوصول لصورة نهائية) اللازم للالة M هو  (نرمز لطول x ب-|x| ). الدالة (f(n هي حد على وقت M .

انواع الات تورنغ

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

آلة تورنغ عديدة الاشرطة

وهي آلة تورنغ كما عرفناها سابقا غير ان فيها اختلاف بسيط : بدل أن يكون هناك شريط مُدخل واحد هنالك عدة اشرطة , وهذا النموذج هو لمحاكاة الخوارزميات الموازية ولكن كما تم الذكر فان هذه الآلة يمكن محاكاتها بواسطة آلة تورنغ عادية . في الواقع إذا كان وقت عمل آلة تورنغ عديدة الاشرطة هو  حينها يمكن بناء آلة تورنغ مع شريط واحد 'M تحاكي الآلة M بحيث أنَّ وقتها هو  أو بكلمات أخرى كل ما نستطيع فعله مع آلة تورنغ عديد الاشرطة يمكن فعله أيضا مع آلة تورنغ بشريط واحد .

آلة تورنغ غير حتمية

بينما تنص اطروحة تشرتش على أن كل نموذج حسابي معقول مساوي لالة تورنغ مع فرق وقت كثير الحدود هذه الآلة , أي آلة تورنغ غير حتمية, يُعتقد بانها لا تحقق هذه الاطروحة حيث أنه حتى يومنا ما زالت مسألة محاكاة هذه الآلة هو الأصعب إذ انه لا يوجد الا محاكاة التي وقتها على آلة تورنغ أسية وهذا هو أساس المسألة الشهيرة NP≠P .

تعريف

آلة تورنغ غير حتمية هي رباعية  وهي قريبة جدا من الآلة العادية :  هي كما في السابق , ولكن الآن لا يوجد خيار واحد للانتقال ولكن مجموعة من الخيارات , وهذا نراه في أن  لم تعد دالة ولكن علاقة (relation)  .

محاكاة الآلة

يمكن محاكاة هذه الآلة بواسطة آلة تورنغ عادية (وحتى نفرق بينها يمكن تسميتها آلة تورنغ حتمية) ولكن الوقت اللازم للمحاكاة أُسي وحدسية NP≠P تقترح انه لا يوجد محاكاة كثيرة الحدود ما يعنيه انه قد يكون صعبا الاتيان بمحاكاة عملية .

آلة تورنغ مع اوركل

هذا النوع من الالات ما هو الا توسيع لالة تورنغ العادية , وفي هذا النموذج تُعطى الآلة القدرة على حل مسألة ربما صعبة بخطوة حسابية واحدة , ولهذه الالات أهمية عظمى في نظرية التعقيد الحسابي إذ انه ينظر لهذا النوع من الالات على أنه اختصار (reduction) وقد تبين ان هذا التوسيع مُفيد جدا في كثير من التعريفات المهمة منها تعريف PCP , وهرم كثير الحدود , ...

آلة تورنغ احتمالية

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

الالات تورنغ على انها سلاسل وآلة تورنغ الكونية

بشكل واضح يمكن تمثيل آلة تورنغ على أنها سلسلة إذ انه يمكن كتابتها وبالتالي يمكن تحويل هذه الآلة إلى سلسلة 0 و- 1 , وهذه الملاحظة لها اهميتها العظمى على علم الحاسوب النظري والعملي إذ انه من دونها ما كان ليكون هناك حاسوب متعدد الاستخدامات . لكل آلة تورنغ حتى نستطيع تمثيلها بواسطة سلسلة سنقوم أيضا بتمثيل دالة الانتقال , كما أن كل  سيكون عبارة عن تمثيل لالة تورنغ , كما أن كل آلة تورنغ يوجد عدد لا نهائي من السلاسل التي تمثل هذه الآلة .
فلتكن M آلة تورنغ نرمز ب-  تمثيل الآلة M على أنها سلسلة . ولنفرض أنَّ  هي سلسلة حينها نكتب ان آلة تورنغ التي تمثلها  ب-  .

آلة تورنغ الكونية

هي آلة تورنغ التي تحاكي عمل الالات تورنغ , بشكل غير رسمي آلة تورنغ الكونية عملها مشابه لعمل المُصرف (compiler) حيث أنَّ مُدخل المُصرف برنامج بلغة برمجة مُعينة ويقوم بكتابة برنامج الحاسوب قادر على تنفيذه خطوة خطوة , بشكل رسمي : يوجد آلة تورنغ كونية  بحيث أنَّ لكل  ,  . بالاضافة إذا  تتوقف خلال T خطوات على المُدخل x , حينها  تتوقف خلال  حيث أنَّ C هو عدد يتعلق بكبر أبجدية M وعدد الاشرطة وعدد الحالات .