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

در نظریه شمارش پذیری یک مجموعه از اعداد طبیعی بازگشتی، شمارش پذیر یا تصمیم پذیر خوانده می شود اگر الگوریتمی موجود باشد به قسمی که پس از یک زمان متناهی مشخص کند که یک عدد داده شده به مجموعه تعلق دارد یا نه. مجموعه ای که شمارش پذیر نباشد، شمارش ناپذیر یا تصمیم ناپذیر خوانده می شود.
یک رده کلی تر از مجموعه ها شامل مجموعه های شمارش پذیر بازگشتی می شود. برای این مجموعه ها تنها لازم است که الگوریتمی وجود داشته باشد که وقتی که عدد داده شده در مجموعه موجود باشد جواب دهد، برای اعدادی که در مجموعه نیستند الگوریتم ممکن است جواب ندهد.
مجموعه S از اعداد طبیعی بازگشتی گفته می شود اگر تابع شمارش پذیر تام f وجود داشته باشد به طوری که f ( x ) = 1 if x ∈ S and f ( x ) = 0 if x ∉ S . به بیان دیگر S بازگشتی است اگر و تنها اگر تابع مشخصه 1 S شمارش پذیر باشد.
• مجموعه تهی شمارش پذیر است.
• کل مجموعه اعداد طبیعی شمارش پذیر است.
• هر زیر مجموعه متناهی از اعداد طبیعی شمارش پذیر است.
• اعداد اول شمارش پذیر است.
اگر A یک مجموعه بازگشتی باشد آنگاه مکملش نیز بازگشتی است.
اگر A و B دو مجموعه بازگشتی باشند آنگاه اجتماع و اشتراکشان نیز بازگشتی است.
اگر A و B دو مجموعه بازگشتی باشند آنگاه A*B نیز تحت ضرب جفتی کانتور بازگشتی است.
یک مجموعه بازگشتی است اگر و تنها اگر در سطح Δ 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