RE (التعقيد)

في نظرية الحوسبة ونظرية التعقيد الحسابي ، تُعرف RE ( القابلة للتعداد التكراري ) بأنها فئة من مسائل القرار التي يمكن التحقق من إجابتها بـ "نعم" بواسطة آلة تورينج في وقت محدود. ^{[ 1 ]} بعبارة أخرى، إذا كانت إجابة مسألة ما هي "نعم"، فهناك إجراء ما يستغرق وقتًا محدودًا لتحديد ذلك، ولا يُبلغ هذا الإجراء أبدًا عن "نعم" بشكل خاطئ عندما تكون الإجابة الصحيحة "لا". مع ذلك، عندما تكون الإجابة الصحيحة "لا"، لا يُشترط أن يتوقف الإجراء؛ فقد يدخل في " حلقة لا نهائية " لبعض حالات "لا". يُطلق على هذا الإجراء أحيانًا اسم شبه خوارزمية ، لتمييزه عن الخوارزمية ، التي تُعرَّف بأنها حل كامل لمسألة قرار. ^{[ 2 ]}

وبالمثل، فإن co-RE هي مجموعة جميع اللغات التي تُكمّل لغةً في RE . بمعنى آخر، تحتوي co-RE على لغات يمكن دحض انتمائها في فترة زمنية محدودة، لكن إثبات هذا الانتماء قد يستغرق وقتًا طويلًا جدًا.

بصورة مكافئة، تُعرَّف RE بأنها فئة مسائل القرار التي تستطيع آلة تورينج سرد جميع حالات الإجابة بـ "نعم" فيها، واحدة تلو الأخرى (وهذا هو معنى "قابل للتعداد"). كل عنصر من عناصر RE هو مجموعة قابلة للتعداد بشكل متكرر ، وبالتالي فهو مجموعة ديوفانتية .

ولإثبات أن هذا متكافئ، لاحظ أنه إذا كانت هناك آلة${\displaystyle E}$يقوم هذا البرنامج بحصر جميع المدخلات المقبولة، ويمكن لجهاز آخر يستقبل سلسلة نصية أن يعمل.${\displaystyle E}$ويتم قبولها إذا كانت السلسلة مُرقمة. وعلى العكس من ذلك، إذا كانت الآلة${\displaystyle M}$يقبل النظام المدخلات بلغة معينة، ويمكن لآلة أخرى تعداد جميع السلاسل النصية في تلك اللغة عن طريق دمج عمليات محاكاة لـ${\displaystyle M}$على كل سلسلة إدخال وإخراج مقبولة (هناك ترتيب للتنفيذ سيصل في النهاية إلى كل خطوة تنفيذ لأنه يوجد عدد لا يحصى من الأزواج المرتبة من المدخلات والخطوات).

مجموعة اللغات التكرارية ( R ) هي مجموعة جزئية من كلٍّ من RE و co-RE . ^{[ 3 ]} في الواقع، هي تقاطع هاتين الفئتين، لأنه يمكننا حلّ أي مشكلة يوجد لها مُعرِّف ومُعرِّف مُساعد ببساطة عن طريق دمجهما حتى نحصل على نتيجة. لذلك:

${\displaystyle {\mbox{R}}={\mbox{RE}}\cap {\mbox{co-RE}}}$.

في المقابل، تُعرف مجموعة اللغات التي لا تنتمي إلى مجموعة اللغات المعزولة (RE) ولا إلى مجموعة اللغات المعزولة المشتركة (co-RE) باسم NRNC . وهي مجموعة اللغات التي لا يمكن إثبات انتمائها أو عدم انتمائها خلال فترة زمنية محددة، وتشمل جميع اللغات الأخرى التي لا تنتمي إلى أي من مجموعتي اللغات المعزولة أو المعزولة المشتركة . أي:

${\displaystyle {\mbox{NRNC}}={\mbox{ALL}}-({\mbox{RE}}\cup {\mbox{co-RE}})}$.

ليست هذه المشكلات غير قابلة للحل فحسب، بل إنها ولا مكملاتها قابلة للتعداد بشكل متكرر.

في يناير 2020، نُشرت ورقة بحثية أولية تُعلن عن برهان يُثبت أن RE مُكافئ للفئة MIP* (الفئة التي يتفاعل فيها مُدقِّق كلاسيكي مع مُثبتين كموميين متعددين ذوي قدرات فائقة يتشاركون التشابك )؛ ^{[ 4 ]} ونُشر برهان مُنقَّح، ولكنه لم يُراجع بالكامل بعد، في مجلة Communications of the ACM في نوفمبر 2021. ويُشير هذا البرهان إلى أن مسألة تضمين كونز ومسألة تسيرلسون خاطئتان. ^{[ 5 ]}

مجموعة مسائل القرار الكاملة في RE هي مجموعة مسائل القرار الكاملة في RE . بمعنى آخر، تُعدّ هذه المسائل "الأصعب" بين مسائل التعداد التكراري. عمومًا، لا تُفرض أي قيود على الاختزالات المستخدمة باستثناء أنها يجب أن تكون اختزالات متعددة من نوع "واحد" .

أمثلة على مسائل إعادة الإكمال:

1. مشكلة التوقف : ما إذا كان البرنامج الذي يُعطى مدخلات محدودة سينتهي من التشغيل أم سيستمر في التشغيل إلى الأبد.
2. بحسب نظرية رايس ، فإن تحديد انتماء عنصر ما إلى أي مجموعة جزئية غير تافهة من مجموعة الدوال الاسترجاعية الجزئية هو مسألة صعبة من نوع RE . وتكون المسألة كاملة كلما كانت المجموعة قابلة للتعداد الاسترجاعي.
3. أثبت جون مايهيل ( 1955 ) ^{[ 6 ]} أن جميع المجموعات الإبداعية هي RE- كاملة. 
4. المسألة اللفظية الموحدة للمجموعات أو أنصاف المجموعات . (في الواقع، المسألة اللفظية لبعض المجموعات الفردية هي مسألة كاملة من نوع RE ).
5. تحديد العضوية في قواعد نحوية رسمية عامة غير مقيدة . (مرة أخرى، بعض القواعد النحوية الفردية لديها مشاكل عضوية كاملة من نوع RE .)
6. مشكلة الصلاحية لمنطق الرتبة الأولى .
7. مشكلة المراسلات اللاحقة : بالنظر إلى قائمة من أزواج السلاسل النصية، حدد ما إذا كان هناك اختيار من هذه الأزواج (مع السماح بالتكرارات) بحيث يكون تسلسل العناصر الأولى (من الأزواج) مساويًا لتسلسل العناصر الثانية.
8. تحديد ما إذا كانت المعادلة الديوفانتية لها أي حلول صحيحة.

تُعرف مجموعة مسائل القرار الكاملة بالنسبة لـ co- RE باسم co-RE-complete . ويمكن القول إنها تُكمل أصعب المسائل القابلة للتعداد التكراري.

أمثلة على مسائل الإكمال المشترك:

1. مشكلة الدومينو لبلاطات وانغ .
2. مشكلة الإرضاء لمنطق الرتبة الأولى .

• خوارزمية إكمال كنوت-بنديكس
• قائمة المسائل غير القابلة للحل
• التكرار متعدد الأشكال
• خوارزمية ريش
• شبه قابلية الحسم