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

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

في حالة تساوي احتمالات الانتقالات، يمكن تعريف آلات تورينغ الاحتمالية على أنها آلات تورينغ حتمية مزودة بتعليمات "كتابة" إضافية، حيث تتوزع قيمة الكتابة بشكل منتظم في أبجدية آلة تورينغ (بشكل عام، احتمال متساوٍ لكتابة "1" أو "0" على الشريط). وهناك صياغة شائعة أخرى تتمثل ببساطة في آلة تورينغ حتمية مزودة بشريط إضافي مليء ببتات عشوائية يُسمى "الشريط العشوائي".

الحاسوب الكمومي (أو آلة تورينج الكمومية ) هو نموذج آخر للحوسبة وهو احتمالي بطبيعته .

آلة تورينج الاحتمالية هي نوع من آلات تورينج غير الحتمية حيث تكون كل خطوة غير حتمية بمثابة "رمية عملة"، أي أنه في كل خطوة توجد حركتان محتملتان تالية، وتقوم آلة تورينج باختيار الحركة التي ستتخذها بشكل احتمالي. ^{[ 1 ]}

يمكن تعريف آلة تورينج الاحتمالية رسميًا على أنها سباعية الترتيب${\displaystyle M=(Q,\Sigma ,\Gamma ,q_{0},A,\delta _{1},\delta _{2})}$، أين

• ${\displaystyle Q}$هي مجموعة محدودة من الحالات
• ${\displaystyle \Sigma }$الأبجدية المدخلة
• ${\displaystyle \Gamma }$هي أبجدية شريطية، تتضمن الرمز الفارغ #
• ${\displaystyle q_{0}\in Q}$هي الحالة الأولية
• ${\displaystyle A\subseteq Q}$هي مجموعة الحالات المقبولة (النهائية)
• ${\displaystyle \delta _{1}:Q\times \Gamma \to Q\times \Gamma \times \{L,R\}}$هي دالة الانتقال الاحتمالية الأولى.${\displaystyle L}$هي حركة خلية واحدة إلى اليسار على شريط آلة تورينج و${\displaystyle R}$هي حركة خلية واحدة إلى اليمين.
• ${\displaystyle \delta _{2}:Q\times \Gamma \to Q\times \Gamma \times \{L,R\}}$هي دالة الانتقال الاحتمالية الثانية.

في كل خطوة، تقوم آلة تورينج بتطبيق دالة الانتقال بشكل احتمالي${\displaystyle \delta _{1}}$أو دالة الانتقال${\displaystyle \delta _{2}}$[ ^{2 ]} يتم هذا الاختيار بشكل مستقل عن جميع الاختيارات السابقة. وبهذه الطريقة، تشبه عملية اختيار دالة الانتقال في كل خطوة من خطوات الحساب عملية رمي عملة معدنية ^.

يُدخل الاختيار الاحتمالي لدالة الانتقال في كل خطوة خطأً في آلة تورينج؛ أي أن السلاسل التي يُفترض أن تقبلها آلة تورينج قد تُرفض في بعض الأحيان، والسلاسل التي يُفترض أن ترفضها قد تُقبل في بعض الأحيان. ولمعالجة هذا، تُستخدم لغة${\displaystyle L}$يقال إنه يتم التعرف عليه باحتمالية خطأ${\displaystyle \epsilon }$بواسطة آلة تورينج احتمالية${\displaystyle M}$لو:

1. خيط${\displaystyle w}$في${\displaystyle L}$يشير ذلك إلى أن${\displaystyle {\text{Pr}}[M{\text{ accepts }}w]\geq 1-\epsilon }$
2. خيط${\displaystyle w}$ليس في${\displaystyle L}$يشير ذلك إلى أن${\displaystyle {\text{Pr}}[M{\text{ rejects }}w]\geq 1-\epsilon }$

