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

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

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

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

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

f:\mathbb{N} \to \mathbb{N}

כך ש

f(x) = 
\left\{\begin{matrix} 
0 &\mbox{if}\ x \in S \\
\neq 0 &\mbox{if}\ x \notin S
\end{matrix}\right.

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

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

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

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