books آلة تورنغ غير حتمية
If you do not find what you're looking for, you can use more accurate words.
آلة تورنغ غير حتمية (Info)
بينما تنص اطروحة تشرتش على أن كل نموذج حسابي معقول مساوي لالة تورنغ مع فرق وقت كثير الحدود هذه الآلة، أي آلة تورنغ غير حتمية، يُعتقد بانها لا تحقق هذه الاطروحة حيث أنه حتى يومنا ما زالت مسألة محاكاة هذه الآلة هو الأصعب إذ انه لا يوجد الا محاكاة التي وقتها على آلة تورنغ أسية وهذا هو أساس المسألة الشهيرة NP≠P .
تعريف
آلة تورنغ غير حتمية هي رباعية وهي قريبة جدا من الآلة العادية : هي كما في السابق، ولكن الآن لا يوجد خيار واحد للانتقال ولكن مجموعة من الخيارات، وهذا نراه في أن لم تعد دالة ولكن علاقة (relation) .
صورة آلة تورنغ غير حتمية
الصورة هي ثلاثي كما عرفناه سابقا، غير انه الآن نقول أن ينتج في خطوة واحدة ونرمز لها ب- إذا يوجد قانون في الذي يجعل هذا ممكنا أي : يوجد تحرك بحيث أنَّ :
- إذا حينها "w هي w غير أن الرمز الأخير في w الذي كان بدلناه ليكون وأول رمز في u هو الرمز الحالي أي انَّ "u هو u غير أن الرمز الأول في u قد حذف .
- إذا حينها "w هي w غير أن الرمز الأخير في w حُذف، و "u هو u غير أننا اضفنا لبدايته .
- إذا حينها "w هي w غير أن الرمز الأخير في w الذي كان بدلناه ليكون ولكن .
محاكاة الآلة
يمكن محاكاة هذه الآلة بواسطة آلة تورنغ عادية (وحتى نفرق بينها يمكن تسميتها آلة تورنغ حتمية) ولكن الوقت اللازم للمحاكاة أُسي وحدسية NP≠P تقترح انه لا يوجد محاكاة كثيرة الحدود ما يعنيه انه قد يكون صعبا الاتيان بمحاكاة عملية .
