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

در منطق ریاضی و علوم کامپیوتر، توابع μ-بازگشتی گروهی از توابع جزئی از اعداد طبیعی به اعداد طبیعی هستند، که به صورت شهودی «قابل محاسبه» می‌باشند. در واقع، در نظریه رایانش‌پذیری نشان داده شده است که توابع μ-بازگشتی دقیقاً توابعی هستند که می‌توانند با ماشین‌های تورینگ محاسبه شوند. توابع μ-بازگشتی رابطهٔ نزدیکی با توابع بازگشتی اولیه دارند، و تعریف قیاسی آن‌ها (پایین) بر پایه‌ای مشابه با توابع بازگشتی اولیه بنا شده است. با این حال، هر تابع μ-بازگشتی یک تابع بازگشتی اولیه نیست–مشهورترین مثال، تابع آکرمان است.

سایر کلاس‌های معادل توابع، توابع λ-بازگشتی و توابعی هستند که می‌توانند با الگوریتم‌های مارکوف محاسبه شوند.

در نظریهٔ پیچیدگی محاسباتی، مجموعهٔ توابع بازگشتی را تحت عنوان R می‌شناسند.

تعریف

توابع μ-بازگشتی (یا توابع μ-بازگشتی جزئی) توابع جزئی هستند که دسته‌های چندتایی متناهی از اعداد طبیعی را می‌گیرند و یک عدد طبیعی منفرد را پس می‌دهند. این توابع کوچک‌ترین کلاس توابع جزئی هستند که شامل توابع اولیه بوده و نسبت به ترکیب، بازگشت اولیه، و عملگر µ بسته می‌باشند.

کوچک‌ترین کلاس توابع که شامل توابع اولیه بوده و نسبت به ترکیب و بازگشت اولیه بسته است (یعنی بدون مینیمم‌سازی)، کلاس توابع بازگشتی اولیه می‌باشد. با این که همهٔ توابع بازگشتی اولیه کامل هستند، اما این موضوع برای توابع بازگشتی جزئی درست نیست؛ برای مثال، مینیمم‌سازی تابع پسین، تعریف‌نشده است. توابع بازگشتی اولیه، زیرمجموعه‌ای از توابع بازگشتی کامل هستند، و توابع بازگشتی کامل زیرمجموعه‌ای از توابع بازگشتی جزئی می‌باشند. برای مثال، می‌توان ثابت کرد که تابع آکرمان یک تابع بازگشتی کامل است، اما اولیه نیست.

توابع اولیه یا «پایه»: در ادامه، زیرنویس‌ها مطابق با (Kleene (۱۹۵۲ صفحهٔ ۲۱۹، هستند. برای کسب اطلاعات بیشتر در مورد نمادگذاری‌های مختلفی که در ادبیات موضوعی به کار رفته‌اند، بخش «نمادگذاری» را در پایین ببینید

1. تابع ثابت: برای هر عدد طبیعی $n\,$ و هر $k\,$:

$f(x_{1},\ldots ,x_{k})=n\,$.

تعریف‌های جایگزین، به جای تابع ثابت از ترکیب‌هایی از تابع پسین استفاده می‌کنند، و تابع صفر که همیشه مقدار صفر را برمی‌گرداند را به کار به کار می‌برند.

1. تابع پسین S:

$S(x){\stackrel {\mathrm {def} }{=}}f(x)=x+1\,$

1. تابع تصویر $P_{i}^{k}$ ((به آن تابع هویت نیز می‌گویند $I_{i}^{k}$): برای همهٔ اعداد طبیعی $i,k\,$ که در آن‌ها $1\leq i\leq k$:

$P_{i}^{k}{\stackrel {\mathrm {def} }{=}}f(x_{1},\ldots ,x_{k})=x_{i}$.

عملگرها:

1. عملگر ترکیب $\circ \,$ (که به آن عملگر تعویض نیز می‌گویند): با فرض یک تابع m-تایی $h(x_{1},\ldots ,x_{m})\,$ و mتا تابع k-تایی $g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k})$:

${\begin{aligned}h\circ (g_{1},\ldots ,g_{m}){\stackrel {\mathrm {def} }{=}}f\quad {\text{where}}\quad f(x_{1},\ldots ,x_{k})=h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}))\,.\end{aligned}}$.

1. عملگر بازگشت اولیه $\rho \,$: با فرض تابع k-تایی $g(x_{1},\ldots ,x_{k})\,$ و تابع k+2-تایی $h(y,z,x_{1},\ldots ,x_{k})\,$:

