كتب انواع الات تورنغ
اذا لم تجد ما تبحث عنه يمكنك استخدام كلمات أكثر دقة.
انواع الات تورنغ (معلومة)
هنالك عدة أنواع من الالات تورنغ أو الات شبيهة ولكن بالرغم من هذا فانه قد تبين أنَّ آلة تورنغ عمومية بما يكفي لتشمل هذه الأنواع من الالات هذه النظرة تبناها تورنغ وتشرتش في اطرحتهما المشهورة إذ انهما فرضا ان كل تعريف لمصطلح الخوارزمية من الناحية الرياضية مكافئ لالة تورنغ انفة الذكر، يعني ان كل نموذج حسابي يوجد آلة تورنغ التي تحاكي عمله واضف ان المسائل التي لا يمكن حلها بمساعدة آلة تورنغ حينها لا يمكن حلها بنموذج اخر الذي قد يكون أكثر تعقيدا . بالرغم من ان هذه الفرضية صعب جدا فحصها والتدقيق فيها ولكن كل نموذج حاسوبي تبين أنه مكافئ لالة تورنغ.
آلة تورنغ عديدة الاشرطة
وهي آلة تورنغ كما عرفناها سابقا غير ان فيها اختلاف بسيط : بدل أن يكون هناك شريط مُدخل واحد هنالك عدة اشرطة، وهذا النموذج هو لمحاكاة الخوارزميات الموازية ولكن كما تم الذكر فان هذه الآلة يمكن محاكاتها بواسطة آلة تورنغ عادية . في الواقع إذا كان وقت عمل آلة تورنغ عديدة الاشرطة هو حينها يمكن بناء آلة تورنغ مع شريط واحد "M تحاكي الآلة M بحيث أنَّ وقتها هو أو بكلمات أخرى كل ما نستطيع فعله مع آلة تورنغ عديد الاشرطة يمكن فعله أيضا مع آلة تورنغ بشريط واحد .
آلة تورنغ غير حتمية
بينما تنص اطروحة تشرتش على أن كل نموذج حسابي معقول مساوي لالة تورنغ مع فرق وقت كثير الحدود هذه الآلة، أي آلة تورنغ غير حتمية، يُعتقد بانها لا تحقق هذه الاطروحة حيث أنه حتى يومنا ما زالت مسألة محاكاة هذه الآلة هو الأصعب إذ انه لا يوجد الا محاكاة التي وقتها على آلة تورنغ أسية وهذا هو أساس المسألة الشهيرة NP≠P .
تعريف
آلة تورنغ غير حتمية هي رباعية وهي قريبة جدا من الآلة العادية : هي كما في السابق، ولكن الآن لا يوجد خيار واحد للانتقال ولكن مجموعة من الخيارات، وهذا نراه في أن لم تعد دالة ولكن علاقة (relation) .
صورة آلة تورنغ غير حتمية
الصورة هي ثلاثي كما عرفناه سابقا، غير انه الآن نقول أن ينتج في خطوة واحدة ونرمز لها ب- إذا يوجد قانون في الذي يجعل هذا ممكنا أي : يوجد تحرك بحيث أنَّ :
وهي آلة تورنغ التي هي نموذج للحساب كمومي بشكل رياضي، وهو فرع من الفيزياء، وهو يختلف عن النموذج العادي بانه يحتوي على كيوبت والذي هو عنده ثلاث حالات : 0,1 , 0 و1 معاً الحالة الأخيرة تسمى الحالة الفائقة . هذا النموذج لا يُعرف إذا ما يمكن محاكاته بواسطة حاسوب عادي ويعتقد أنها مهمة صعبة للغاية وقد تكون مستحيلة ! وهذا النموذج سطع نجمه عندما قدم بيتر شور خوارزمية لتحليل عدد لعوامله الأولية بوقت كثير الحدود بواسطة هذه الآلة .
