تابع μ -بازگشتی
در منطق ریاضی و علوم کامپیوتر، توابع
سایر کلاسهای معادل توابع، توابع
در نظریهٔ پیچیدگی محاسباتی، مجموعهٔ توابع بازگشتی را تحت عنوان R میشناسند.
تعریف[ویرایش]
توابع
کوچکترین کلاس توابع که شامل توابع اولیه بوده و نسبت به ترکیب و بازگشت اولیه بسته است (یعنی بدون مینیممسازی)، کلاس توابع بازگشتی اولیه میباشد. با این که همهٔ توابع بازگشتی اولیه کامل هستند، اما این موضوع برای توابع بازگشتی جزئی درست نیست؛ برای مثال، مینیممسازی تابع پسین، تعریفنشده است. توابع بازگشتی اولیه، زیرمجموعهای از توابع بازگشتی کامل هستند، و توابع بازگشتی کامل زیرمجموعهای از توابع بازگشتی جزئی میباشند. برای مثال، میتوان ثابت کرد که تابع آکرمان یک تابع بازگشتی کامل است، اما اولیه نیست.
توابع اولیه یا «پایه»: در ادامه، زیرنویسها مطابق با (Kleene (۱۹۵۲ صفحهٔ ۲۱۹، هستند. برای کسب اطلاعات بیشتر در مورد نمادگذاریهای مختلفی که در ادبیات موضوعی به کار رفتهاند، بخش «نمادگذاری» را در پایین ببینید
- تابع ثابت: برای هر عدد طبیعی و هر :
- .
تعریفهای جایگزین، به جای تابع ثابت از ترکیبهایی از تابع پسین استفاده میکنند، و تابع صفر که همیشه مقدار صفر را برمیگرداند را به کار به کار میبرند.
- تابع پسین S:
- تابع تصویر ((به آن تابع هویت نیز میگویند ): برای همهٔ اعداد طبیعی که در آنها :
- .
عملگرها:
- عملگر ترکیب (که به آن عملگر تعویض نیز میگویند): با فرض یک تابع m-تایی و mتا تابع k-تایی :
- .
- عملگر بازگشت اولیه : با فرض تابع k-تایی و تابع k+2-تایی :
- .
- عملگر مینیممسازی : با فرض تابع کامل k+1-تایی :
به طور شهودی، مینیممسازی به دنبال کوچکترین آرگومانی است که باعث شود تابع مقدار صفر را برگرداند (جستجو را از ۰ شروع میکند و به سمت بالا پیش میرود)؛ اگر چنین آرگومانی وجود نداشته باشد، جستجو هیچگاه به پایان نمیرسد.
عملگر برابری قوی میتواند برای مقایسهٔ توابع
در صورتی برقرار است که برای هر آرگومان انتخابی، یا هر دو تابع تعریفشده باشند و مقادیرشان برابر باشد، یا هر دو تابع تعریفنشده باشند،
همارزی مدلهای شمارهپذیری[ویرایش]
در همارزی مدلهای شمارهپذیری، پاراللی بین ماشین تورینگ که برای ورودیهای خاص خاتمه نمیپذیرند، و نتیجهٔ تعریفنشدهٔ آن ورودی در تابع هدف جزئی، رسم میشود. عملگر جستجوی بیکران قابل تعریف با قواعد بازگشت اولیه نیست، چون این قواعد مکانیزمی برای «حلقههای نامتناهی» (مقادیر تعریفنشده) فراهم نمیکنند.
قضیهٔ حالت نرمال[ویرایش]
قضیهٔ حالت نرمال بر طبق استیون کول کلین میگوید که برای هر k، توابع بازگشتی اولیهٔ و طوری وجود دارند که برای هر تابع
- .
عدد e، اندیس یا عدد Gödel برای تابع f خوانده میشود. پیامد این نتیجه آن است که هر تابع
مینسکی (۱۹۷۶) مشاهده کرد که پارامتر U که در عبارت بالا تعریف شده است، به طور ذاتی معادل
نمادگذاری[ویرایش]
در ادبیات موضوعی از نمادگذاریهای متفاوتی استفاده شده است. یکی از مزایای استفاده از نمادگذاری این است که مشتقگیری از یک تابع با «لانهگزینی» عملگرها در همدیگر، سادهتر از نوشتن فرم فشرده است. در ادامه، رشته پارامترهای x1, … , xn را به x خلاصه میکنیم:
- تابع ثابت: Kleene از " Cqn(x) = q " و (Boolos-Burgess-Jeffrey (2002) (B-B-J از اختصار " constn(x) = n " استفاده میکند:
- e.g. C137 (r, s, t, u, v, w, x) = ۱۳
- e.g. const13 (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 (۱۹۵۲ از " Uin " برای اشاره به تابع هویت روی متغیرهای "xi" استفاده میکند، و B-B-J از تابع هویت "idin" روی متغیرهای "x1" تا "xn" استفاده مینماید:
- Uin(x) = idin(x) = xi
- e.g. U37 = id37 (r, s, t, u, v, w, x) = t
- عملگر ترکیب (تعویض): Kleene از حرف برجستهٔ Snm استفاده میکند (با S نمایندهٔ "پسین" اشتباه نشود). بالانویس "m" به m-اُمین تابع "fm"، و زیرنویس "n" به n-اُمین متغیر "xn" اشاره دارد:
اگر ((h(x)= g(f1(x), … , fm(x را داشته باشیم،
- (h(x) = Smn(g, f1, … , fm
و B-B-J به شکل مشابه ولی بدون زیرنویس و بالانویس مینویسد:
- ('h(x)= Cn[g, f1 ,..., fm](x
- بازگشت اولیه: Kleene از نماد " (Rn(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 = U11(a
- (induction step: f(b' , a) = (f (b, a))' = g(b, f(b, a), a) = g(b, c, a) = c' = S(U23(b, c, a
- (R2 U11(a), S (U23( b, c, a)
- ( Pr U11(a), S (U23( b, c, a
مثال Kleene یک مثال ارائه داد که چگونه مشتق را بازگشتی انجام داد. f(b, a) = b + a . با ۳ تابع اولیه شروع کرد :
- 'S(a) = a
- U11(a) = a
- U23( b, c, a ) = c
- 'g(b, c, a) = S(U23( b, c, a )) = c
- (base step: h( 0, a ) = U11(a
- (induction step: h( b', a ) = g( b, h( b, a ), a
و به عبارت پایین رسید :
- [ ( a+b = R2[ U11, S13(S, U23
نمونهها[ویرایش]
جستارهای وابسته[ویرایش]
منابع[ویرایش]
- استیون کول کلین (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]