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