كتب turing machine
اذا لم تجد ما تبحث عنه يمكنك استخدام كلمات أكثر دقة.
آلة تورنغ (معلومة)
آلة تورنغ هي نموذج نظري بسيط يحاكي طريقة عمل الحاسوب. سميت بهذا الاسم نسبة لعالم الرياضيات الإنجليزي آلان تورنغ الذي أوجد هذا النموذج سنة 1936م. هذا النموذج يعطي تعريفا رياضيا دقيقا للمصطلح خوارزم Algorithm, أهمية هذا النموذج تكمن في بساطته مقارنة بجهاز الحاسوب المعقد وبالرغم من ذلك فهو قادر على تنفيذ كل خوارزمية قابلة للتنفيذ بواسطة أي حاسوب متطور. لذلك يمكن معرفة إذا كانت عملية معينة قابلة للتنفيذ بواسطة الحاسوب أم لا عن طريق فحصها بواسطة آلة تورنغ. من هنا فإن لآلة تورنغ استعمال واسع في مجال دراسة قدرة الحاسوب والعمليات التي يمكنه أو لا يمكنه تنفيذها، وهو ما يسمى علم قابلية الحساب. يعتبر نموذج آلة التورينغ نموذج رياضياً بسيطاً للحاسوب وينمذج المقدرة الحسابية لحاسوب ذي وظائف عمومية وهو أيضاً من أهم اللغات الصورية إذ يقبل أوسع مجموعة منها وهي اللغات القابلة للعد عمودياً والتي يمكن توليدها بنماذج قواعدية من النوع صفر. يتألف النموذج الأساسي لآلة التورينغ من تحكم منته وشريط دخل منته من جهة واحدة هي جهة اليسار وغير منته من جهة اليمين ومقسم إلى عدة خلايا كل منها يحمل رمزاً واحداً من مجموعة منتهية تسمى "رموز الشريط" ورأس يسمى رأس القراءة والكتابة الذي يمر في كل مرة على خلية واحدة من الشريط. تحتوي الخلايا الn اليسارية من شريط الدخل (n عدد منته)في الحالة الابتدائية رموز الدخلفي حين تحتوي الخلايا المتبقة من الشريط رمزاً فارغاً.
تقوم آلة التورينغ في الحركة الواحدة واعتماداً على رمز الدخل المقروء من شريط الدخل وحالة التحكم المنتهي بالعمليات التالية:
وهي آلة تورنغ التي هي نموذج للحساب كمومي بشكل رياضي، وهو فرع من الفيزياء، وهو يختلف عن النموذج العادي بانه يحتوي على كيوبت والذي هو عنده ثلاث حالات : 0,1 , 0 و1 معاً الحالة الأخيرة تسمى الحالة الفائقة . هذا النموذج لا يُعرف إذا ما يمكن محاكاته بواسطة حاسوب عادي ويعتقد أنها مهمة صعبة للغاية وقد تكون مستحيلة ! وهذا النموذج سطع نجمه عندما قدم بيتر شور خوارزمية لتحليل عدد لعوامله الأولية بوقت كثير الحدود بواسطة هذه الآلة .
الالات تورنغ على انها سلاسل وآلة تورنغ الكونية
بشكل واضح يمكن تمثيل آلة تورنغ على أنها سلسلة إذ انه يمكن كتابتها وبالتالي يمكن تحويل هذه الآلة إلى سلسلة 0 و- 1 , وهذه الملاحظة لها اهميتها العظمى على علم الحاسوب النظري والعملي إذ انه من دونها ما كان ليكون هناك حاسوب متعدد الاستخدامات . لكل آلة تورنغ حتى نستطيع تمثيلها بواسطة سلسلة سنقوم أيضا بتمثيل دالة الانتقال، كما أن كل سيكون عبارة عن تمثيل لالة تورنغ، كما أن كل آلة تورنغ يوجد عدد لا نهائي من السلاسل التي تمثل هذه الآلة .
فلتكن M آلة تورنغ نرمز ب- تمثيل الآلة M على أنها سلسلة . ولنفرض أنَّ هي سلسلة حينها نكتب ان آلة تورنغ التي تمثلها ب- .
آلة تورنغ الكونية
هي آلة تورنغ التي تحاكي عمل الالات تورنغ، بشكل غير رسمي آلة تورنغ الكونية عملها مشابه لعمل المُصرف (compiler) حيث أنَّ مُدخل المُصرف برنامج بلغة برمجة مُعينة ويقوم بكتابة برنامج الحاسوب قادر على تنفيذه خطوة خطوة، بشكل رسمي : يوجد آلة تورنغ كونية بحيث أنَّ لكل , . بالإضافة إذا تتوقف خلال T خطوات على المُدخل x , حينها تتوقف خلال حيث أنَّ C هو عدد يتعلق بكبر أبجدية M وعدد الاشرطة وعدد الحالات .
