زبان شمارش‌پذیر بازگشتی
در ریاضیات، منطق و علوم کامپیوتر، یک زبان صوری شمارش‌پذیر بازگشتی می‌باشد در صورتی که زیرمجموعه شمارش‌پذیر بازگشتی در مجموعه‌ای از کلمات احتمالی برحسب الفبای زبان وجود داشته باشد، یعنی یک ماشین تورینگ وجود داشته باشد که تمام رشته‌های معتبر زبان را شمارش می‌کند.
زبانهای شمارش‌پذیر بازگشتی، به عنوان زبانهای نوع ۰ در سلسله مراتب چامسکی زبانهای صوری شناخته شده می‌باشند. تمام زبانهای بازگشتی، حساس به متن، مستقل از متن و منظم، شمارش‌پذیر بازگشتی می‌باشند.
کلاسی از تمام زبانهای شمارش‌پذیر بازگشتی، RE نامیده می‌شود.
تعریف‌ها
[ویرایش]تعریف‌های اصلی متناظری برای مفهوم یک زبان شمارش پذیر بازگشتی وجود دارد.
- یک زبان شمارش‌پذیر بازگشتی، یک زیرمجموعه شمارش پذیر بازگشتی در مجموعه‌ای از تمام کلمات ممکن برحسب الفبای زبان می‌باشد.
- یک زبان شمارش‌پذیر بازگشتی، یک زبان صوری می‌باشد که برای آن یک ماشین تورینگ وجود دارد که تمام رشته‌های معتبر زبان را شمارش می‌کند. توجه کنید که اگر زبان، نامحدود باشد، الگوریتم شمارنده ارائه شده را می‌توان انتخاب نمود بنابراین از تکرار اجتناب می‌کند، چون ما می‌توانیم آزمایش کنیم که ایا رشته تولید شده برای عدد n، برای عددی تولید می‌شود که کمتر از n می‌باشد. اگر قبلاً تولید شده باشد، از خروجی را برای ورودی n+1 استفاده کنید ولی دوباره آزمایش کنید که آیا، جدید است یا نه.
- یک زبان شمارش‌پذیر بازگشتی، زبان صوری می‌باشد که برای ان یک ماشین تورینگ وجود دارد که در زمان نمایش دادن با هر رشته در زبان به عنوان ورودی، مکث می‌کند و قبول می‌شود ولی ممکن است هنگام نمایش با رشته‌ای نه در زبان، مکث کند و رد نماید یا برای همیشه در حلقه بیفتد. در مقابل این برای زبانهای بازگشتی، نیاز است که ماشین تورینگ در تمام موارد و نمونه‌ها مکث نماید.
تمام زبانهای بازگشتی، حساس به متن، مستقل از متن و منظم، شمارش‌پذیر بازگشتی می‌باشند.
قضیه Post نشان می‌دهد که RE به همراه همتاهای RE کامل خود متناظر با اولین سطح سلسله مراتب ریاضی می‌باشد.
مثال
[ویرایش]مسئله توقف، r.e می‌باشد نه بازگشتی. فرد می‌تواند ماشین تورینگ را اجرا نماید و قبول کند که ایا دستگاه مکث کند یا نه. از طرفی دیگر، این مشکل، غیرقابل تصمیم گیری می‌باشد. برخی زبانهای r.e، بازگشتی نمی‌باشند:
- مسئله ارتباطات ارسالی
- مرگ و میر (تئوری قابلیت محاسبه)
- مسئله توقف
خواص خاتمه
[ویرایش]زبانهای بازگشتی شمارش پذیر تحت عملیات زیر به هم مربوط می‌شوند. یعنی، اگر L ،P دو زبان شمارش پذیر بازگشتی باشند، انگاه زبانهای زیر، بازگشتی شمارش پذیر می‌باشند:
- ستاره کلین مربوط به L
- الحاق L ،P
- اجتماع
- اشتراک
توجه کنید که زبانهای شمارش پذیر برگشتی تحت تفاضل دو مجموعه یا مکمل مجموعه بسته نیستند. تفاوت مجموعه L-P، ممکن است شمارش پذیر بازگشتی باشد و ممکن است بدین صورت نباشد. اگر L، شمارش پذیر بازگشتی باشد، انگاه مکمل L اگر و تنهااگر شمارش پذیر بازگشتی می‌باشد که L بازگشتی باشد.
منابع
[ویرایش]- مشارکت‌کنندگان ویکی‌پدیا. «Recursively enumerable language». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۴ ژوئن ۲۰۱۳.
_
پیوند به بیرون
[ویرایش]