موضوع مقاله: تابع μ-بازگشتی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # تابع μ-بازگشتی | مقدمه: در واقع، در نظریه رایانش‌پذیری نشان داده شده است که توابع μ-بازگشتی دقیقاً توابعی هستند که می‌توانند با ماشین‌های تورینگ محاسبه شوند. | ## بخش 1: تابع μ-بازگشتی | توابع μ-بازگشتی رابطهٔ نزدیکی با توابع بازگشتی اولیه دارند، و تعریف قیاسی آن‌ها (پایین) بر پایه‌ای مشابه با توابع بازگشتی اولیه بنا شده است. با این حال، هر تابع μ-بازگشتی یک تابع بازگشتی اولیه نیست–مشهورترین مثال، تابع آکرمان است. سایر کلاس‌های معادل توابع، توابع λ-بازگشتی و توابعی هستند که می‌توانند با الگوریتم‌های مارکوف محاسبه شوند. تعریف توابع μ-بازگشتی (یا توابع μ-بازگشتی جزئی) توابع جزئی هستند که دسته‌های چندتایی متناهی از اعداد طبیعی را می‌گیرند و یک عدد طبیعی منفرد را پس می‌دهند. این توابع کوچک‌ترین کلاس توابع جزئی هستند که شامل توابع اولیه بوده و نسبت به ترکیب، بازگشت اولیه، و عملگر µ بسته می‌باشند. کوچک‌ترین کلاس توابع که شامل توابع اولیه بوده و نسبت به ترکیب و بازگشت اولیه بسته است (یعنی بدون مینیمم‌سازی)، کلاس توابع بازگشتی اولیه می‌باشد. با این که همهٔ توابع بازگشتی اولیه کامل هستند، اما این موضوع برای توابع بازگشتی جزئی درست نیست؛ برای مثال، مینیمم‌سازی تابع پسین، تعریف‌نشده است. | ## بخش 2: تابع μ-بازگشتی | توابع بازگشتی اولیه، زیرمجموعه‌ای از توابع بازگشتی کامل هستند، و توابع بازگشتی کامل زیرمجموعه‌ای از توابع بازگشتی جزئی می‌باشند. برای مثال، می‌توان ثابت کرد که تابع آکرمان یک تابع بازگشتی کامل است، اما اولیه نیست. توابع اولیه یا «پایه»: در ادامه، زیرنویس‌ها مطابق با (Kleene (۱۹۵۲ صفحهٔ ۲۱۹، هستند. برای کسب اطلاعات بیشتر در مورد نمادگذاری‌های مختلفی که در ادبیات موضوعی به کار رفته‌اند، بخش «نمادگذاری» را در پایین ببینید تابع ثابت: برای هر عدد طبیعی و هر : . تعریف‌های جایگزین، به جای تابع ثابت از ترکیب‌هایی از تابع پسین استفاده می‌کنند، و تابع صفر که همیشه مقدار صفر را برمی‌گرداند را به کار به کار می‌برند. تابع پسین S: تابع تصویر به آن تابع هویت نیز می‌گویند ): برای همهٔ اعداد طبیعی که در آن‌ها : . عملگرها: عملگر ترکیب (که به آن عملگر تعویض نیز می‌گویند): با فرض یک تابع m-تایی و mتا تابع k-تایی : . | ## بخش 3: تابع μ-بازگشتی | عملگر مینیمم‌سازی : با فرض تابع کامل k+1-تایی : به طور شهودی، مینیمم‌سازی به دنبال کوچک‌ترین آرگومانی است که باعث شود تابع مقدار صفر را برگرداند (جستجو را از ۰ شروع می‌کند و به سمت بالا پیش می‌رود)؛ اگر چنین آرگومانی وجود نداشته باشد، جستجو هیچ‌گاه به پایان نمی‌رسد. این عملگر برای همهٔ توابع جزئی f و g طوری تعریف شده است که در صورتی برقرار است که برای هر آرگومان انتخابی، یا هر دو تابع تعریف‌شده باشند و مقادیرشان برابر باشد، یا هر دو تابع تعریف‌نشده باشند، هم‌ارزی مدل‌های شماره‌پذیری در هم‌ارزی مدل‌های شماره‌پذیری، پاراللی بین ماشین تورینگ که برای ورودی‌های خاص خاتمه نمی‌پذیرند، و نتیجهٔ تعریف‌نشدهٔ آن ورودی در تابع هدف جزئی، رسم می‌شود. عملگر جستجوی بی‌کران قابل تعریف با قواعد بازگشت اولیه نیست، چون این قواعد مکانیزمی برای «حلقه‌های نامتناهی» (مقادیر تعریف‌نشده) فراهم نمی‌کنند. قضیهٔ حالت نرمال قضیهٔ حالت نرمال بر طبق استیون کول کلین می‌گوید که برای هر k، توابع بازگشتی اولیهٔ و طوری وجود دارند که برای هر تابع μ-بازگشتی با k متغیر آزاد، eای وجود دارد که . پیامد این نتیجه آن است که هر تابع μ-بازگشتی می‌تواند با استفاده از یک مورد منفرد اپراتور µ که بر یک تابع بازگشتی اولیه (کامل) اعمال شده باشد، تعریف گردد. تولید مستقیم U به همان‌قدر تلاش نیاز دارد و لازم است که به همان اندازه ایده داشته باشیم، چون روی ساخت ماشین تورینگ جهانی سرمایه‌گذاری کرده‌ایم (در اصل italic، مینسکی (۱۹۶۷) صفحهٔ ۱۸۹). | ## جمع‌بندی | یکی از مزایای استفاده از نمادگذاری این است که مشتق‌گیری از یک تابع با «لانه‌گزینی» عملگرها در همدیگر، ساده‌تر از نوشتن فرم فشرده است.