تابع μ بازگشتی

در منطق ریاضی و علوم کامپیوتر، توابع μ-بازگشتی گروهی از توابع جزئی از اعداد طبیعی به اعداد طبیعی هستند، که به صورت شهودی «قابل محاسبه» می باشند. در واقع، در نظریه رایانش پذیری نشان داده شده است که توابع μ-بازگشتی دقیقاً توابعی هستند که می توانند با ماشین های تورینگ محاسبه شوند. توابع μ-بازگشتی رابطهٔ نزدیکی با توابع بازگشتی اولیه دارند، و تعریف قیاسی آن ها (پایین) بر پایه ای مشابه با توابع بازگشتی اولیه بنا شده است. با این حال، هر تابع μ-بازگشتی یک تابع بازگشتی اولیه نیست–مشهورترین مثال، تابع آکرمان است.
تابع ثابت: Kleene از " Cqn(x) = q " و (Boolos-Burgess-Jeffrey (2002) (B-B-J از اختصار " constn(x) = n " استفاده می کند:
سایر کلاس های معادل توابع، توابع λ-بازگشتی و توابعی هستند که می توانند با الگوریتم های مارکوف محاسبه شوند.
در نظریهٔ پیچیدگی محاسباتی، مجموعهٔ توابع بازگشتی را تحت عنوان R می شناسند.
توابع μ-بازگشتی (یا توابع μ-بازگشتی جزئی) توابع جزئی هستند که دسته های چندتایی متناهی از اعداد طبیعی را می گیرند و یک عدد طبیعی منفرد را پس می دهند. این توابع کوچک ترین کلاس توابع جزئی هستند که شامل توابع اولیه بوده و نسبت به ترکیب، بازگشت اولیه، و عملگر µ بسته می باشند.