زبان بازگشتی

در ریاضیات، منطق و علم کامپیوتر، یک زبان رسمی (که مجموعه ای از یک سری نماد محدود برگرفته شده از یک الفبای ثابت است) بازگشتی است، اگر زیر مجموعهٔ بازگشتی از مجموعهٔ تمام ترتیب های محدود ممکن از الفبای آن زبان باشد. به عبارت دیگر، یک زبان رسمی زمانی بازگشتی نامیده می شود که در آنجا یک ماشین تورینگ کلی وجود داشته باشد (ماشین تورینگی که برای هر ورودی ای توقف می کند) که هر زمان ترتیب محدودی از نمادها به عنوان ورودی داده شوند، آن را در صورتی قبول کند که به آن زبان مربوط باشد و در غیر اینصورت آن را رد کند. زبان های بازگشتی همچنین به عنوان زبان های قابل تصمیم گیری شناخته می شوند.
کلینی استار L ∗ {\displaystyle L^{*}}
تصویر (φ)L تحت همریختی آزاد φ
ترکیب L ∘ P {\displaystyle L\circ P}
اجتماع L ∪ P {\displaystyle L\cup P}
اشتراک L ∩ P {\displaystyle L\cap P}
مکمل L {\displaystyle L}
تفاضل مجموعه L − P {\displaystyle L-P}
مفهوم تصمیم پذیری ممکن است به مدل های محاسباتی دیگری قابل گسترش باشد. به طور مثال ممکن است کسی در مورد زبان های تصمیم پذیر بر روی یک ماشین تورینگ غیر قطعی صحبت کند؛ بنابراین، زمانی که ابهام ممکن باشد، مفهوم معادلی که به جای قابل تصمیم گیری برای زبان بازگشتی به کار می رود زبان تورینگ تصمیم پذیر است.
کلاس تمامی زبان های بازگشتی اغلب R نامیده می شود، اگرچه این نام برای کلاس RP نیز استفاده می شود.این نوع از زبان در سلسله مراتب چامسکی (مربوط به چامسکی ۱۹۵۹) تعریف نشده است. همهٔ زبان های بازگشتی، به طور بازگشتی قابل شمارش نیز هستند. همهٔ زبان های منظم، مستقل از متن و حساس به متن نیز بازگشتی هستند.
دو تعریف اصلی معادل برای مفهوم زبان بازگشتی وجود دارد: