آلة تورينج غير الحتمية

في علم الحاسوب النظري ونظرية الحوسبة ، تُعدّ آلة تورينغ غير الحتمية ( NTM ) نموذجًا نظريًا للحوسبة، حيث تحدد قواعدها الحاكمة أكثر من إجراء ممكن في بعض الحالات المعطاة. أي أن الحالة التالية لآلة تورينغ غير الحتمية لا تتحدد بشكل كامل بفعلها والرمز الحالي الذي تراه، على عكس آلة تورينغ الحتمية التقليدية .

تُستخدم نماذج NTM أحيانًا في التجارب الفكرية لدراسة قدرات الحواسيب وحدودها. ومن أهم المشكلات المفتوحة في علم الحاسوب النظري مشكلة P مقابل NP ، والتي تتعلق (من بين صياغات مكافئة أخرى) بمدى صعوبة محاكاة الحساب غير الحتمي باستخدام حاسوب حتمي.

ابتكر آلان تورينج مفهوم آلة تورينج عام 1936، متخيلاً إياها كحاسوب بسيط يقرأ ويكتب الرموز على شريط لا نهائي، رمزًا تلو الآخر، باتباع مجموعة محددة مسبقًا من القواعد. تحدد الآلة الإجراء الذي يجب عليها القيام به تاليًا بناءً على حالتها الداخلية والرمز الذي تراه حاليًا . على سبيل المثال، قد تكون إحدى قواعد آلة تورينج كالتالي: "إذا كنت في الحالة 2 ورأيت الرمز 'A'، فغيّره إلى 'B'، ثم انتقل إلى اليسار، وانتقل إلى الحالة 3."

على عكس آلة تورينغ الحتمية، في آلة تورينغ غير الحتمية ، قد تحدد مجموعة القواعد أكثر من إجراء واحد يجب تنفيذه في أي موقف معين. على سبيل المثال، قد يسمح وجود علامة X على الشريط في الحالة 3 لآلة تورينغ غير الحتمية بما يلي:

• اكتب حرف Y، ثم تحرك إلى اليمين، وانتقل إلى الحالة 5

أو

• اكتب علامة X، ثم تحرك إلى اليسار، وابقى في الحالة 3.

نظرًا لإمكانية وجود عدة إجراءات تترتب على موقف معين، فإنه يمكن أن توجد عدة تسلسلات ممكنة من الخطوات التي يمكن أن تتخذها آلة تورينج العصبية (NTM) انطلاقًا من مدخل معين. إذا أدى أحد هذه التسلسلات الممكنة على الأقل إلى حالة "قبول"، يُقال إن آلة تورينج العصبية قد قبلت المدخل. بينما تتبع آلة تورينج الرقمية (DTM) "مسار حسابي" واحد، فإن آلة تورينج العصبية (NTM) لديها " شجرة حسابية ".

يمكن تعريف آلة تورينج غير الحتمية رسميًا على أنها مجموعة سداسية.${\displaystyle M=(Q,\Sigma ,\iota ,\sqcup ,A,\delta )}$، أين

• ${\displaystyle Q}$هي مجموعة محدودة من الحالات
• ${\displaystyle \Sigma }$هي مجموعة محدودة من الرموز (أبجدية الشريط)
• ${\displaystyle \iota \in Q}$هي الحالة الأولية
• ${\displaystyle \sqcup \in \Sigma }$هو رمز الفراغ
• ${\displaystyle A\subseteq Q}$هي مجموعة الحالات المقبولة (النهائية)
• ${\displaystyle \delta \subseteq \left(Q\backslash A\times \Sigma \right)\times \left(Q\times \Sigma \times \{L,S,R\}\right)}$هي علاقة بين الحالات والرموز تسمى علاقة الانتقال .${\displaystyle L}$الحركة إلى اليسار،${\displaystyle S}$لا يوجد أي تحرك، و${\displaystyle R}$الحركة إلى اليمين.

الفرق مع آلة تورينج القياسية (الحتمية) هو أنه بالنسبة لآلات تورينج الحتمية، فإن علاقة الانتقال هي دالة وليست مجرد علاقة.

تُشابه التكوينات وعلاقة النتائج بينها، التي تصف الإجراءات الممكنة لآلة تورينج بناءً على أي محتوى محتمل للشريط، تلك الموجودة في آلات تورينج القياسية، باستثناء أن علاقة النتائج لم تعد أحادية القيمة. (إذا كانت الآلة حتمية، فإن العمليات الحسابية الممكنة هي جميعها بادئات لمسار واحد، قد يكون لانهائيًا).

يتم توفير المدخلات لآلة NTM بنفس الطريقة التي يتم بها توفير المدخلات لآلة تورينج الحتمية: يتم تشغيل الآلة في التكوين الذي يكون فيه رأس الشريط على الحرف الأول من السلسلة (إن وجد)، ويكون الشريط فارغًا تمامًا فيما عدا ذلك.

تقبل آلة تورينج غير خطية (NTM) سلسلة إدخال إذا وفقط إذا كان أحد المسارات الحسابية الممكنة التي تبدأ من تلك السلسلة يضع الآلة في حالة قبول. عند محاكاة مسارات التفرع المتعددة لآلة تورينج غير خطية على آلة حتمية، يمكننا إيقاف المحاكاة بالكامل بمجرد وصول أي فرع إلى حالة قبول.

أي مسألة حسابية يمكن حلها باستخدام آلة تورينج المنفصلة (DTM) يمكن حلها أيضًا باستخدام آلة تورينج غير الخطية (NTM)، والعكس صحيح. ومع ذلك، يُعتقد عمومًا أن التعقيد الزمني قد لا يكون متطابقًا.

تتمتع آلة تورينج غير الخطية (NTM) بخاصية عدم الحتمية المحدودة. بمعنى آخر، إذا توقفت آلة تورينج غير الخطية دائمًا عند شريط إدخال معين T ، فإنها تتوقف في عدد محدود من الخطوات، وبالتالي لا يمكن أن يكون لها إلا عدد محدود من التكوينات الممكنة.

نظرًا لأن الحواسيب الكمومية تستخدم بتات كمومية ، والتي يمكن أن تكون في تراكبات من الحالات، بدلًا من البتات التقليدية، يسود أحيانًا اعتقاد خاطئ بأنها آلات غير محوِّلة. ^{[ 4 ]} ومع ذلك، يعتقد الخبراء (وإن لم يُثبت ذلك) أن قدرة الحواسيب الكمومية لا تُقارن بقدرة الآلات غير المحوِّلة؛ أي أنه من المحتمل وجود مسائل يمكن للآلة غير المحوِّلة حلها بكفاءة بينما تعجز الحواسيب الكمومية عن حلها، والعكس صحيح. [ ^{5 ] وعلى} وجه الخصوص، من المرجح أن تكون المسائل الكاملة من فئة NP قابلة للحل بواسطة الآلات غير المحوِّلة، ولكن ليس بواسطة الحواسيب الكمومية، في وقت متعدد الحدود.

بصورة بديهية، بينما يمكن للحاسوب الكمومي أن يكون في حالة تراكب تتوافق مع تنفيذ جميع الفروع الحسابية الممكنة في الوقت نفسه (على غرار آلة تورينغ غير الخطية)، فإن القياس النهائي سيؤدي إلى انهيار الحاسوب الكمومي إلى فرع مُختار عشوائيًا. وبالتالي، لا يُمثل هذا الفرع، في الغالب، الحل المنشود، على عكس آلة تورينغ غير الخطية، التي يُسمح لها باختيار الحل الصحيح من بين عدد هائل من الفروع.

• آلة تورينج الاحتمالية
• بي سبيس

• برنامج محاكاة بلغة C++ لآلة تورينج متعددة الأشرطة غير الحتمية (برنامج مجاني).
• رابط تحميل برنامج محاكاة آلة تورينغ متعددة الأشرطة غير الحتمية بلغة C++ من موقع sourceforge.net