${\begin{aligned}\rho (g,h)&{\stackrel {\mathrm {def} }{=}}f(y,x_{1},\ldots ,x_{k})\quad {\rm {where}}\\f(0,x_{1},\ldots ,x_{k})&=g(x_{1},\ldots ,x_{k})\\f(y+1,x_{1},\ldots ,x_{k})&=h(y,f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})\,\end{aligned}}$.

1. عملگر مینیمم‌سازی $\mu \,$: با فرض تابع کامل k+1-تایی $f(y,x_{1},\ldots ,x_{k})\,$:

${\begin{aligned}\mu (f)(x_{1},\ldots ,x_{k})=z{\stackrel {\mathrm {def} }{\iff }}\ f(z,x_{1},\ldots ,x_{k})&=0\quad {\text{and}}\\f(i,x_{1},\ldots ,x_{k})&>0\quad {\text{for}}\ i=0,\ldots ,z-1.\end{aligned}}$

به طور شهودی، مینیمم‌سازی به دنبال کوچک‌ترین آرگومانی است که باعث شود تابع مقدار صفر را برگرداند (جستجو را از ۰ شروع می‌کند و به سمت بالا پیش می‌رود)؛ اگر چنین آرگومانی وجود نداشته باشد، جستجو هیچ‌گاه به پایان نمی‌رسد.

عملگر برابری قوی $\simeq$ می‌تواند برای مقایسهٔ توابع μ-بازگشتی به کار روند. این عملگر برای همهٔ توابع جزئی f و g طوری تعریف شده است که

$f(x_{1},\ldots ,x_{k})\simeq g(x_{1},\ldots ,x_{l})$

در صورتی برقرار است که برای هر آرگومان انتخابی، یا هر دو تابع تعریف‌شده باشند و مقادیرشان برابر باشد، یا هر دو تابع تعریف‌نشده باشند،

هم‌ارزی مدل‌های شماره‌پذیری

در هم‌ارزی مدل‌های شماره‌پذیری، پاراللی بین ماشین تورینگ که برای ورودی‌های خاص خاتمه نمی‌پذیرند، و نتیجهٔ تعریف‌نشدهٔ آن ورودی در تابع هدف جزئی، رسم می‌شود. عملگر جستجوی بی‌کران قابل تعریف با قواعد بازگشت اولیه نیست، چون این قواعد مکانیزمی برای «حلقه‌های نامتناهی» (مقادیر تعریف‌نشده) فراهم نمی‌کنند.

قضیهٔ حالت نرمال

قضیهٔ حالت نرمال بر طبق استیون کول کلین می‌گوید که برای هر k، توابع بازگشتی اولیهٔ $U(y)\!$ و $T(y,e,x_{1},\ldots ,x_{k})\!$ طوری وجود دارند که برای هر تابع μ-بازگشتی $f(x_{1},\ldots ,x_{k})\!$ با k متغیر آزاد، eای وجود دارد که

$f(x_{1},\ldots ,x_{k})\simeq U(\mu y\,T(y,e,x_{1},\ldots ,x_{k}))$.

عدد e، اندیس یا عدد Gödel برای تابع f خوانده می‌شود. پیامد این نتیجه آن است که هر تابع μ-بازگشتی می‌تواند با استفاده از یک مورد منفرد اپراتور µ که بر یک تابع بازگشتی اولیه (کامل) اعمال شده باشد، تعریف گردد.

