توابع بازگشتی نخستینی (Recursive Primitive Functions)

■ مقدمه

در نظریه رایانش، یک تابع بازگشتی-نخستینی تابعی است که می‌تواند توسط یک ماشین اندوختگانی رایانش شود، به قسمی که چرخه‌های این رایانش همگی چرخه کراندار باشند.

«تئوری توابع بازگشتی» (Recursive Functions theory) که اکنون «نظریه رایانش» (Theory of Computation) نامیده می‌شود، پاسخ دقیقی به چیستی یک الگوریتم است. در واقع، نظریه رایانش بخشی از منطق ریاضی است که در پی پیکربندی دقیق برای مفاهیم الگوریتم، روند مکانیکی (روند ماشینی) و توابع رایانش‌پذیر (نیز مجموعه‌ها و رابطه‌های رایانش‌پذیر) و سرانجام ارائه متدولوژی برای بازشناختن آنچه رایانش ‌پذیر نیست است. ما در این یادداشت و سه یادداشت بعد با جزئيات درخور به مرور این نظریه خواهیم پرداخت.

■ دستگاه توابع بازگشتی-نخستینی (Primitive Recursive Functions)

توابع آمده در فهرست زیر، یعنی A۲ ،A۱ و A۳، را به عنوان توابع پیشینی بازگشتی-نخستینی در دستگاه توابع بازگشتی-نخستینی معرفی می‌کنیم.

■ مجموعه بازگشتی-نخستینی (Primitive recursive sets)

گیریم A یک مجموعه باشد، آنگاه A را یک مجموعه بازگشتی-نخستینی (مجموعه تصمیم پذیر بازگشتی-نخستینی) گوییم اگر تابع مشخصه آن P.r باشد.

■ رابطه بازگشتی-نخستینی (Primitive recursive relations)

گیریم R یک رابطه باشد، آنگاه R را یک رابطه بازگشتی-نخستینی (نیز رابطه تصمیم پذیر بازگشتی-نخستینی) گوییم اگر تابع مشخصه آن بازگشتی-نخستینی باشد.

مثال:

فرض کنید l یک تابع دو متغیری باشد. تابع f را به قرار زیر تعریف می‌کنیم:

f(x, b) = l(x, ۰) + ۲l(x, ۱) + . . . + (b + ۱)l(x, b).

برای اینکه نشان دهیم تابع f یک تابع P.r است دو تابع g و H که P.r هستند را یافته و نشان می‌دهیم f از g و H با کارزدن قاعد R۲ به دست می‌آید.

تابع g را به قرار زیر تعریف می‌کنیم:

a'۱: g(x) = l(x, ۰).

برای تعریف H بنابر تعریف f می‌توان نوشت:

f(x, b + ۱) =
= l(x, ۰) + ۲l(x, ۱) + . . . + (b + ۱)l(x, b) + (b + ۲)l(x, b +۱) =
= f(x, b) + (b + ۲)l(x, b +۱)

از طرفی، H باید در رابطه زیر صدق کند:

f(x, b + ۱) = H(x, b, f(x, b)).

بنابراین H به قرار زیر خواهد بود:

a'۲:H(x, b, y). = y + (b + ۲)l(x, b +۱)

■ تابع کاهش

نشان می‌دهیم تابع کاهش، D، (نیز موسوم به تابع پیشین - Decrease function - Predecessor function)، تعریف شده در زیر، P.r است.

D(x)	=
			D(۰) = D(۱) =۰
			D(x) = x - ۱

می‌نویسیم:

D(S(x))	=
			D(۰) = D(۱) =Z(x)
			= H(x, D (x)) = = S(π۲(x, D(x)))

■ تابع جمع

نشان می‌دهیم تابع sum (جمع) P.r است.

می‌نویسیم:

