آلة تورنغ

  لمعانٍ أخرى، طالع آلة (توضيح).

آلة تورنغ

معلومات عامة

صنف فرعي من	نموذج
البداية	1936
سُمِّي باسم	آلان تورنغ
المكتشف أو المخترع	آلان تورنغ
مكان الصنع	كلية الملك بلندن

آلة تورنغ هي نموذج نظري بسيط يحاكي طريقة عمل الحاسوب. سميت بهذا الاسم نسبة لعالم الرياضيات الإنجليزي آلان تورنغ الذي أوجد هذا النموذج سنة 1936م. هذا النموذج يعطي تعريفا رياضيا دقيقا للمصطلح خوارزم Algorithm, أهمية هذا النموذج تكمن في بساطته مقارنة بجهاز الحاسوب المعقد وبالرغم من ذلك فهو قادر على تنفيذ كل خوارزمية قابلة للتنفيذ بواسطة أي حاسوب متطور. لذلك يمكن معرفة إذا كانت عملية معينة قابلة للتنفيذ بواسطة الحاسوب أم لا عن طريق فحصها بواسطة آلة تورنغ. من هنا فإن لآلة تورنغ استعمال واسع في مجال دراسة قدرة الحاسوب والعمليات التي يمكنه أو لا يمكنه تنفيذها، وهو ما يسمى علم قابلية الحساب. يعتبر نموذج آلة التورينغ نموذج رياضياً بسيطاً للحاسوب وينمذج المقدرة الحسابية لحاسوب ذي وظائف عمومية وهو أيضاً من أهم اللغات الصورية إذ يقبل أوسع مجموعة منها وهي اللغات القابلة للعد عمودياً والتي يمكن توليدها بنماذج قواعدية من النوع صفر. يتألف النموذج الأساسي لآلة التورينغ من تحكم منته وشريط دخل منته من جهة واحدة هي جهة اليسار وغير منته من جهة اليمين ومقسم إلى عدة خلايا كل منها يحمل رمزاً واحداً من مجموعة منتهية تسمى «رموز الشريط» ورأس يسمى رأس القراءة والكتابة الذي يمر في كل مرة على خلية واحدة من الشريط. تحتوي الخلايا الn اليسارية من شريط الدخل (n عدد منته)في الحالة الابتدائية رموز الدخلفي حين تحتوي الخلايا المتبقة من الشريط رمزاً فارغاً.

تقوم آلة التورينغ في الحركة الواحدة واعتماداً على رمز الدخل المقروء من شريط الدخل وحالة التحكم المنتهي بالعمليات التالية:

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

تعريف

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

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

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

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

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

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

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

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

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

1. إذا $D=\to$ حينها 'w هي w غير أن الرمز الأخير في w الذي كان $\sigma$ بدلناه ليكون $\rho$ وأول رمز في u هو الرمز الحالي أي انَّ 'u هو u غير أن الرمز الأول في u قد حذف.
2. إذا $D=\gets$ حينها 'w هي w غير أن الرمز الأخير في w حُذف، و 'u هو u غير أننا اضفنا $\rho$ لبدايته.
3. إذا $D=-$ حينها 'w هي w غير أن الرمز الأخير في w الذي كان $\sigma$ بدلناه ليكون $\rho$ ولكن $u'=u$ .

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

مخطط الصور

فلتكن M آلة تورنغ، لكل $x\in \{0,1\}^{*}$ مخطط الصور،G_M,x , هو مخطط الذي فيه كل رأس هو صورة آلة تورنغ M أثناء حساب x , ويوجد ضلع بين رأسين c₁ ,c₂ فقط إذا يمكن الوصول من c₁ إلى c₂ بخطوة حسابية واحدة.

لهذا المخطط أهمية كبيرة في نظرية التعقيد حيث أن له استخدامات عديدة من بينها في مبرهنة سافيتش، L⊆ NL , NL⊆ P , PSPACE ⊆EXP ...

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

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

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

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

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

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

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

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

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

