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