مجموعه بازگشتی

در نظریه شمارش پذیری یک مجموعه از اعداد طبیعی بازگشتی،شمارش پذیر یا تصمیم پذیر خوانده می‌شود اگر الگوریتمی موجود باشد به قسمی که پس از یک زمان متناهی مشخص کند که یک عدد داده شده به مجموعه تعلق دارد یا نه.مجموعه ای که شمارش پذیر نباشد،شمارش ناپذیر یا تصمیم ناپذیر خوانده می شود.

یک رده کلی تر از مجموعه‌ها شامل مجموعه‌های شمارش پذیر بازگشتی می شود.برای این مجموعه‌ها تنها لازم است که الگوریتمی وجود داشته باشد که وقتی که عدد داده شده در مجموعه موجود باشد جواب دهد، برای اعدادی که در مجموعه نیستند الگوریتم ممکن است جواب ندهد.

تعریف رسمی

مجموعه S از اعداد طبیعی بازگشتی گفته می‌شود اگر تابع شمارش پذیر تام ${\displaystyle f\,}$ وجود داشته باشد به طوری که ${\displaystyle f(x)=1\,}$ if ${\displaystyle x\in S}$ and ${\displaystyle f(x)=0\,}$ if ${\displaystyle x\notin S}$. به بیان دیگر S بازگشتی است اگر و تنها اگر تابع مشخصه ${\displaystyle 1_{S}\,}$ شمارش پذیر باشد.

مثال‌ها

• مجموعه تهی شمارش پذیر است.
• کل مجموعه اعداد طبیعی شمارش پذیر است.
• هر زیر مجموعه متناهی از اعداد طبیعی شمارش پذیر است.
• اعداد اول شمارش پذیر است.

ویژگی‌ها

اگر A یک مجموعه بازگشتی باشد آنگاه مکملش نیز بازگشتی است.

اگر A و B دو مجموعه بازگشتی باشند آنگاه اجتماع و اشتراکشان نیز بازگشتی است.

اگر A و B دو مجموعه بازگشتی باشند آنگاه A*B نیز تحت ضرب جفتی کانتور بازگشتی است.

یک مجموعه بازگشتی است اگر و تنها اگر در سطح ${\displaystyle \Delta _{1}^{0}}$ از سلسله مراتب حسابی باشد.

یک مجموعه بازگشتی است اگر و تنها اگر در دامنه غیر نزولی تابع شمارش کل باشد یا مجموعه تهی باشد.

پیوند به بیرون

https://web.archive.org/web/20110514035110/http://www.cl.cam.ac.uk/~ts328/supervision/comptheory/recenum.pdf

https://web.archive.org/web/20110822000807/http://www.statemaster.com/encyclopedia/Recursive-set

منابع

Wikipedia contributors, «Recursive set», Wikipedia, The Free Encyclopedia,

http://en.wikipedia.org/wiki/Recursive_set

• Cutland, N. Computability. Cambridge University Press, Cambridge-New York, 1980. ISBN 0-521-22384-9; ISBN 0-521-29465-7
• Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. ISBN 0-262-68052-1; ISBN 0-07-053522-1