زبان بازگشتی

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

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

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

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

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

در اینجا n نشان دهندهٔ طول فرمول داده شده است. با توجه به این که هر زبان حساس به متنی می‌تواند توسط یک آتاماتون محدود خطی پذیرفته شود و چنین آتاماتون می‌تواند توسط یک ماشین تورینگ قطعی با زمان اجرای بدترین حالت ${\displaystyle c^n}$

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

• کلینی استار ${\displaystyle L^{\ast }}$
• تصویر (φ)L تحت همریختی آزاد φ
• ترکیب ${\displaystyle L\circ P}$
• اجتماع ${\displaystyle L\cup P}$
• اشتراک ${\displaystyle L\cap P}$
• مکمل ${\displaystyle L}$
• تفاضل مجموعه ${\displaystyle 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 22 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.