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