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

הגדרה

---

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

$f:\backslash mathbb\{N\}\; \backslash to\; \backslash 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 הן קבוצות הניתנות למנייה רקורסיבית.
• התמונה של קבוצה רקורסיבית תחת פונקציה שלמה וניתנת לחישוב היא קבוצה רקורסיבית.

חישוביות

Recursive set | Rekursiv entscheidbare Menge | Komputebla aro | Ensemble récursif | Insieme ricorsivo | 帰納的集合 | Zbiór rekurencyjny | 递归集合