آلة تورنغ

من الناحية الرياضية آلة تورنغ هي رباعية ${\displaystyle {\mbox{M}}=(K,\Sigma ,\delta ,{\mathcal {S}})}$ حيث أن ${\displaystyle K}$ هي مجموعة نهائية من الحالات (states), ${\displaystyle \Sigma }$ هي مجموعة نهائية من الرموز وعادة ما تُسمى هذه المجموعة أبجدية M . سنفرض أنَّ ${\displaystyle \Sigma \cap K=\emptyset }$ , ${\displaystyle \Sigma }$ دائما يحتوي على رمزين خاصين هما رمز البداية (${\displaystyle \vartriangleright }$) ورمز الفراغ (${\displaystyle \sqcup }$), ${\displaystyle \delta }$ هي دالة الانتقال أي ${\displaystyle \delta :K\times \Sigma \to (K\cup \{h,yes,no\})\times \Sigma \times \{\to ,\gets ,-\}}$ في حين أنَّ h هو حالة التوقف و-"yes" هي حالة القبول و-"no" هي حالة الرفض. ومؤشرات الاتجاه ${\displaystyle \to }$ تعني تحرك يمينا و- ${\displaystyle \gets }$ تحرك يسارا و- ${\displaystyle -}$ معناه لا تتحرك وهذه المؤشرات ليست ضمن المجموعة: ${\displaystyle \Sigma \cup K}$ .

يمكن اعتبار ${\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 }$ دائما يوجه المؤشر إلى اليمين ولا يمحى ابدا.

البرنامج يبدأ في الحالية الابتدائية ${\displaystyle {\mathcal {(}}S)}$ . السلسلة تُهيئ فيكون في أولها الرمز ${\displaystyle \vartriangleright }$ ويتبعه سلسلة طولها نهائي: ${\displaystyle x\in (\Sigma -\{\sqcup \})^{*}}$ ونسمي x مُدخل الآلة. في البداية المؤشر يؤشر على بداية المُدخل وبشكل عام هو ${\displaystyle \vartriangleright }$ . من هذه الصورة (configuration) الأولية الآلة تتحرك حسب ${\displaystyle \delta }$ وخلال هذا يتغير الحال وتطبع الآلة المُخرج وتحرك المؤشر وبعدها تتحرك خطوة أخرى وعلى هذا المنوال...

كما ذكرنا سالفا بالنسبة ${\displaystyle \delta (q,\vartriangleright )}$ فانه لا يمكن للمؤشر ان «يقع يسارا» أي أنه دوما سيتحرك المؤشر ضمن نطاق تواجد سلسلة المُدخل. اما بالنسبة لليمين فان نهاية السلسلة تكون عندما يصل المؤشر إلى الرمز ${\displaystyle \sqcup }$ حينها يمكنه إعادة كتابة المحتوى هكذا السلسلة تصبح أطول ولا يمكنها ان تصبح أقصر وهذه صفة مهمة لان الآلة مُعدة لتقوم بحسابات بشكل عام.

تتوقف الآلة عندما تصل إلى واحد من ثلاث حالات التوقف وهي "yes", "no", h والتي تم ذكرها انفا، عندما تصل إلى هذه الحالة نقول ان الآلة توقفت. ونقول ان الآلة «قبلت» المدخل إذا توقفت في الحال "yes" اما إذا توقفت على الحال "no" فاننا نقول ان الآلة «رفضت» المُدخل. نرمز للمُخرج الآلة ${\displaystyle M(x)}$ لذا فانه في حال قبلت أو رفضت الآلة المُدخل ${\displaystyle M(x)=yes\ {\mbox{or}}\ no}$ حسب الجواب.

إذا دخلت الآلة حالة التوقف حينها السلسلة التي تبدأ من الرمز ${\displaystyle \vartriangleright }$ حتى الرمز الفارغ نقول انها سلسلة المُخرج (أو باختصار المُخرج) نرمز لها ب-y حينها نكتب ${\displaystyle M(x)=y}$ للدلالة على أنها المُخرج، في بعض الأحيان قد لا تتوقف الآلة M عندما المُدخل يكون x وحينها نكتب: ${\displaystyle M(x)=\nearrow }$ .

