קבוצה ניתנת למנייה רקורסיבית – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
BDaniel (שיחה | תרומות)
אין תקציר עריכה
אירי (שיחה | תרומות)
אין תקציר עריכה
שורה 2:
ב[[חישוביות]], [[קבוצה (מתמטיקה)|קבוצה]] [[קבוצה בת מנייה|בת מנייה]] נקראת '''ניתנת למנייה רקורסיבית'''
(נל"ר) או '''כריעה חיובית''' (כריעה למחצה) אם קיים [[אלגוריתם]] שבהינתן קלט, עוצר אם האיבר הנקלט שייך לקבוצה זו, אחרת האלגוריתם לא עוצר כלל.
לחלופין, קיים אלגוריתם שמייצר רשימה (ייתכן ואינסופית) של כלל האברים בקבוצה. קבוצת בעיות אלו מסומנת לרוב בסימון RE{{כ}} (recursiveRecursively enumerableEnumerable){{כ}}, מכיוון שקיים אלגוריתם המונה את אבריהם.
 
==הגדרה==