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

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

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

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

תת קבוצה 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.

תכונות[עריכת קוד מקור | עריכה]

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

כריעות שלילית[עריכת קוד מקור | עריכה]

באופן שקול, ניתן להגדיר קבוצה כריעה למחצה (שלילית), עבורה קיים אלגוריתם שעוצר אם הקלט אינו שייך לקבוצה (אבל אולי לא עוצר עבור קלט בקבוצה). קבוצת כל הבעיות מסוג זה מסומנת לרוב על ידי co-RE (התחילית co מסמנת "משלים", complement).

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