آلة تورنغ
آلة تورنغ هي نموذج نظري بسيط يحاكي طريقة عمل الحاسوب. سميت بهذا الاسم نسبة لعالم الرياضيات الإنجليزي آلان تورنغ الذي أوجد هذا النموذج سنة 1936م. هذا النموذج يعطي تعريفا رياضيا دقيقا للمصطلح خوارزم Algorithm, أهمية هذا النموذج تكمن في بساطته مقارنة بجهاز الحاسوب المعقد وبالرغم من ذلك فهو قادر على تنفيذ كل خوارزمية قابلة للتنفيذ بواسطة أي حاسوب متطور. لذلك يمكن معرفة إذا كانت عملية معينة قابلة للتنفيذ بواسطة الحاسوب أم لا عن طريق فحصها بواسطة آلة تورنغ. من هنا فإن لآلة تورنغ استعمال واسع في مجال دراسة قدرة الحاسوب والعمليات التي يمكنه أو لا يمكنه تنفيذها، وهو ما يسمى علم قابلية الحساب.
يعتبر نموذج آلة التورينغ نموذج رياضياً بسيطاً للحاسوب وينمذج المقدرة الحسابية لحاسوب ذي وظائف عمومية وهو أيضاً من أهم اللغات الصورية إذ يقبل أوسع مجموعة منها وهي اللغات القابلة للعد عمودياً والتي يمكن توليدها بنماذج قواعدية من النوع صفر. يتألف النموذج الأساسي لآلة التورينغ من تحكم منته وشريط دخل منته من جهة واحدة هي جهة اليسار وغير منته من جهة اليمين ومقسم إلى عدة خلايا كل منها يحمل رمزاً واحداً من مجموعة منتهية تسمى "رموز الشريط" ورأس يسمى رأس القراءة والكتابة الذي يمر في كل مرة على خلية واحدة من الشريط. تحتوي الخلايا الn اليسارية من شريط الدخل (n عدد منته)في الحالة الابتدائية رموز الدخلفي حين تحتوي الخلايا المتبقة من الشريط رمزاً فارغاً.
تقوم آلة التورينغ في الحركة الواحدة واعتماداً على رمز الدخل المقروء من شريط الدخل وحالة التحكم المنتهي بالعمليات التالية:
من الناحية الرياضية آلة تورنغ هي رباعية formula_1 حيث أن formula_2 هي مجموعة نهائية من الحالات (states) , formula_3 هي مجموعة نهائية من الرموز وعادة ما تُسمى هذه المجموعة أبجدية M . سنفرض أنَّ formula_4 , formula_5 دائما يحتوي على رمزين خاصين هما رمز البداية (formula_6) ورمز الفراغ (formula_7), formula_8 هي دالة الانتقال أي formula_9 في حين أنَّ h هو حالة التوقف و-"yes" هي حالة القبول و-"no" هي حالة الرفض . ومؤشرات الاتجاه formula_10 تعني تحرك يمينا و- formula_11 تحرك يسارا و- formula_12 معناه لا تتحرك وهذه المؤشرات ليست ضمن المجموعة : formula_13 .
يمكن اعتبار formula_8 "برنامج" الآلة وهو يحدد , لكل زوج من الحالة الحالية formula_15 والرمز الحالي formula_16 , ثلاثي أي : formula_17 حيث أنَّ p هو الحال التالية و- formula_18 هو الرمز الذي تم استبداله مع formula_19 . و- formula_20 هو اتجاه تحرك المؤشر . وعند الرمز formula_21 إذا formula_22 حينها formula_23 و- formula_24 أي انه formula_6 دائما يوجه المؤشر إلى اليمين ولا يمحى ابدا .
البرنامج يبدأ في الحالية الابتدائية formula_26 . السلسلة تُهيئ فيكون في أولها الرمز formula_6 ويتبعه سلسلة طولها نهائي : formula_28 ونسمي x مُدخل الآلة . في البداية المؤشر يؤشر على بداية المُدخل وبشكل عام هو formula_6 . من هذه الصورة (configuration) الأولية الآلة تتحرك حسب formula_30 وخلال هذا يتغير الحال وتطبع الآلة المُخرج وتحرك المؤشر وبعدها تتحرك خطوة أخرى وعلى هذا المنوال ...
كما ذكرنا سالفا بالنسبة formula_31 فانه لا يمكن للمؤشر ان "يقع يسارا" أي أنه دوما سيتحرك المؤشر ضمن نطاق تواجد سلسلة المُدخل . اما بالنسبة لليمين فان نهاية السلسلة تكون عندما يصل المؤشر إلى الرمز formula_7 حينها يمكنه إعادة كتابة المحتوى هكذا السلسلة تصبح أطول ولا يمكنها ان تصبح أقصر وهذه صفة مهمة لان الآلة مُعدة لتقوم بحسابات بشكل عام .
تتوقف الآلة عندما تصل إلى واحد من ثلاث حالات التوقف وهي "yes" , "no" , h والتي تم ذكرها انفا , عندما تصل إلى هذه الحالة نقول ان الآلة توقفت . ونقول ان الآلة "قبلت" المدخل إذا توقفت في الحال "yes" اما إذا توقفت على الحال "no" فاننا نقول ان الآلة "رفضت" المُدخل . نرمز للمُخرج الآلة formula_33 لذا فانه في حال قبلت أو رفضت الآلة المُدخل formula_34 حسب الجواب .
إذا دخلت الآلة حالة التوقف حينها السلسلة التي تبدأ من الرمز formula_6 حتى الرمز الفارغ نقول انها سلسلة المُخرج (أو باختصار المُخرج) نرمز لها ب-y حينها نكتب formula_36 للدلالة على أنها المُخرج , في بعض الأحيان قد لا تتوقف الآلة M عندما المُدخل يكون x وحينها نكتب : formula_37 .
بشكل عام لوصف الفعالية لالات تورنغ نستخدم بشكل عام مصطلح "صورة"(Configuration) . وبشكل غير دقيق صورة آلة تورنغ في لحظة مُعينة تحوي كل الحسابات التي قامت بها الآلة في تلك اللحظة , أي انه صورة آلة تورنغ M هي ثلاثي : formula_38 حيث أن formula_15 هو الحال الحالي , و- formula_40 هما سلسلتان اللتين تصفان ما على يمين المؤشر (الذي قد يكون فارغا) وما على يساره . نقول أن الصورة formula_38 تنتج الصورة formula_42 في خطوة واحدة نرمز لها ب- formula_43 إذا خطوة الآلة بعد الصورة formula_38 نرى الصورة formula_42 أي انه : فلنفرض أنَّ formula_19 هو الرمز الأخير في السلسلة formula_47 ولنفرض أن formula_17 حينها formula_49 , اما بالنسبة ل-D فعندنا ثلاث حالات :
بشكل مشابه يمكن القول أن الصورة formula_38 تنتج الصورة formula_60 خلال k خطوات نرمز لها ب-formula_61 , ونقول أنَّ الصورة formula_62 تنتج الصورة formula_60 ونرمز لهذا ب- formula_64 إذا يوجد formula_65 بحيث يتحقق : formula_61 .
فلتكن M آلة تورنغ , لكل formula_67 مخطط الصور,G , هو مخطط الذي فيه كل رأس هو صورة آلة تورنغ M أثناء حساب x , ويوجد ضلع بين رأسين c ,c فقط إذا يمكن الوصول من c إلى c بخطوة حسابية واحدة .
لهذا المخطط أهمية كبيرة في نظرية التعقيد حيث أن له استخدامات عديدة من بينها في مبرهنة سافيتش , L⊆ NL , NL⊆ P , PSPACE ⊆EXP ...
فلتكن formula_68 لغة أي : مجموعة سلاسل من المركبة من رموز . ولتكن M آلة تورنغ بحيث أنه لكل formula_69 يتحقق التالي:
حينها نقول أنَّ M تقرر اللغة L , ونكتب formula_74 . نسمي L لغة عودية( recursive language) إذا يوجد آلة تورنغ تقررها . 
التعقيد هو تحديد أحد خصل الآلة لكل المُدخلات (مثل : الوقت أو كمية المساحة الاضافية) والتي نريد قياسها , كما في الخوارزميات كان هناك مقياس "النجاعة" هو وقت الخوارزمية ولعلنا أردنا في بعض المسائل تحديد كمية الوقت مثلا : في مسألة تصفيف الاعداد , يمكننا حل هذه المسألة بواسطة تصفيف الفقاعة بوقت (O(n بهذا نكون قد حصرنا الوقت وهكذا فاننا نعلم أن كل مُدخل لن يلزمه أكثر من هذا الوقت , وقياس وقت آلة تورنغ يكون بعد عدد الخطوات حتى توقف الآلة وإخراج النتيجة . بشكل رياضي : لتكن formula_75 دالة , نقول أن آلة تورنغ تعمل خلال وقت formula_76 إذا لكل مُدخل formula_77 الوقت (عدد خطوات الحساب أو بشكل مكافئ عدد الصور حتى الوصول لصورة نهائية) اللازم للالة M هو formula_78 (نرمز لطول x ب-|x| ). الدالة (f(n هي حد على وقت M .
هنالك عدة أنواع من الالات تورنغ أو الات شبيهة ولكن بالرغم من هذا فانه قد تبين أنَّ آلة تورنغ عمومية بما يكفي لتشمل هذه الأنواع من الالات هذه النظرة تبناها تورنغ وتشرتش في اطرحتهما المشهورة إذ انهما فرضا ان كل تعريف لمصطلح الخوارزمية من الناحية الرياضية مكافئ لالة تورنغ انفة الذكر , يعني ان كل نموذج حسابي يوجد آلة تورنغ التي تحاكي عمله واضف ان المسائل التي لا يمكن حلها بمساعدة آلة تورنغ حينها لا يمكن حلها بنموذج اخر الذي قد يكون أكثر تعقيدا . بالرغم من ان هذه الفرضية صعب جدا فحصها والتدقيق فيها ولكن كل نموذج حاسوبي تبين أنه مكافئ لالة تورنغ.
وهي آلة تورنغ كما عرفناها سابقا غير ان فيها اختلاف بسيط : بدل أن يكون هناك شريط مُدخل واحد هنالك عدة اشرطة , وهذا النموذج هو لمحاكاة الخوارزميات الموازية ولكن كما تم الذكر فان هذه الآلة يمكن محاكاتها بواسطة آلة تورنغ عادية . في الواقع إذا كان وقت عمل آلة تورنغ عديدة الاشرطة هو formula_76 حينها يمكن بناء آلة تورنغ مع شريط واحد 'M تحاكي الآلة M بحيث أنَّ وقتها هو formula_80 أو بكلمات أخرى كل ما نستطيع فعله مع آلة تورنغ عديد الاشرطة يمكن فعله أيضا مع آلة تورنغ بشريط واحد . 
بينما تنص اطروحة تشرتش على أن كل نموذج حسابي معقول مساوي لالة تورنغ مع فرق وقت كثير الحدود هذه الآلة , أي آلة تورنغ غير حتمية, يُعتقد بانها لا تحقق هذه الاطروحة حيث أنه حتى يومنا ما زالت مسألة محاكاة هذه الآلة هو الأصعب إذ انه لا يوجد الا محاكاة التي وقتها على آلة تورنغ أسية وهذا هو أساس المسألة الشهيرة NP≠P . 
آلة تورنغ غير حتمية هي رباعية formula_81 وهي قريبة جدا من الآلة العادية : formula_82 هي كما في السابق , ولكن الآن لا يوجد خيار واحد للانتقال ولكن مجموعة من الخيارات , وهذا نراه في أن formula_83 لم تعد دالة ولكن علاقة (relation) formula_84 .
الصورة هي ثلاثي كما عرفناه سابقا, غير انه الآن نقول أن formula_38 ينتج formula_42 في خطوة واحدة ونرمز لها ب- formula_87 إذا يوجد قانون في formula_83 الذي يجعل هذا ممكنا أي : يوجد تحرك formula_89 بحيث أنَّ :
يمكن محاكاة هذه الآلة بواسطة آلة تورنغ عادية (وحتى نفرق بينها يمكن تسميتها آلة تورنغ حتمية) ولكن الوقت اللازم للمحاكاة أُسي وحدسية NP≠P تقترح انه لا يوجد محاكاة كثيرة الحدود ما يعنيه انه قد يكون صعبا الاتيان بمحاكاة عملية .
هذا النوع من الالات ما هو الا توسيع لالة تورنغ العادية , وفي هذا النموذج تُعطى الآلة القدرة على حل مسألة ربما صعبة بخطوة حسابية واحدة , ولهذه الالات أهمية عظمى في نظرية التعقيد الحسابي إذ انه ينظر لهذا النوع من الالات على أنه اختصار (reduction) وقد تبين ان هذا التوسيع مُفيد جدا في كثير من التعريفات المهمة منها تعريف PCP , وهرم كثير الحدود , ... 
عندما خضنا في آلة تورنغ غير حتمية كان العامل الأساسي هناك هو "التحزر" أي حتى نعلم إذا ما مُدخل جوابه "نعم" تحزرنا مسار حسابي واذا كان المسار "نعم" اجبنا نعم وغير هذا عدنا وبحثنا من جديد . بشكل حدسي آلة تورنغ الاحتمالية تعتمد على عدد مسارات الحساب التي جوابها "نعم" وبناء على هذا فانه لو كان هنالك عدد كاف من مسارات الحساب التي جوابها نعم حينها إذا اخترنا بشكل عشوائي(هذه العملية تحتاج لمولد اعداد عشوائية حقيقية واحد هذه المولدات هو القاء قطعة نقدية "عادلة" غير منحازة ) مسار حساب فاننا قد نحصل وباحتمال كبير على مسار "نعم" , مقارنة هذه الالات بالة تورنغ غير حتمية هو سؤال أساسي في علم الحاسوب إذ انه لم يتم للان برهنة ان هذه الآلة مكافئة بقدرتها لالة تورنغ غير الحتمية , وفي نظرية التعقيد الحاسوبي هذا السؤال هو : هل formula_99 ؟ كما أنه لا يُعرف هل هذه الآلة اقوى من آلة تورنغ حتمية ولكن اغلب علماء الحاسوب يؤمنون بشدة ان هذه الالات مكافئة لالات تورنغ حتمية (أي ان العشوائية لا تساعد ) .
وهي آلة تورنغ التي هي نموذج للحساب كمومي بشكل رياضي , وهو فرع من الفيزياء , وهو يختلف عن النموذج العادي بانه يحتوي على كيوبت والذي هو عنده ثلاث حالات : 0,1 , 0 و1 معاً الحالة الأخيرة تسمى الحالة الفائقة . هذا النموذج لا يُعرف إذا ما يمكن محاكاته بواسطة حاسوب عادي ويعتقد أنها مهمة صعبة للغاية وقد تكون مستحيلة ! وهذا النموذج سطع نجمه عندما قدم بيتر شور خوارزمية لتحليل عدد لعوامله الأولية بوقت كثير الحدود بواسطة هذه الآلة .
بشكل واضح يمكن تمثيل آلة تورنغ على أنها سلسلة إذ انه يمكن كتابتها وبالتالي يمكن تحويل هذه الآلة إلى سلسلة 0 و- 1 , وهذه الملاحظة لها اهميتها العظمى على علم الحاسوب النظري والعملي إذ انه من دونها ما كان ليكون هناك حاسوب متعدد الاستخدامات . لكل آلة تورنغ حتى نستطيع تمثيلها بواسطة سلسلة سنقوم أيضا بتمثيل دالة الانتقال , كما أن كل formula_100 سيكون عبارة عن تمثيل لالة تورنغ , كما أن كل آلة تورنغ يوجد عدد لا نهائي من السلاسل التي تمثل هذه الآلة .
فلتكن M آلة تورنغ نرمز ب- formula_101 تمثيل الآلة M على أنها سلسلة . ولنفرض أنَّ formula_102 هي سلسلة حينها نكتب ان آلة تورنغ التي تمثلها formula_102 ب- formula_104 . 
هي آلة تورنغ التي تحاكي عمل الالات تورنغ , بشكل غير رسمي آلة تورنغ الكونية عملها مشابه لعمل المُصرف (compiler) حيث أنَّ مُدخل المُصرف برنامج بلغة برمجة مُعينة ويقوم بكتابة برنامج الحاسوب قادر على تنفيذه خطوة خطوة , بشكل رسمي : يوجد آلة تورنغ كونية formula_105 بحيث أنَّ لكل formula_106 , formula_107 . بالاضافة إذا formula_108 تتوقف خلال T خطوات على المُدخل x , حينها formula_109 تتوقف خلال formula_110 حيث أنَّ C هو عدد يتعلق بكبر أبجدية M وعدد الاشرطة وعدد الحالات .