نتيجةً للخطأ الناتج عن استخدام رمي العملة الاحتمالي، يمكن تعريف مفهوم قبول سلسلة بواسطة آلة تورينغ الاحتمالية بطرق مختلفة. أحد هذه المفاهيم، الذي يشمل عدة فئات تعقيد مهمة، هو السماح باحتمال خطأ قدره 1/3. على سبيل المثال، تُعرَّف فئة التعقيد BPP بأنها فئة اللغات التي تتعرف عليها آلة تورينغ الاحتمالية في وقت متعدد الحدود باحتمال خطأ قدره 1/3. فئة أخرى مُعرَّفة باستخدام مفهوم القبول هذا هي BPL ، وهي مماثلة لـ BPP ولكنها تفرض قيدًا إضافيًا يتمثل في ضرورة أن تكون اللغات قابلة للحل في فضاء لوغاريتمي .

تشمل فئات التعقيد الناتجة عن تعريفات أخرى للقبول RP و co-RP و ZPP . إذا اقتصرت الآلة على فضاء لوغاريتمي بدلاً من زمن متعدد الحدود، فسيتم الحصول على فئات التعقيد المماثلة RL و co-RL و ZPL . بفرض كلا القيدين، يتم الحصول على RLP و co-RLP و BPLP و ZPLP .

يُعدّ الحساب الاحتمالي بالغ الأهمية لتعريف معظم فئات أنظمة الإثبات التفاعلية ، حيث تعتمد آلة التحقق على العشوائية لتجنب التنبؤ بها وخداعها من قِبل آلة الإثبات القوية. على سبيل المثال، الفئة IP تُساوي PSPACE ، ولكن إذا أُزيلت العشوائية من آلة التحقق، فلن يتبقى لدينا سوى NP ، وهي فئة أصغر بكثير، وإن كانت غير معروفة على نطاق واسع.

أحد الأسئلة المحورية في نظرية التعقيد هو ما إذا كانت العشوائية تُضيف قوةً؛ أي، هل توجد مشكلة يمكن حلها في وقت متعدد الحدود بواسطة آلة تورينج احتمالية، ولكن ليس بواسطة آلة تورينج حتمية؟ أم أن آلات تورينج الحتمية قادرة على محاكاة جميع آلات تورينج الاحتمالية بكفاءة مع تباطؤ لا يتجاوز متعدد الحدود؟ من المعروف أن P ⊆ BPP ، لأن آلة تورينج الحتمية هي حالة خاصة من آلة تورينج الاحتمالية. مع ذلك، يبقى من غير المؤكد (وإن كان يُشتبه على نطاق واسع) أن BPP ⊆ P ، مما يعني أن BPP = P. ويُعتقد على نطاق أوسع أن السؤال نفسه ينطبق على فضاء اللوغاريتم بدلاً من وقت متعدد الحدود (هل L = BPLP ؟). من ناحية أخرى، فإن القوة التي تُضفيها العشوائية على أنظمة الإثبات التفاعلية، بالإضافة إلى الخوارزميات البسيطة التي تُنشئها لحل المشكلات الصعبة مثل اختبار أولية الأعداد في وقت متعدد الحدود واختبار اتصال الرسوم البيانية في فضاء اللوغاريتم، تُشير إلى أن العشوائية قد تُضيف قوةً.

• خوارزمية عشوائية

• أرورا، سانجيف ؛ باراك، بواز (2016). التعقيد الحسابي: منهج حديث . مطبعة جامعة كامبريدج. ص 123-142 . ISBN  978-0-521-42426-4.
• سيبسر، مايكل (2006). مقدمة في نظرية الحوسبة (  الطبعة الثانية). الولايات المتحدة الأمريكية: تومسون كورس تكنولوجي. الصفحات 368-380 . ISBN  978-0-534-95097-2.

• موقع المعهد الوطني للمعايير والتكنولوجيا (NIST) حول آلات تورينج الاحتمالية