تابع μ-بازگشتی
در منطق ریاضی و علوم کامپیوتر، توابع μ-بازگشتی گروهی از توابع جزئی از اعداد طبیعی به اعداد طبیعی هستند، که به صورت شهودی «قابل محاسبه» می‌باشند. در واقع، در نظریه رایانش‌پذیری نشان داده شده است که توابع μ-بازگشتی دقیقاً توابعی هستند که می‌توانند با ماشین‌های تورینگ محاسبه شوند. توابع μ-بازگشتی رابطهٔ نزدیکی با توابع بازگشتی اولیه دارند، و تعریف قیاسی آن‌ها (پایین) بر پایه‌ای مشابه با توابع بازگشتی اولیه بنا شده است. با این حال، هر تابع μ-بازگشتی یک تابع بازگشتی اولیه نیست–مشهورترین مثال، تابع آکرمان است.
سایر کلاس‌های معادل توابع، توابع λ-بازگشتی و توابعی هستند که می‌توانند با الگوریتم‌های مارکوف محاسبه شوند.
در نظریهٔ پیچیدگی محاسباتی، مجموعهٔ توابع بازگشتی را تحت عنوان R می‌شناسند.
توابع μ-بازگشتی (یا "توابع μ-بازگشتی جزئی") توابع جزئی هستند که دسته‌های چندتایی متناهی از اعداد طبیعی را می‌گیرند و یک عدد طبیعی منفرد را پس می‌دهند. این توابع کوچک‌ترین کلاس توابع جزئی هستند که شامل توابع اولیه بوده و نسبت به ترکیب، بازگشت اولیه، و عملگر µ بسته می‌باشند.
کوچک‌ترین کلاس توابع که شامل توابع اولیه بوده و نسبت به ترکیب و بازگشت اولیه بسته است (یعنی بدون مینیمم‌سازی)، کلاس توابع بازگشتی اولیه می‌باشد. با این که همهٔ توابع بازگشتی اولیه کامل هستند، اما این موضوع برای توابع بازگشتی جزئی درست نیست؛ برای مثال، مینیمم‌سازی تابع پسین، تعریف‌نشده است. توابع بازگشتی اولیه، زیرمجموعه‌ای از توابع بازگشتی کامل هستند، و توابع بازگشتی کامل زیرمجموعه‌ای از توابع بازگشتی جزئی می‌باشند. برای مثال، می‌توان ثابت کرد که تابع آکرمان یک تابع بازگشتی کامل است، اما اولیه نیست.
توابع اولیه یا «پایه»: در ادامه، زیرنویس‌ها مطابق با (Kleene (۱۹۵۲ صفحهٔ ۲۱۹، هستند. برای کسب اطلاعات بیشتر در مورد نمادگذاری‌های مختلفی که در ادبیات موضوعی به کار رفته‌اند، بخش «نمادگذاری» را در پایین ببینید
تعریف‌های جایگزین، به جای تابع ثابت از ترکیب‌هایی از تابع پسین استفاده می‌کنند، و تابع صفر که همیشه مقدار صفر را برمی‌گرداند را به کار به کار می‌برند.
عملگرها: به طور شهودی، مینیمم‌سازی به دنبال کوچک‌ترین آرگومانی است که باعث شود تابع مقدار صفر را برگرداند (جستجو را از ۰ شروع می‌کند و به سمت بالا پیش می‌رود)؛ اگر چنین آرگومانی وجود نداشته باشد، جستجو هیچ‌گاه به پایان نمی‌رسد.
عملگر برابری قوی formula_21 می‌تواند برای مقایسهٔ توابع μ-بازگشتی به کار روند. این عملگر برای همهٔ توابع جزئی "f" و "g" طوری تعریف شده است که
در صورتی برقرار است که برای هر آرگومان انتخابی، یا هر دو تابع تعریف‌شده باشند و مقادیرشان برابر باشد، یا هر دو تابع تعریف‌نشده باشند،
در هم‌ارزی مدل‌های شماره‌پذیری، پاراللی بین ماشین تورینگ که برای ورودی‌های خاص خاتمه نمی‌پذیرند، و نتیجهٔ تعریف‌نشدهٔ آن ورودی در تابع هدف جزئی، رسم می‌شود. عملگر جستجوی بی‌کران قابل تعریف با قواعد بازگشت اولیه نیست، چون این قواعد مکانیزمی برای «حلقه‌های نامتناهی» (مقادیر تعریف‌نشده) فراهم نمی‌کنند.
قضیهٔ حالت نرمال بر طبق استیون کول کلین می‌گوید که برای هر k، توابع بازگشتی اولیهٔ formula_23 و formula_24 طوری وجود دارند که برای هر تابع μ-بازگشتی formula_25 با k متغیر آزاد، eای وجود دارد که
عدد "e"، "اندیس" یا "عدد Gödel" برای تابع "f" خوانده می‌شود. پیامد این نتیجه آن است که هر تابع μ-بازگشتی می‌تواند با استفاده از یک مورد منفرد اپراتور µ که بر یک تابع بازگشتی اولیه (کامل) اعمال شده باشد، تعریف گردد.
مینسکی (۱۹۷۶) مشاهده کرد که پارامتر U که در عبارت بالا تعریف شده است، به طور ذاتی معادل μ-بازگشتی ماشین تورینگ جهانی می‌باشد (Boolos-)Burgess-Jeffrey (۲۰۰۲ صفحهٔ ۹۴–۹۵ نیز این کار را کرده‌اند): مقدار U را می‌توان با نوشتن تعریف یک تابع بازگشتی-عام (U(n, x که عدد n را به خوبی تفسیر کرده و تابع مناسب x را محاسبه کند، به دست آورد. تولید مستقیم U به همان‌قدر تلاش نیاز دارد و لازم است که به همان اندازه ایده داشته باشیم، چون روی ساخت ماشین تورینگ جهانی سرمایه‌گذاری کرده‌ایم (در اصل italic، مینسکی (۱۹۶۷) صفحهٔ ۱۸۹).
در ادبیات موضوعی از نمادگذاری‌های متفاوتی استفاده شده است. یکی از مزایای استفاده از نمادگذاری این است که مشتق‌گیری از یک تابع با «لانه‌گزینی» عملگرها در همدیگر، ساده‌تر از نوشتن فرم فشرده است. در ادامه، رشته پارامترهای x, … , x را به x خلاصه می‌کنیم: اگر ((h(x)= g(f(x), … , f(x را داشته باشیم، و B-B-J به شکل مشابه ولی بدون زیرنویس و بالانویس می‌نویسد:
" (Pr(base step, induction step)(x" استفاده می‌کند. با فرض:
مثال: تعریف بازگشت اولیهٔ a+b:
مثال Kleene یک مثال ارائه داد که چگونه مشتق را بازگشتی انجام داد. f(b, a) = b + a . با ۳ تابع اولیه شروع کرد :
و به عبارت پایین رسید :