در ، و ، یک شمارش‌پذیر بازگشتی می‌باشد در صورتی که در از کلمات احتمالی برحسب وجود داشته باشد، یعنی یک وجود داشته باشد که تمام رشته‌های معتبر زبان را شمارش می‌کند. 
زبان‌های شمارش‌پذیر بازگشتی، به عنوان زبانهای نوع ۰ در زبان‌های صوری شناخته شده می‌باشند. تمام زبان‌های ، ، و ، شمارش پذیر بازگشتی می‌باشند. 
کلاسی از تمام زبان‌های شمارش پذیر بازگشتی، RE نامیده می‌شود.
 تعریف‌های اصلی متناظری برای مفهوم یک زبان شمارش پذیر بازگشتی وجود دارد.
 
 
 تمام زبان‌های ، ، و ، شمارش پذیر بازگشتی می‌باشند. 
قضیه Post نشان می‌دهد که RE به همراه همتاهای RE کامل خود متناظر با اولین سطح سلسله مراتب ریاضی می‌باشد.
 ، r.e می‌باشد نه بازگشتی. فرد می‌تواند را اجرا نماید و قبول کند که ایا دستگاه مکث کند یا نه. از طرفی دیگر، این مشکل، غیرقابل تصمیم گیری می‌باشد.
برخی زبان‌های r.e، بازگشتی نمی‌باشند:
 
 
 زبانهای بازگشتی شمارش پذیر تحت عملیات زیر به هم مربوط می‌شوند. یعنی، اگر L ،P دو زبان شمارش پذیر بازگشتی باشند، انگاه زبان‌های زیر، بازگشتی شمارش پذیر می‌باشند:
 
 
 
 توجه کنید که زبان‌های شمارش پذیر برگشتی تحت تفاضل دو مجموعه یا مکمل مجموعه بسته نیستند. تفاوت مجموعه L-P، ممکن است شمارش پذیر بازگشتی باشد و ممکن است بدین صورت نباشد. اگر L، شمارش پذیر بازگشتی باشد، انگاه مکمل L اگر و تنهااگر شمارش پذیر بازگشتی می‌باشد که L بازگشتی باشد.
 
 _
{"title": "زبان شمارش‌پذیر بازگشتی", "link": "https://fa.wikipedia.org//w/index.php?title=%D8%B2%D8%A8%D8%A7%D9%86_%D8%B4%D9%85%D8%A7%D8%B1%D8%B4%E2%80%8C%D9%BE%D8%B0%DB%8C%D8%B1_%D8%A8%D8%A7%D8%B2%DA%AF%D8%B4%D8%AA%DB%8C&oldid=33913452", "language": "fa"}