وهي آلة تورنغ كما عرفناها سابقا غير ان فيها اختلاف بسيط: بدل أن يكون هناك شريط مُدخل واحد هنالك عدة اشرطة، وهذا النموذج هو لمحاكاة الخوارزميات الموازية ولكن كما تم الذكر فان هذه الآلة يمكن محاكاتها بواسطة آلة تورنغ عادية. في الواقع إذا كان وقت عمل آلة تورنغ عديدة الاشرطة هو $f(n)$ حينها يمكن بناء آلة تورنغ مع شريط واحد 'M تحاكي الآلة M بحيث أنَّ وقتها هو $O(f^{2}(n))$ أو بكلمات أخرى كل ما نستطيع فعله مع آلة تورنغ عديد الاشرطة يمكن فعله أيضا مع آلة تورنغ بشريط واحد.

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

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

تعريف

آلة تورنغ غير حتمية هي رباعية $N=(K,\Sigma ,\Delta ,{\mathcal {(}}S))$ وهي قريبة جدا من الآلة العادية: $K,\Sigma ,{\mathcal {(}}S)$ هي كما في السابق، ولكن الآن لا يوجد خيار واحد للانتقال ولكن مجموعة من الخيارات، وهذا نراه في أن $\Delta$ لم تعد دالة ولكن علاقة (relation) $\Delta \subset K\times \Sigma \to (K\cup \{h,yes,no\})\times \Sigma \times \{\to ,\gets ,-\}$ .

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

الصورة هي ثلاثي كما عرفناه سابقا، غير انه الآن نقول أن $(q,w,u)$ ينتج $(q',w',u')$ في خطوة واحدة ونرمز لها ب- $(q,w,u){\xrightarrow {N}}(q',w',u')$ إذا يوجد قانون في $\Delta$ الذي يجعل هذا ممكنا أي: يوجد تحرك $((q,\sigma ),(q',\rho ,D))\in \Delta$ بحيث أنَّ:

1. إذا $D=\to$ حينها 'w هي w غير أن الرمز الأخير في w الذي كان $\sigma$ بدلناه ليكون $\rho$ وأول رمز في u هو الرمز الحالي أي انَّ 'u هو u غير أن الرمز الأول في u قد حذف.
2. إذا $D=\gets$ حينها 'w هي w غير أن الرمز الأخير في w حُذف، و 'u هو u غير أننا اضفنا $\rho$ لبدايته.
3. إذا $D=-$ حينها 'w هي w غير أن الرمز الأخير في w الذي كان $\sigma$ بدلناه ليكون $\rho$ ولكن $u'=u$ .

محاكاة الآلة

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

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

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

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

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

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

المقالة الرئيسة: آلة تورنغ الكمومية

وهي آلة تورنغ التي هي نموذج للحساب كمومي بشكل رياضي، وهو فرع من الفيزياء، وهو يختلف عن النموذج العادي بانه يحتوي على كيوبت والذي هو عنده ثلاث حالات: 0,1 , 0 و1 معاً الحالة الأخيرة تسمى الحالة الفائقة. هذا النموذج لا يُعرف إذا ما يمكن محاكاته بواسطة حاسوب عادي ويعتقد أنها مهمة صعبة للغاية وقد تكون مستحيلة ! وهذا النموذج سطع نجمه عندما قدم بيتر شور خوارزمية لتحليل عدد لعوامله الأولية بوقت كثير الحدود بواسطة هذه الآلة.

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

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

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

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

هي آلة تورنغ التي تحاكي عمل الالات تورنغ، بشكل غير رسمي آلة تورنغ الكونية عملها مشابه لعمل المُصرف (compiler) حيث أنَّ مُدخل المُصرف برنامج بلغة برمجة مُعينة ويقوم بكتابة برنامج الحاسوب قادر على تنفيذه خطوة خطوة، بشكل رسمي: يوجد آلة تورنغ كونية ${\mathcal {U}}$ بحيث أنَّ لكل $x,\alpha \in \{0,1\}^{*}$ , ${\mathcal {U}}(x,\alpha )=M_{\alpha }(x)$ . بالإضافة إذا $M_{\alpha }$ تتوقف خلال T خطوات على المُدخل x , حينها ${\mathcal {U}}(x,\alpha )$ تتوقف خلال $C\cdot T\cdot log(T)$ حيث أنَّ C هو عدد يتعلق بكبر أبجدية M وعدد الاشرطة وعدد الحالات.

انظر أيضا

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

مراجع

• Christos H. Papadimitriou , "Computational complexity"
• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing.