קבוצה ניתנת למנייה רקורסיבית
מתוך ויקיפדיה, האנציקלופדיה החופשית
בחישוביות, קבוצה בת מנייה נקראת ניתנת למנייה רקורסיבית (נל"ר) או כריעה חיובית (כריעה למחצה) אם קיים אלגוריתם שבהינתן קלט, עוצר אם האיבר הנקלט שייך לקבוצה זו, אחרת האלגוריתם לא עוצר כלל.
תוכן עניינים |
[עריכה] הגדרה
תת קבוצה S של המספרים הטבעיים היא נל"ר אם קיימת פונקציה ניתנת לחישוב
כך ש-
[עריכה] תכונות
- אם A ו-B הן נל"ר אז גם A ∩ B וגם A ∪ B הן נל"ר.
- קבוצה A והמשלים של A הן נל"ר אם"ם A היא קבוצה רקורסיבית
- התמונה של קבוצה נל"ר תחת פונקציה ניתנת לחישוב היא גם קבוצה נל"ר
- קבוצת הקבוצות הניתנות למנייה רקורסיבית מכילה ממש את קבוצת הקבוצות הרקורסיביות - בעיית העצירה היא דוגמה לקבוצה לא רקורסיבית הניתנת למנייה רקורסיבית.
[עריכה] דוגמאות
- כל קבוצה רקורסיבית היא נל"ר
- שפה ניתנת למנייה רקורסיבית היא תת קבוצה נל"ר בקבוצת כל המילים תחת אלפבית של שפה מסוימת.