زبان شمارش‌پذیر بازگشتی

تعریف‌های اصلی متناظری برای مفهوم یک زبان شمارش پذیر بازگشتی وجود دارد.

1. یک زبان شمارش‌پذیر بازگشتی، یک زیرمجموعه شمارش پذیر بازگشتی در مجموعه‌ای از تمام کلمات ممکن برحسب الفبای زبان می‌باشد.
2. یک زبان شمارش‌پذیر بازگشتی، یک زبان صوری می‌باشد که برای آن یک ماشین تورینگ وجود دارد که تمام رشته‌های معتبر زبان را شمارش می‌کند. توجه کنید که اگر زبان، نامحدود باشد، الگوریتم شمارنده ارائه شده را می‌توان انتخاب نمود بنابراین از تکرار اجتناب می‌کند، چون ما می‌توانیم آزمایش کنیم که ایا رشته تولید شده برای عدد n، برای عددی تولید می‌شود که کمتر از n می‌باشد. اگر قبلاً تولید شده باشد، از خروجی را برای ورودی n+1 استفاده کنید ولی دوباره آزمایش کنید که آیا، جدید است یا نه.
3. یک زبان شمارش‌پذیر بازگشتی، زبان صوری می‌باشد که برای ان یک ماشین تورینگ وجود دارد که در زمان نمایش دادن با هر رشته در زبان به عنوان ورودی، مکث می‌کند و قبول می‌شود ولی ممکن است هنگام نمایش با رشته‌ای نه در زبان، مکث کند و رد نماید یا برای همیشه در حلقه بیفتد. در مقابل این برای زبان‌های بازگشتی، نیاز است که ماشین تورینگ در تمام موارد و نمونه‌ها مکث نماید.

تمام زبان‌های بازگشتی، حساس به متن، مستقل از متن و منظم، شمارش‌پذیر بازگشتی می‌باشند.
قضیه Post نشان می‌دهد که RE به همراه همتاهای RE کامل خود متناظر با اولین سطح سلسله مراتب ریاضی می‌باشد.

مسئله توقف، r.e می‌باشد نه بازگشتی. فرد می‌تواند ماشین تورینگ را اجرا نماید و قبول کند که ایا دستگاه مکث کند یا نه. از طرفی دیگر، این مشکل، غیرقابل تصمیم گیری می‌باشد. برخی زبان‌های r.e، بازگشتی نمی‌باشند:

• مسئله ارتباطات ارسالی
• مرگ و میر (تئوری قابلیت محاسبه)
• مسئله توقف

زبانهای بازگشتی شمارش پذیر تحت عملیات زیر به هم مربوط می‌شوند. یعنی، اگر L ،P دو زبان شمارش پذیر بازگشتی باشند، انگاه زبان‌های زیر، بازگشتی شمارش پذیر می‌باشند:

• ستاره کلین مربوط به L
• الحاق L ،P
• اجتماع
• اشتراک

توجه کنید که زبان‌های شمارش پذیر برگشتی تحت تفاضل دو مجموعه یا مکمل مجموعه بسته نیستند. تفاوت مجموعه L-P، ممکن است شمارش پذیر بازگشتی باشد و ممکن است بدین صورت نباشد. اگر L، شمارش پذیر بازگشتی باشد، انگاه مکمل L اگر و تنهااگر شمارش پذیر بازگشتی می‌باشد که L بازگشتی باشد.

_

Lecture slides