زبان بازگشتی

در ریاضیات، منطق و علم کامپیوتر، یک زبان رسمی (که مجموعه‌ای از یک سری نماد محدود برگرفته شده از یک الفبای ثابت است) بازگشتی است، اگر زیر مجموعهٔ بازگشتی از مجموعهٔ تمام ترتیب‌های محدود ممکن از الفبای آن زبان باشد. به عبارت دیگر، یک زبان رسمی زمانی بازگشتی نامیده می‌شود که در آنجا یک ماشین تورینگ کلی وجود داشته باشد (ماشین تورینگی که برای هر ورودی ای توقف می‌کند) که هر زمان ترتیب محدودی از نمادها به عنوان ورودی داده شوند، آن را در صورتی قبول کند که به آن زبان مربوط باشد و در غیر اینصورت آن را رد کند. زبان‌های بازگشتی همچنین به عنوان زبان‌های قابل تصمیم‌گیری شناخته می‌شوند.

مفهوم تصمیم پذیری ممکن است به مدل‌های محاسباتی دیگری قابل گسترش باشد. به طور مثال ممکن است کسی در مورد زبان‌های تصمیم پذیر بر روی یک ماشین تورینگ غیر قطعی صحبت کند؛ بنابراین، زمانی که ابهام ممکن باشد، مفهوم معادلی که به جای قابل تصمیم‌گیری برای زبان بازگشتی به کار می‌رود زبان تورینگ تصمیم پذیر است.

کلاس تمامی زبان‌های بازگشتی اغلب R نامیده می‌شود، اگرچه این نام برای کلاس RP نیز استفاده می‌شود. این نوع از زبان در سلسله مراتب چامسکی (مربوط به چامسکی ۱۹۵۹) تعریف نشده است. همهٔ زبان‌های بازگشتی، به طور بازگشتی قابل شمارش نیز هستند. همهٔ زبان‌های منظم، مستقل از متن و حساس به متن نیز بازگشتی هستند.

تعریف

دو تعریف اصلی معادل برای مفهوم زبان بازگشتی وجود دارد:

1. یک زبان رسمی بازگشتی مجموعه‌ای بازگشتی در مجموعهٔ همهٔ کلمات ممکن الفبای یک زباناست.
2. یک زبان بازگشتی، یک زبان رسمی است که برای آن یک ماشین تورینگ وجود دارد به گونه‌ای که هر زمان یک رشته ورودی محدود داده شود، در صورتی که در آن زبان وجود داشته باشد، ماشین متوقف شده و آن را می‌پذیرد، در غیر این صورت متوقف شده و آن را رد می‌کند. ماشین تورینگ همواره متوقف می‌شود، به عنوان یک تصمیم گیرنده معروف است و در مورد زبان بازگشتی تصمیم می‌گیرد.

بر اساس تعریف دوم، هرمسئله تصمیم، می‌تواند با ارائهٔ الگوریتمی برای آن که بر روی همهٔ ورودی‌ها خاتمه می‌یابد، به صورت تصمیم پذیر نشان داده شود. مسئلهٔ غیر تصمیم پذیر، مسئله‌ای است که قابل تصمیم‌گیری نیست.

مثال

همان‌طور که قبلاً گفته شد، هر زبان مستقل از متنی بازگشتی است؛ بنابراین، مثال ساده‌ای از یک زبان بازگشتی مجموعه ... ,L=abc, aabbcc, aaabbbccc است؛ به طور رسمی‌تر، مجموعهٔ $L=\{\,w\in \{a,b,c\}^{*}\mid w=a^{n}b^{n}c^{n}{\mbox{ for some }}n\geq 1\,\}$ حساس به متن و در نتیجه بازگشتی است.

تشریح مثال‌هایی از زبان‌های قابل تصمیم‌گیری که حساس به متن نباشند، سخت‌تر است. برای چنین مثالی، آشنایی اولیه با منطق ریاضی ضروری است: محاسبات پرسبرگر نظریه مرتبه اول اعداد طبیعی به همراه جمع (اما بدون ضرب) هستند. هنگامی که مجموعهٔ فرمول‌های خوش تعریف در محاسبات پرسبرگر $2^{2^{cn}}$ مستقل از متن است، هر ماشین تورینگ قطعی که مجموعه عبارات صحیح در محاسبات پرسبرگر را می‌پذیرد یک زمان اجرای بدترین حالت با حداقل مرتبه برای برخی از ثابت‌های c>0 دارد(فیشر و رابین ۱۹۷۴).

در اینجا n نشان دهندهٔ طول فرمول داده شده است. با توجه به این که هر زبان حساس به متنی می‌تواند توسط یک آتاماتون محدود خطی پذیرفته شود و چنین آتاماتون می‌تواند توسط یک ماشین تورینگ قطعی با زمان اجرای بدترین حالت $c^{n}$ برای برخی مقادیر ثابت C شبیه‌سازی گردد، مجموعه فرمول‌های معتبر در محاسبات پرسبرگر حساس به متن نیستند. در قسمت مثبت، معلوم است که یک ماشین تورینگ قطعی وجود دارد که در زمان اجرای توان سوم n اجرا می‌شود و تصمیم گیرندهٔ مجموعه فرمول‌های صحیح در محاسبه پرسبرگر است(آپن، ۱۹۷۸). بدین ترتیب، این مثالی از یک زبان تصمیم پذیر اما غیر حساس به متن بود.

ویژگی‌های خاتمه

زبان‌های بازگشتی تحت عملیات زیر خاتمه می‌یابند. یعنی اگر L و P دو زبان بازگشتی باشند، آن گاه زبان‌های زیر نیز بازگشتی هستند:

• کلینی استار $L^{*}$
• تصویر (φ)L تحت همریختی آزاد φ
• ترکیب $L\circ P$
• اجتماع $L\cup P$
• اشتراک $L\cap P$
• مکمل $L$
• تفاضل مجموعه $L-P$

آخرین ویژگی از این حقیقت پیروی می‌کند که اختلاف مجموعه می‌تواند به صورت اشتراک و مکمل نمایش داده شود.

جستارهای وابسته

• زبان شمارش‌پذیر بازگشتی
• قواعد بازگشتی

منابع

• Michael Sipser (1997). "Decidability". Introduction to the Theory of Computation. PWS Publishing. pp. 151–170. ISBN 0-534-94728-X.
• Chomsky, Noam (1959). "On certain formal properties of grammars". Information and Control. 2 (2): 137–167. doi:10.1016/S0019-9958(59)90362-6.
• Fischer, Michael J.; Rabin, Michael O. (1974). "Super-Exponential Complexity of Presburger Arithmetic". Proceedings of the SIAM-AMS Symposium in Applied Mathematics. 7: 27–41. Archived from the original on 15 September 2006. Retrieved 4 May 2015.
• Oppen, Derek C. (1978). "A 2²2^pn Upper Bound on the Complexity of Presburger Arithmetic" (PDF). J. Comput. Syst. Sci. 16 (3): 323–332. doi:10.1016/0022-0000(78)90021-1.