بشكل عام لوصف الفعالية لالات تورنغ نستخدم بشكل عام مصطلح «صورة»(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 فعندنا ثلاث حالات:

1. إذا ${\displaystyle D=\to }$ حينها 'w هي w غير أن الرمز الأخير في w الذي كان ${\displaystyle \sigma }$ بدلناه ليكون ${\displaystyle \rho }$ وأول رمز في u هو الرمز الحالي أي انَّ 'u هو u غير أن الرمز الأول في u قد حذف.
2. إذا ${\displaystyle D=\gets }$ حينها 'w هي w غير أن الرمز الأخير في w حُذف، و 'u هو u غير أننا اضفنا ${\displaystyle \rho }$ لبدايته.
3. إذا ${\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)}$ تنتج الصورة ${\displaystyle (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')}$ .

فلتكن ${\displaystyle L\subset (\Sigma -\{\sqcup \})^{*}}$ لغة أي: مجموعة سلاسل من المركبة من رموز. ولتكن M آلة تورنغ بحيث أنه لكل ${\displaystyle x\in (\Sigma -\{\sqcup \})^{*}}$ يتحقق التالي:

• إذا ${\displaystyle x\in L}$ حينها: ${\displaystyle M(x)={\text{``yes''}}}$
• إذا ${\displaystyle x\notin L}$ حينها: ${\displaystyle M(x)={\text{``no''}}}$

حينها نقول أنَّ M تقرر اللغة L , ونكتب ${\displaystyle L(M)=L}$ . نسمي L لغة عودية (recursive language) إذا يوجد آلة تورنغ تقررها.

التعقيد هو تحديد أحد خصل الآلة لكل المُدخلات (مثل: الوقت أو كمية المساحة الاضافية) والتي نريد قياسها، كما في الخوارزميات كان هناك مقياس «النجاعة» هو وقت الخوارزمية ولعلنا أردنا في بعض المسائل تحديد كمية الوقت مثلا: في مسألة تصفيف الاعداد، يمكننا حل هذه المسألة بواسطة تصفيف الفقاعة بوقت (O(n² بهذا نكون قد حصرنا الوقت وهكذا فاننا نعلم أن كل مُدخل لن يلزمه أكثر من هذا الوقت، وقياس وقت آلة تورنغ يكون بعد عدد الخطوات حتى توقف الآلة وإخراج النتيجة. بشكل رياضي: لتكن ${\displaystyle f:\mathbb {N} \to \mathbb {N} }$ دالة، نقول أن آلة تورنغ تعمل خلال وقت ${\displaystyle f(n)}$ إذا لكل مُدخل ${\displaystyle x}$ الوقت (عدد خطوات الحساب أو بشكل مكافئ عدد الصور حتى الوصول لصورة نهائية) اللازم للالة M هو ${\displaystyle f(|x|)}$ (نرمز لطول x ب-|x|). الدالة (f(n هي حد على وقت M .

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

بشكل واضح يمكن تمثيل آلة تورنغ على أنها سلسلة إذ انه يمكن كتابتها وبالتالي يمكن تحويل هذه الآلة إلى سلسلة 0 و- 1 , وهذه الملاحظة لها اهميتها العظمى على علم الحاسوب النظري والعملي إذ انه من دونها ما كان ليكون هناك حاسوب متعدد الاستخدامات. لكل آلة تورنغ حتى نستطيع تمثيلها بواسطة سلسلة سنقوم أيضا بتمثيل دالة الانتقال، كما أن كل ${\displaystyle x\in {0,1}^{*}}$ سيكون عبارة عن تمثيل لالة تورنغ، كما أن كل آلة تورنغ يوجد عدد لا نهائي من السلاسل التي تمثل هذه الآلة.

فلتكن M آلة تورنغ نرمز ب- ${\displaystyle \llcorner M\lrcorner }$ تمثيل الآلة M على أنها سلسلة. ولنفرض أنَّ ${\displaystyle \alpha }$ هي سلسلة حينها نكتب ان آلة تورنغ التي تمثلها ${\displaystyle \alpha }$ ب- ${\displaystyle M_{\alpha }}$ .

• خوارزمية
• آلة تورنغ الكمومية
• هيكلة فون نيومان
• كلود شانون
• قسم تعقيد
• نظرية التعقيد الحسابي.
• مسألة P=NP
• نظرية الحاسوبية

• بوابة رياضيات
• بوابة علم الحاسوب