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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

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

تعریف رسمی[ویرایش]

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

مثال‌ها[ویرایش]

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

ویژگی‌ها[ویرایش]

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

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

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

یک مجموعه بازگشتی است اگر و تنها اگر در سطح \Delta^0_1 از سلسله مراتب حسابی باشد.

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

پیوند به بیرون[ویرایش]

منابع[ویرایش]

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

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