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

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

הגדרה שקולה

המחלקה R שקולה לקבוצת כל הפונקציות בנות-חישוב כך ש:

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

סגירות המחלקה לפעולות

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

יחסים בין המחלקה למחלקות אחרות

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

לקריאה נוספת

• לנור בלום, מייק שאב וסטפן סמל, On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines, כרך 21, הסדרה החדשה, Bulletin of the American Mathematical Society‏, 1989, עמ' 1-46. (באנגלית)

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

• סקוט אהרונסון, Class R, באתר Complexity Zoo (באנגלית)

ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.