קבוצה רקורסיבית

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה לניווט קפיצה לחיפוש

בחישוביות, קבוצה בת מנייה נקראת רקורסיבית או כריעה אם ניתן לבנות אלגוריתם המסתיים לאחר מספר סופי של צעדים הקובע האם איבר מסוים שייך לקבוצה או לא.

הגדרה[עריכת קוד מקור | עריכה]

תת קבוצה S של המספרים הטבעיים נקראת רקורסיבית אם קיימת פונקציה ניתנת לחישוב

כך ש

באופן שקול, קבוצה היא רקורסיבית אם הפונקציה המציינת שלה היא פונקציה רקורסיבית.

תכונות[עריכת קוד מקור | עריכה]

  • אם A היא קבוצה רקורסיבית אז המשלים של A היא קבוצה רקורסיבית.
  • אם A ו-B הן קבוצות רקורסיביות אז גם A ∩ B וגם A ∪ B הן קבוצות רקורסיביות.
  • A היא קבוצה רקורסיבית אם"ם A והמשלים של A הן קבוצות הניתנות למנייה רקורסיבית.
  • התמונה של קבוצה רקורסיבית תחת פונקציה שלמה וניתנת לחישוב היא קבוצה רקורסיבית.

ראו גם[עריכת קוד מקור | עריכה]


קישורים חיצוניים[עריכת קוד מקור | עריכה]