R (מחלקת סיבוכיות)

בתורת החישוביות והסיבוכיות, המחלקה R (מאנגלית: Recursive) היא מחלקה אשר מכילה את כל בעיות ההכרעה אשר ניתנות לפתירה על ידי מכונת טיורינג ואשר מהווה קבוצה של כלל השפות הרקורסיביות (אשר מכונות גם שפות כריעות).

 הגדרה שקולה 
המחלקה R שקולה לקבוצת כל הפונקציות בנות-חישוב כך ש:
 בעיית הכרעה נמצאת ב-R אם ורק אם הפונקציה המציינת היא בת-חישוב.
 פונקציה שלמה היא בת-חישוב אם ורק אם הגרף שלה נמצא ב-R.

 סגירות המחלקה לפעולות 
המחלקה R סגורה לפעולות הבאות: איחוד, חיתוך, משלים, שרשור, היפוך וכוכב קלין.

 יחסים בין המחלקה למחלקות אחרות 
מכיוון שניתן להכריע כל בעיה שקיימת לה מכונת טיורינג מקבלת (כלומר מכונת טיורינג שעונה כן אם התשובה היא כן) וכן מכונת טיורינג דוחה (כלומר מכונת טיורינג שעונה לא אם התשובה היא לא), אזי בעזרתן ניתן לבנות מכונת טיורינג אשר מכריעה את הבעיה ולכן המחלקה R מוגדרת להיות החיתוך בין המחלקות RE ו-coRE, דהי, .

 לקריאה נוספת 


 קישורים חיצוניים 


קטגוריה:מחלקות סיבוכיות