آلة تورنج

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

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



محتويات [أخف]
1 تعريف
2 طريقة عمل الالة
3 صورة آلة تيورنج 3.1 مخطط الصور

4 لغات آلة تيورنج
5 مقاييس التعقيد
6 انواع الات تيورنج 6.1 آلة تيورنج عديدة الاشرطة
6.2 آلة تيورنج غير حتمية 6.2.1 تعريف
6.2.2 صورة آلة تيورنج غير حتمية
6.2.3 محاكاة الالة

6.3 آلة تيورنج مع اوركل
6.4 آلة تيورنج احتمالية
6.5 آلة تيورنج كمومية

7 الالات تيورنج على انها سلاسل والة تيورنج الكونية 7.1 آلة تيورنج الكونية

8 انظر أيضا
9 مراجع


تعريف[عدل]


Model of a Turing machine.jpg



من الناحية الرياضية آلة تيورنج هي رباعية \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\ge 0 بحيث يتحقق : (q,w,u) \overset{\underset{\mathrm{M^k}}{}}{\to} (q',w',u') .

مخطط الصور[عدل]

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

لهذا المخطط اهمية كبيرة في نظرية التعقيد حيث ان له استخدامات عديدة من بينها في مبرهنة سافيتش , 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(n2 بهذا نكون قد حصرنا الوقت وهكذا فاننا نعلم ان كل مُدخل لن يلزمه أكثر من هذا الوقت , وقياس وقت آلة تيورنج يكون بعد عدد الخطوات حتى توقف الالة واخراج النتيجة . بشكل رياضي : لتكن 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 ؟ كما انه لا يُعرف هل هذه الالة اقوى من آلة تيورنج حتمية ولكن اغلب علماء الحاسوب يؤمنون بشدة ان هذه الالات مكافئة لالات تيورنج حتمية (اي ان العشوائية لا تساعد ) .

آلة تيورنج كمومية[عدل]

Crystal Clear app kdict.png مقالة مفصلة: آلة تورنج الكمومية

وهي آلة تيورنج التي هي نموذج للحساب كمومي بشكل رياضي , وهو فرع من الفيزياء , وهو يختلف عن النموذج العادي بانه يحتوي على كيوبت والذي هو عنده ثلاث حالات : 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 وعدد الاشرطة وعدد الحالات