مینسکی (۱۹۷۶) مشاهده کرد که پارامتر U که در عبارت بالا تعریف شده است، به طور ذاتی معادل μ-بازگشتی ماشین تورینگ جهانی می‌باشد (Boolos-)Burgess-Jeffrey (۲۰۰۲ صفحهٔ ۹۴–۹۵ نیز این کار را کرده‌اند): مقدار U را می‌توان با نوشتن تعریف یک تابع بازگشتی-عام (U(n, x که عدد n را به خوبی تفسیر کرده و تابع مناسب x را محاسبه کند، به دست آورد. تولید مستقیم U به همان‌قدر تلاش نیاز دارد و لازم است که به همان اندازه ایده داشته باشیم، چون روی ساخت ماشین تورینگ جهانی سرمایه‌گذاری کرده‌ایم (در اصل italic، مینسکی (۱۹۶۷) صفحهٔ ۱۸۹).

نمادگذاری

در ادبیات موضوعی از نمادگذاری‌های متفاوتی استفاده شده است. یکی از مزایای استفاده از نمادگذاری این است که مشتق‌گیری از یک تابع با «لانه‌گزینی» عملگرها در همدیگر، ساده‌تر از نوشتن فرم فشرده است. در ادامه، رشته پارامترهای x₁, … , x_n را به x خلاصه می‌کنیم:

• تابع ثابت: Kleene از " C_qⁿ(x) = q " و (Boolos-Burgess-Jeffrey (2002) (B-B-J از اختصار " const_n(x) = n " استفاده می‌کند:

e.g. C₁₃⁷ (r, s, t, u, v, w, x) = ۱۳

e.g. const₁₃ (r, s, t, u, v, w, x) = ۱۳

• تابع پسین: Kleene از x' و S برای «پسین» استفاده می‌کند. از آن‌ا که «پسین» اولیه لحاظ می‌شود، بیشتر متن‌ها به صورت زیر از آپاستروف استفاده می‌کنند:

S(a) = a +1 =_def a', where 1 =_def 0', 2 =_def 0 ' ', etc.

• تابع هویت: (Kleene (۱۹۵۲ از " U_iⁿ " برای اشاره به تابع هویت روی متغیرهای "x_i" استفاده می‌کند، و B-B-J از تابع هویت "id_iⁿ" روی متغیرهای "x₁" تا "x_n" استفاده می‌نماید:

U_iⁿ(x) = id_iⁿ(x) = x_i

e.g. U₃⁷ = id₃⁷ (r, s, t, u, v, w, x) = t

• عملگر ترکیب (تعویض): Kleene از حرف برجستهٔ S_n^m استفاده می‌کند (با S نمایندهٔ "پسین" اشتباه نشود). بالانویس "m" به m-اُمین تابع "f_m"، و زیرنویس "n" به n-اُمین متغیر "x_n" اشاره دارد:

اگر ((h(x)= g(f₁(x), … , f_m(x را داشته باشیم،

(h(x) = S_mⁿ(g, f₁, … , f_m

و B-B-J به شکل مشابه ولی بدون زیرنویس و بالانویس می‌نویسد:

('h(x)= Cn[g, f₁ ,..., f_m](x

• بازگشت اولیه: Kleene از نماد " (Rⁿ(base step, induction step " استفاده می‌کند، که n در آن تعداد متغیرها را نشان می‌دهد. B-B-J از

" (Pr(base step, induction step)(x" استفاده می‌کند. با فرض:

• (base step: h(0, x)= f(x، و
• (induction step: h(y+1, x) = g(y, h(y, x),x

مثال: تعریف بازگشت اولیهٔ a+b:

• (base step: f(0, a) = a = U₁¹(a
• (induction step: f(b' , a) = (f (b, a))' = g(b, f(b, a), a) = g(b, c, a) = c' = S(U₂³(b, c, a

(R² U₁¹(a), S (U₂³( b, c, a)

( Pr U₁¹(a), S (U₂³( b, c, a

مثال Kleene یک مثال ارائه داد که چگونه مشتق را بازگشتی انجام داد. f(b, a) = b + a . با ۳ تابع اولیه شروع کرد :

1. 'S(a) = a
2. U₁¹(a) = a
3. U₂³( b, c, a ) = c
4. 'g(b, c, a) = S(U₂³( b, c, a )) = c
5. (base step: h( 0, a ) = U₁¹(a

(induction step: h( b', a ) = g( b, h( b, a ), a

و به عبارت پایین رسید :

[ ( a+b = R²[ U₁¹, S₁³(S, U₂³

نمونه‌ها

• اعداد فیبوناچی
• McCarthy 91 function

جستارهای وابسته

• نظریه رایانش‌پذیری
• بازگشت
• توابع بازگشتی

منابع

• استیون کول کلین (1952) Introduction to Metamathematics. Walters-Noordhoff & North-Holland, with corrections (6th imprint 1971); Tenth impression 1991, ISBN 0-7204-2103-9.
• Soare, R. Recursively enumerable sets and degrees. Springer-Verlag 1987.
• ماروین مینسکی (1967), Computation: Finite and Infinite Machines, Prentice-Hall, Inc. Englewood Cliffs, N.J.

On pages 210-215 Minsky shows how to create the μ-operator using the register machine model, thus demonstrating its equivalence to the general recursive functions.

• George Boolos, John Burgess, Richard Jeffrey (2002), Computability and Logic: Fourth Edition, Cambridge University Press, Cambridge, UK. Cf pp. ۷۰–۷۱.

پیوند خارجی

• Stanford Encyclopedia of Philosophy entry
• http://people.irisa.fr/Francois.Schwarzentruber/recursive_functions_to_turing_machines/ A compiler for transforming a recursive function into an] equivalent Turing machine]