קבוצה ניתנת למנייה רקורסיבית

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

בחישוביות, קבוצה בת מנייה נקראת ניתנת למנייה רקורסיבית (נל"ר) או כריעה חיובית אם קיים אלגוריתם שכאשר הוא מקבל קלט הוא עוצר אם האיבר הנקלט שייך לקבוצה זו, אחרת האלגוריתם לא עוצר כלל.

תוכן עניינים

[עריכה] הגדרה

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

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

כך ש-

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

[עריכה] תכונות

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


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


[עריכה] ראו גם