ebooksgratis.com

See also ebooksgratis.com: no banners, no cookies, totally FREE.

CLASSICISTRANIERI HOME PAGE - YOUTUBE CHANNEL
Privacy Policy Cookie Policy Terms and Conditions
קבוצה ניתנת למנייה רקורסיבית – ויקיפדיה

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

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

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

תוכן עניינים

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

תת קבוצה 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 היא קבוצה רקורסיבית
  • התמונה של קבוצה נל"ר תחת פונקציה ניתנת לחישוב היא גם קבוצה נל"ר
  • קבוצת הקבוצות הניתנות למנייה רקורסיבית מכילה ממש את קבוצת הקבוצות הרקורסיביות - בעיית העצירה היא דוגמה לקבוצה לא רקורסיבית הניתנת למנייה רקורסיבית.

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


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


aa - ab - af - ak - als - am - an - ang - ar - arc - as - ast - av - ay - az - ba - bar - bat_smg - bcl - be - be_x_old - bg - bh - bi - bm - bn - bo - bpy - br - bs - bug - bxr - ca - cbk_zam - cdo - ce - ceb - ch - cho - chr - chy - co - cr - crh - cs - csb - cu - cv - cy - da - de - diq - dsb - dv - dz - ee - el - eml - en - eo - es - et - eu - ext - fa - ff - fi - fiu_vro - fj - fo - fr - frp - fur - fy - ga - gan - gd - gl - glk - gn - got - gu - gv - ha - hak - haw - he - hi - hif - ho - hr - hsb - ht - hu - hy - hz - ia - id - ie - ig - ii - ik - ilo - io - is - it - iu - ja - jbo - jv - ka - kaa - kab - kg - ki - kj - kk - kl - km - kn - ko - kr - ks - ksh - ku - kv - kw - ky - la - lad - lb - lbe - lg - li - lij - lmo - ln - lo - lt - lv - map_bms - mdf - mg - mh - mi - mk - ml - mn - mo - mr - mt - mus - my - myv - mzn - na - nah - nap - nds - nds_nl - ne - new - ng - nl - nn - no - nov - nrm - nv - ny - oc - om - or - os - pa - pag - pam - pap - pdc - pi - pih - pl - pms - ps - pt - qu - quality - rm - rmy - rn - ro - roa_rup - roa_tara - ru - rw - sa - sah - sc - scn - sco - sd - se - sg - sh - si - simple - sk - sl - sm - sn - so - sr - srn - ss - st - stq - su - sv - sw - szl - ta - te - tet - tg - th - ti - tk - tl - tlh - tn - to - tpi - tr - ts - tt - tum - tw - ty - udm - ug - uk - ur - uz - ve - vec - vi - vls - vo - wa - war - wo - wuu - xal - xh - yi - yo - za - zea - zh - zh_classical - zh_min_nan - zh_yue - zu -