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