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