آرای (پیچیدگی). در تئوری محاسباتی و تئوری پیچیدگی محاسباتی، RE (قابل شمارش بازگشتی)، کلاسی از مسئله تصمیم می باشد که برای ان پاسخ بلی را می توان با ماشین تورینگ در مدت زمان متناهی مشخص نمود.به طور معمول، بدین معناست که اگر پاسخ " بلی " باشد، انگاه رویه هایی وجود دارند که زمان محدودی را برای تعیین ان می گیرند. از طرفی دیگر، اگر پاسخ " خیر " باشد، ممکن است دستگاه هرگز مکث نکند. RE، کلاسی از مشکلات تصمیم گیری می باشد که برای ان یک ماشین تورینگ می تواند تمام نمونه های " بلی " یک به یک را لیست نماید.به طور مشابه، RE، مجموعه ای از تمام زبان هایی می باشد که مکمل های یک زبان در RE می باشند. در یک حالت، RE شامل زبان هایی می باشد که عضویت ان را می توان در مدت زمان محدودی رد کرد ولی تأیید عضویت ممکن است برای همیشه به طول انجامد.هر عضو از RE، یک مجموعه قابل شمارش بازگشتی و بنابراین یک مجموعه Diophantine می باشد.
زبان شمارش پذیر بازگشتی
مجموعه ای از زبان های بازگشتی (R)، زیرمجموعه ای از RE و co-RE می باشد. در حقیقت، ارتباط ان دو کلاس به صورت زیر است:
RE-کامل، مجموعه ای از مشکلات تصمیم گیری است که برای RE کامل است. در یک حالت، اینها، سخت ترین مشکلات قابل شمارش بازگشتی می باشند. تمام این مشکلات، غیربازگشتی هستند. معمولاً، هیچ محدودیتی در کاهش های استفاده شده قرار نمی گیرد مگراینکه آن ها باید کاهش چند به یک باشند.نمونه هایی از مشکلات RE- کامل
Co-RE کامل، مجموعه ای از مشکلات تصمیم گیری می باشد که برای co-RE کامل است. در یک حالت، مکمل هایی برای سخت ترین مشکلات بازگشتی قابل شمارش وجود دارد.نمونه هایی از مشکلات co-RE- کامل:
