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

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

הגדרה

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

$f\colon \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$ היא קבוצה רקורסיבית.
• אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} הן קבוצות רקורסיביות אז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \cap B} וגם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \cup B} הן קבוצות רקורסיביות.
• הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} היא קבוצה רקורסיבית אם"ם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} והמשלים של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} הן קבוצות הניתנות למנייה רקורסיבית.
• התמונה של קבוצה רקורסיבית תחת פונקציה שלמה וניתנת לחישוב היא קבוצה רקורסיבית.

ראו גם

• כריעות
• היררכיית חומסקי

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

• קבוצה רקורסיבית, באתר MathWorld (באנגלית)

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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