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

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

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

הגדרה

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

f:

כך ש

f(x)={0if xS0if xS

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

תכונות

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

ראו גם

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

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


 


 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 


 
 
 
 
 
 
 
 
 
 
 
 
 
 
 


 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 


 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 


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

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