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

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

הגדרהעריכה

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

 

כך ש

 

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

תכונותעריכה

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

ראו גםעריכה


קישורים חיצונייםעריכה