הצגת המקור של הדף "קבוצה רקורסיבית"

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

==הגדרה==
תת קבוצה S של ה[[מספרים טבעיים|מספרים הטבעיים]] נקראת '''רקורסיבית''' אם קיימת [[פונקציה ניתנת לחישוב]]

:<math>f \colon \mathbb{N} \to \mathbb{N}</math>
כך ש
:<math>f(x) =
\left\{\begin{matrix}
0 &\mbox{if}\ x \in S \\
\neq 0 &\mbox{if}\ x \notin S
\end{matrix}\right.
</math>
באופן שקול, קבוצה היא רקורסיבית אם [[פונקציה מציינת|הפונקציה המציינת]] שלה היא [[פונקציה רקורסיבית]].

==תכונות==
*אם <math>A</math> היא קבוצה רקורסיבית אז [[משלים (מתמטיקה)|המשלים]] של <math>A</math> היא קבוצה רקורסיבית.
*אם <math>A</math> ו-<math>B</math> הן קבוצות רקורסיביות אז <math>A \cap B</math> וגם <math>A \cup B</math> הן קבוצות רקורסיביות.
*<math>A</math> היא קבוצה רקורסיבית [[אם"ם]] <math>A</math> והמשלים של <math>A</math> הן [[קבוצה ניתנת למנייה רקורסיבית|קבוצות הניתנות למנייה רקורסיבית]].
*ה[[תמונה (מתמטיקה)|תמונה]] של קבוצה רקורסיבית תחת פונקציה שלמה וניתנת לחישוב היא קבוצה רקורסיבית.

==ראו גם==
* [[כריעות]]
* [[היררכיית חומסקי]]

==קישורים חיצוניים==
* {{MathWorld}}

[[קטגוריה:חישוביות]]