مقاله‌ی زیر به همراه خلاصه آن در وب‌سایت ویکیپدیا آمده است. موضوع آن را مشخص کنید

مقاله: تعریف‌های اصلی متناظری برای مفهوم یک‌زبان شمارش پذیر بازگشتی وجود دارد. یک‌زبان شمارش‌پذیر بازگشتی، یک زیرمجموعه شمارش پذیر بازگشتی در مجموعه‌ای از تمام کلمات ممکن برحسب الفبای زبان می‌باشد. یک‌زبان شمارش‌پذیر بازگشتی، یک‌زبان صوری می‌باشد که برای آن یک ماشین تورینگ وجود دارد که تمام رشته‌های معتبر زبان را شمارش می‌کند. توجه کنید که اگر زبان، نامحدود باشد، الگوریتم شمارنده ارائه‌شده را می‌توان انتخاب نمود بنابراین از تکرار اجتناب می‌کند، چون ما می‌توانیم آزمایش کنیم که ایا رشته تولید شده برای عدد n، برای عددی تولید می‌شود که کمتر از n می‌باشد. اگر قبلا تولید شده باشد، از خروجی را برای ورودی n+ ۱ استفاده کنید ولی دوباره آزمایش کنید که آیا، جدید است یا نه. یک‌زبان شمارش‌پذیر بازگشتی، زبان صوری می‌باشد که برای ان یک ماشین تورینگ وجود دارد که در زمان نمایش دادن با هر رشته در زبان به عنوان ورودی، مکث می‌کند و قبول می‌شود ولی ممکن است هنگام نمایش با رشته‌ای نه در زبان، مکث کند و رد نماید یا برای همیشه در حلقه بیفتد. در مقابل این برای زبان‌های بازگشتی، نیاز است که ماشین تورینگ در تمام موارد و نمونه‌ها مکث نماید. تمام زبان‌های بازگشتی، حساس به متن، مستقل از متن و منظم، شمارش پذیر بازگشتی می‌باشند. قضیه post نشان می‌دهد که re به همراه همتاهای re کامل خود متناظر با اولین سطح سلسله‌مراتب ریاضی می‌باشد. مسئله توقف، r. e می‌باشد نه بازگشتی. فرد می‌تواند ماشین تورینگ را اجرا نماید و قبول کند که ایا دستگاه مکث کند یا نه. از طرفی دیگر، این مشکل، غیرقابل تصمیم‌گیری می‌باشد. برخی زبان‌های r. e، بازگشتی نمی‌باشند: مسئله ارتباطات ارسالی مرگ و میر (تئوری قابلیت محاسبه) مسئله توقف زبانهای بازگشتی شمارش پذیر تحت عملیات زیر به هم مربوط می‌شوند. یعنی، اگر l، p دو زبان شمارش پذیر بازگشتی باشند، انگاه زبان‌های زیر، بازگشتی شمارش پذیر می‌باشند: ستاره کلین مربوط به l الحاق l، p اجتماع اشتراک توجه کنید که زبان‌های شمارش پذیر برگشتی تحت تفاضل دو مجموعه یا مکمل مجموعه بسته نیستند. تفاوت مجموعه l-p، ممکن است شمارش پذیر بازگشتی باشد و ممکن است بدین صورت نباشد. اگر l، شمارش پذیر بازگشتی باشد، انگاه مکمل l اگر و تنهااگر شمارش پذیر بازگشتی می‌باشد که l بازگشتی باشد. 
خلاصه: در ریاضیات، منطق و علوم کامپیوتر، یک‌زبان صوری شمارش‌پذیر بازگشتی می‌باشد در صورتی که زیرمجموعه شمارش‌پذیر بازگشتی در مجموعه‌ای از کلمات احتمالی برحسب الفبای زبان وجود داشته باشد، یعنی یک ماشین تورینگ وجود داشته باشد که تمام رشته‌های معتبر زبان را شمارش می‌کند. زبان‌های شمارش‌پذیر بازگشتی، به عنوان زبانهای نوع ۰ در سلسله‌مراتب چامسکی زبان‌های صوری شناخته‌شده می‌باشند. تمام زبان‌های بازگشتی، حساس به متن، مستقل از متن و منظم، شمارش پذیر بازگشتی می‌باشند. کلاسی از تمام زبان‌های شمارش پذیر بازگشتی، re نامیده می‌شود. 
موضوع:
زبان شمارش پذیر بازگشتی