R (التعقيد)

في نظرية التعقيد الحسابي ، R هي فئة مشاكل القرار التي يمكن حلها بواسطة آلة تورينج ، وهي مجموعة جميع اللغات المتكررة (وتسمى أيضًا اللغات القابلة للتقرير).

الصيغ المتكافئة

R مكافئة لمجموعة جميع الدوال القابلة للحساب الكلي بالمعنى التالي:

تكون مسألة القرار في لغة R إذا وفقط إذا كانت دالة المؤشر الخاصة بها قابلة للحساب.
تكون الدالة الكلية قابلة للحساب إذا وفقط إذا كان رسمها البياني في R.

بما أنه يمكننا تحديد أي مشكلة يوجد لها معترف ومعترف مساعد عن طريق دمجها ببساطة حتى نحصل على نتيجة، فإن الفئة تساوي RE ∩ co-RE .

بلوم، لينور ، مايك شوب ، وستيف سميل ، (1989)، "حول نظرية الحساب والتعقيد على الأعداد الحقيقية: اكتمال NP، والدوال المتكررة، والآلات العالمية"، نشرة الجمعية الرياضية الأمريكية ، السلسلة الجديدة، 21 (1): 1-46.