sum(x۱, S(x۲))	=
			sum(x۱, ۰) = g(x۱) = π<۱, ۱>(x۱)
			= H(x۱, x۲ , sum (x۱, x۲)) = = S(π<۳, ۳>(x۱, x۲, sum(x۱, x۲))

■ تابع تفریق کوتاه شده (Truncated subtraction function)

 نشان می‌دهیم تابع تفریق کوتاه شده، "∸"، که در زیر تعریف شده است، P.r است.

x۱ ∸ x۲	=
			۰	x۱ < x۲
			x۱ - x۲	x۱ ≥ x۲

می‌نویسیم:

dif(x۱, S(x۲))	=
			g(x۱) = Z(x۱)	x۱ < x۲
			= H(x۱, x۲ , dif (x۱, x۲)) = = D(π۳(x۱, x۲, dif(x۱, x۲))	x۱ ≥ x۲

■ تابع قدر مطلق

تابع قدر مطلق |x - y| یک تابع P.r است:

|x - y| = (x ∸ y) + (y ∸ x)

■ تابع علامت

تابع علامت sgn(x) یک تابع P.r است:

sgn(x)	=
			۱	x ≠ ۰
			۰	وگرنه

sgn(x) = ۱∸ (۱ ∸ x)

■ رابطه‌های کوچکتر و تساوی

■ تابع ضرب:

نشان می‌دهیم تابع ضرب بازگشتی نخستینی است.

می‌نویسیم:

mul(x۱, S(x۲)) =
		mul(x۱, ۰) = g(x۱) = Z(x۱)
		= H(x۱, x۲ , Sum (x۱, x۲)) = = sum(π<۱>, π<۳>)(x۱, x۲, mul(x۱, x۲))

■ تابع فاکتوریل

تابع فاکتوریل، !، بازگشتی-نخستینی است:

fctrl(S(x۱)) =
		fctrl(۰) = ۱
		fctrl(۱) = ۱
		mul(S(x۱), fctrl(x۱))

■ قاعده‌های جمع و ضرب کراندار (Bounded sum, bounded product rules)

دو قاعده جمع کراندار و ضرب کراندار که در پی می‌آیند موجب آسانی گسترش توابع و مجموعه‌های P.r می‌گردند. می‌توان به آسانی نشان داد که این دو قاعده از A۱، A۲ و A۳ و توسط  قواعد R۱ یا R۲، با توجه به توابعی که تاکنون گسرانده شده‌اند، به آسانی قابل استنتاج هستند.

قاعده جمع کراندار

فرض کنید تابع f(x, y) یک تابع P.r باشد. در این صورت، تابع BndS که در زیر تعریف شده است و جمع کراندار نام دارد، یک تابع P.r است.

BndS(x, y) = 𝚺_{<i=۰, y>}f(x, i) = f(x, ۰) + ... + f(x, y)

BndS(x, S(y))	=
			BndS(x, ۰) = f(x, ۰)
			BndS(x, y + ۱) = BndS(x, y) + f(x, y + ۱)

---

قاعده ضرب کراندار

همچنین، فرض کنید تابع f(x, y) یک تابع P.r باشد. در این صورت، تابع BndP که در زیر تعریف شده است و ضرب کراندار نام دارد، یک تابع P.r است.

BndP(x, y) = Π_{<i=۰, y>}f(x, i) = f(x, ۰) × ... × f(x, y)

یک تابع P.r است.

BndP(x, S(y))	=
			BndP(x, ۰) = f(x, ۰)
			BndP(x, y + ۱) = BndP(x, y) + f(x, y + ۱)

■ باقیمانده و خارج قسمت

تابع باقیمانده (Remainder) تقسیم x بر y یک تابع P.r است:

rmd(x, S(y))	=
			rmd(x, ۰) = ۰
			rmd(x, S(y)) = S(rmd(x, y)) × sgn(x ∸ (rmd(x, y)+ ۱))

تابع خارج قسمت (Quotient) تقسیم x بر y وقتی x|y یک تابع P.r است:

quo(x, S(y))	=
			quo(x, ۰) = ۰
			quo(x, S(y)) = quo(x, y) + sgn(rmd(x, y))

■ شمارش مقسوم علیه

تابع شمارش y توسط x، (div(x,y، یک تابع P.r است:

div(x, y)	=
			۱	اگر x|y
			۰	وگرنه

div(x, y) = sgn(x, y)

■ تابع چرخه

تابع چرخه [Function iteration] تعریف شده در زیر به شرط P.r بودن تابع BLoop یک تابع P.r است:

	BLoop⚬(y) = y
	BLoopS(x)(y) = BLoop(Boopx (y))

■ تابع ثابت

تابع ثابت، Cte(x_۱)=c، یک تابع P.r است. تابع Cte با کارزدن (ترکیب) c بار تابع تالی روی تابع صفر تعریف می‌شود. یعنی:

Cte(x_۱) = S^⚬Cte(Z(x_۱)

به عبارت دیگر:

Cte(x_۱) = S(S(S . . . S(Z(x_۱))))

■ تعریف و استدلال مبتنی بر مورد (Case-based definition and reasoning)

فرض کنید g_۱,...,g_m و R_۱,...,R_m به ترتیب توابع n متغیری و رابطه‌های n گانه P.r باشند، آنگونه که برای a∈ℕⁿ یک و فقط یکی از رابطه‌های R_۱(a),...,R_m(a) برقرار باشد. در این صورت تابع f، تعریف شده در زیر، P.r است.

f(a)	=
			g۱(a) .. .. gm(a)	... ... ... ...	اگر R۱(a) آنگاه: .. .. اگر Rm(a) آنگاه:		مورد ۱: .. .. مورد m:

تابع f تعریف شده در بالا را می‌توان به صورت زیر نوشت که آشکارا P.r است.

f(a) = [g_۱(a) × sgn(χ_۱(a))] + . . . + [g_m(a) × sgn(χ_m(a))].

■ در بالا χ_i تابع مشخصه رابطه R_i است و sgn متمم تابع علامت است.

■ تعداد مقسوم علیه‌ها (Counting divisors)

■ اول بودن

تابع اول بودن x یک تابع P.r است.

prm(x)	=
			۱		اگر x اول است آنگاه:
			۰		وگرنه:

  prm(x) = sgn(dvsr(|x, - ۲|).

■ کمینه سازی ‌کراندار - Bounded Minimalization

برای مثال: در تابع تفریق کوتاه‌شده (x∸y): برای هر y کوچکتر یا مساوی x داریم x∸y=۰. به عبارت دیگر کمینه تابع دو متغیری تفریق کوتاه‌شده تابع یک متغیری f(x)=x است.

در زبان یونانی «μικρό» (میکرو) به معنی کوچک است. در نظریه رایانش μ نماد عملگر کمینه‌ساز (Minimalization operator) است.

گیریم g(x) یک تابع باشد، آنگاه تابع f(x) را کمینه کراندار تابع g(x) گوییم اگر:

در تعریف بالا عبارت سمت راست این گونه خوانده می‌شود: کوچکترین i که کوچک‌تر یا مساوی k باشد و داشته باشیم g(x, i)=۰. به عبارت دیگر در تعریف بالا داریم:

[∀j < i (g(x, i) ≠ ۰].

■ جستجوی کراندار

کمینه‌سازی آن گونه که در بالا گفته شد را گاهی جستجوی کراندار (Bounded Search) می‌نامند و به شیوه زیر تعریف می‌کنند:

μz ≤ y[f(x, z)=۰]	=
			μz ≤ y		اگر f(x, z)=۰ آنگاه:
			y + ۱		وگرنه:

 از این جهت به μ عملگر جستجو (Search operator) نیز می‌گویند.

■ nامین عدد اول

تابع یافتن nامین عدد اول یک تابع P.r است.

nprm(n)	=
			nprm(۰) =۰
			nprm(n+۱) =	µk<(۲+fctrl(nprm(n))) (۱∸ (k∸ nprm(n) × prm(k) = ۰)

■ محاسبه توان nامین فاکتور اول در تجزیه اعداد

تابع ep(x, n): محاسبه توان nامین فاکتور اول در تجزیه x به عوامل اول یک تابع P.r است.

از حساب می‌دانیم هر عدد طبیعی بزرگتر از ۱ را می‌توان بطور یکتا به عوامل اول تجزیه کرد. برای مثال:

[۱= ۲^۰,۱= ۳^۰ , ...]
۴=۲^۲,
۷ = ۷^۱,
۶۶۰۰ = ۲^۳۳^۱۵^۲۱۱^۱

اکنون تابع ep(x, n) را به صورت زیر تعریف می‌کنیم:

ep(x, n)	=
			k		اگر x, n>۰ است آنگاه k توان nامین عدد اول در تجزیه x به عوامل اول است
			۰		اگر x=۰ ⋁ n=۰ آنگاه

و در زیر نشان می‌دهیم که ep(x, n) یک تابع P.r است.

ep(x, n) = µ_(m<x)(div(pow(n, m+۱), x) = ۰).

■ دنباله‌های کد گذاری (Coding sequences)

فرض کنید p_۱,...,p_n به ترتیب دنباله n عدد اول آغازین باشند، نیز فرض کنید s=(a_۱,...,a_n) دنباله متناهی اعداد طبیعی باشد. دنباله s را می‌توان با (توجه به بند بالا) به گونه زیر به  صورت کد درآورد (کدگذاری کرد):

c = pow(p_۱, a_۱+۱) × pow(p_۲, a_۲+۱) × . . . × pow(p_n, a_n+۱)

برای مثال دنباله s۱=(۳, ۱, ۲, ۱) را در نظر بگیرید. می‌توان نوشت:

(۳, ۱, ۲, ۱) ↔ ۶۶۰۰ = ۲^۳۳^۱۵^۲۱۱^۱

(۳, ۱, ۲, ۱) ↔ ۶۶۰۰ = ۲^۳۳^۱۵^۲۱۱^۱۱۷^۰۱۱^۰

اکنون فرض کنید عدد ۶۶۰۰ داده شده است و می‌خواهیم طول دنباله s۱ را محاسبه کنیم. برای این کار کافی است کوچکترین توان عامل اول که از آن کوچکتر نباشد را به گونه‌ای که در زیر آمده بیابیم:

طول c =µ_z<c (ep(c, z+۱) = ۰)

☚: برای مثال بیشتر «شمارایی مجموعه فرمول‌ها» را ببینید.

عنصر iام دنباله‌ی تجزیه عدد c به عوامل را می‌توان به شیوه زیر یافت:

NthF(c) = ep(c, i) ∸ ۱

■ رایانش‌پذیری و توابع بازگشتی-نخستینی

در یادداشت‌های پیشین «روند منطق مدرن، الگوریتم، محاسبه و تصمیم» درباره الگوریتم، رایانش‌پذیری، تصمیم پذیری و مدل رایانشی شرح و تفصیل آمده است. می‌توان نشان داد توابع آغازین (A۱، A۲ و A۳) رایانش پذیر هستند. نیز دو قاعده R۱ و R۲ سرایت دهنده رایانش‌پذیری هستند. پس هر تابع P.r رایانش‌پذیر است. [این را به آسانی نیز می‌توان با استقرای روی تعداد گام‌ها به کار رفته در استخراج توابع P.r نشان ‌داد.] اما برعکس آن چطور؟ یعنی:

آیا هر تابع رایانش پذیر P.r است؟ پاسخ به طور قطعی نه است.

 یعنی، حداقل یک تابع رایانش پذیر وجود دارد که بازگشتی-نخستینی نیست.

برای نشان دادن اینکه تابعی وجود دارد که رایانش‌پذیر است ولی P.r نیست از روش برهان قطری کانتور استفاده می‌کنیم. پیش از این به خود این روش را مرور می‌کنیم.

■ یادآوری روش قطری کانتور (Diagonalization method)

در یادآور نظریه مجموعه‌ها برای اثبات ناشمارایی مجموعه اعداد حقیقی از روش موسوم به برهان قطری کانتور↝ سود جستیم. در آنجا نشان داده ‌شد در هر برشمارش مجموعه اعداد حقیقی عضوی از اعداد حقیقی هست که در این برشمارش نیست، پس مجموعه اعداد حقیقی شمارش پذیر نیست.

مورد بالا فقط یکی از موردهای روش قطری است.  ایده زیربنایی این روش در حالت‌های گوناگون قابل پیاده سازی است و از جمله در اثبات بسیاری از نتایج در نظریه رایانش، به ویژه در رایانش ناپذیری توابع، مجموعه‌ها و رابطه‌ها، دارای نقش مرکزی است.

برای توضیح و روش کارزدن این روش فرض کنید کلاس توابع F (از ℕ در ℕ) برشمردنی و دارای ویژگی P هستند. بنابراین می‌توان نوشت:

<F>: f_۰, f_۱, f_۲, . . .

برشمارش <F> را می‌توان در یک ماتریس (با تعداد سطر و ستون نامتناهی) همراه با برشمارش مقادیر متغیر x مطابق زیر نشان داد:

دنباله عناصر قطری ماتریس بالا را در زیر برمی‌شمریم:

f_۰(۰), f_۱(۱),  . . . ,f_n(n), . . .

اکنون تابع g (از ℕ در ℕ) را گونه‌ای تعریف می‌کنیم تا بطور یکنوا و صریح عناصر قطری در بالا را به دنباله زیر برگرداند:

g(۰), g(۱), g(۲), . . .

 به قسمی که برای هر n مقدار f_n(n) از g(n) متفاوت باشد. در انتخاب تابع g(n) آزاد هستیم و فقط کافی است متفاوت از f_n(n) باشد. در صورت وجود چنین تابعی آنگاه ثابت می‌شود که تابعی، یعنی g، هست که در کلاس F نیست، یعنی ویژگی P را ندارد.

■ چنین نیست همه توابع رایانش‌پذیر، توابع بازگشتی-نخستینی باشند↝.

اثبات:

از آنجا که کلاس توابع P.r شمارا است پس میتوان آنها را برشمرد. یعنی:

Φ_۰, Φ_۱, . . ., Φ_n-۱, Φ_n, Φ_n+۱, . . .

در ماتریس پایین (با تعداد سطر و ستون نامتناهی) برشمارش بالا همراه با برشمارش مقادیر متغیر x نشان داده شده است:

تابع U را برای n معین به قرار زیر تعریف می‌کنیم:

U(n, x) = Φ_n(x) .

اکنون تابع F را برحسب تابع تعریف شده U به قرار زیر تعریف می‌کنیم:

F(x) = U(x, x) + ۱.

(آشکار است که F باید P.r باشد.)

نشان می‌دهیم تابع F یک تابع P.r نیست.

برای اثبات فرض می‌کنیم F یک تابع P.r باشد. بنابراین و با توجه به تعریفِ Φ_n(x)، باید عدد n باشد که تحت F دارای تصویر Φ_n(x) در کلاس توابع P.r باشد. بنابراین می‌توان نوشت:

(∀x)[F(x) = Φ_n(x) = U(n , x)].

رابطه بالا به ویژه برای x = n نیز برقرار است. پس:

F(n) = U(n, n).

اما بنابر تعریف داریم:

F(n) = U(n, n) + ۱.

که این یک تناقض است و بنابراین F یک تابع P.r نیست.

به عبارت دیگر، اگر F یک تابع P.r باشد F باید همان U باشد. در این صورت:

F(n) = U(n, n)

⇓

U(n, n) = U(n, n) +۱

⇓

 ۰ = ۱

در اینجا مرور ما در بحث توابع بازگشتی-نخستینی تمام می‌شود. در یادداشت بعد در پی یافتن موردی از تابع F در بالا خواهیم شد و اینکه چگونه با گسترش نخستینی‌ها به بازگشتی‌ها برسیم.