קבוצה ניתנת למנייה רקורסיבית

בחישוביות, קבוצה בת מנייה נקראת ניתנת למנייה רקורסיבית (נל"ר) או בת מנייה רקורסיבית (במ"ר) או כריעה חיובית (כריעה למחצה) אם קיים אלגוריתם שבהינתן קלט, עוצר אם האיבר הנקלט שייך לקבוצה זו. לחלופין, קיים אלגוריתם שמייצר רשימה (ייתכן ואינסופית) של כלל האיברים בקבוצה. קבוצת בעיות אלו מסומנת לרוב בסימון RE‏ (Recursively Enumerable)‏, מכיוון שקיים אלגוריתם המונה את אבריהם.

הגדרה

תת קבוצה ${\displaystyle S}$ של המספרים הטבעיים היא נל"ר אם קיימת פונקציה ניתנת לחישוב

${\displaystyle f\colon \mathbb {N} \to \mathbb {N} }$

כך ש-

${\displaystyle f(x)=\left\{{\begin{matrix}0&{\mbox{if}}\ x\in S\\{\mbox{does not halt}}&{\mbox{if}}\ x\notin S\end{matrix}}\right.}$

תכונות

• אם ${\displaystyle A}$ ו-${\displaystyle B}$ הן נל"ר אז גם ${\displaystyle A\cap B}$ וגם ${\displaystyle A\cup B}$ הן נל"ר.
• קבוצה ${\displaystyle A}$ והמשלים של ${\displaystyle A}$ הן נל"ר אם"ם A היא קבוצה רקורסיבית.
• התמונה של קבוצה נל"ר תחת פונקציה ניתנת לחישוב היא גם קבוצה נל"ר.
• קבוצת הקבוצות הניתנות למנייה רקורסיבית מכילה ממש את קבוצת הקבוצות הרקורסיביות - בעיית העצירה היא דוגמה לקבוצה לא רקורסיבית הניתנת למנייה רקורסיבית.

דוגמאות

• כל קבוצה רקורסיבית היא נל"ר.
• שפה ניתנת למנייה רקורסיבית היא תת-קבוצה נל"ר בקבוצת כל המילים תחת אלפבית של שפה מסוימת.

כריעות שלילית

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

ראו גם

• קבוצה רקורסיבית
• כריעות
• היררכיית חומסקי

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

• קבוצה ניתנת למנייה רקורסיבית, באתר MathWorld (באנגלית)

מחלקות חישוביות וסיבוכיות

מקרא   מחלקת חישוביות   מחלקת סיבוכיות ${\displaystyle \cap }$ מחלקה המהווה חיתוך של המחלקות שמכילות אותה ומופיעות בתרשים.   מסלול שיורד למטה מצביע על כך שהמחלקה התחתונה היא חלקית ממש למחלקה העליונה   מסלול שיורד למטה מצביע על כך שהמחלקה התחתונה היא חלקית למחלקה העליונה אך לא ידוע האם הן שוות בעיית הכרעה בעיית הכרעה       בעיות כריעות חיובית (למחצה) בעיות כריעות חיובית (למחצה)       בעיות כריעות בעיות כריעות         EXPSPACE EXPSPACE           EXPTIME EXPTIME                                             PSPACE PSPACE                               שפה תלוית הקשר שפה תלוית הקשר   NP NP   BQP BQP co-NP co-NP                                                   BPP BPP                               RP RP co-RP co-RP                       ZPP ZPP ${\displaystyle \,\cap }$                     P P                                 NC NC                   שפה חופשית הקשר שפה חופשית הקשר       שפה רגולרית שפה רגולרית