קבוצה רקורסיבית - Wikiwand
For faster navigation, this Iframe is preloading the Wikiwand page for קבוצה רקורסיבית.

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

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

הגדרה

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

כך ש

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

תכונות

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

ראו גם


קישורים חיצוניים

{{bottomLinkPreText}} {{bottomLinkText}}
קבוצה רקורסיבית
Listen to this article