دالة تكرارية عامة

في المنطق الرياضي وعلوم الحاسوب ، تُعرف الدالة التكرارية العامة ، أو الدالة التكرارية الجزئية ، أو الدالة التكرارية-μ ، بأنها دالة جزئية من الأعداد الطبيعية إلى الأعداد الطبيعية، وهي قابلة للحساب بالمعنى البديهي، وكذلك بالمعنى الرسمي . إذا كانت الدالة كلية ، تُسمى أيضًا دالة تكرارية كلية (أو اختصارًا دالة تكرارية ). ^{[ 1 ]} في نظرية الحوسبة ، يُبين أن الدوال التكرارية-μ هي تحديدًا الدوال التي يمكن حسابها بواسطة آلات تورينج ^{[ 2 ] [ 4 ]} (وهذه إحدى النظريات التي تدعم فرضية تشيرش-تورينج ). ترتبط الدوال التكرارية-μ ارتباطًا وثيقًا بالدوال التكرارية الأولية ، ويستند تعريفها الاستقرائي (المذكور أدناه) إلى تعريف الدوال التكرارية الأولية. مع ذلك، ليست كل دالة تكرارية كلية دالة تكرارية أولية ، وأشهر مثال على ذلك دالة أكرمان .

ومن الفئات المكافئة الأخرى للدوال دوال حساب التفاضل والتكامل لامدا والدوال التي يمكن حسابها بواسطة خوارزميات ماركوف .

تُعرف المجموعة الفرعية من جميع الدوال التكرارية الكلية ذات القيم في {0،1} في نظرية التعقيد الحسابي باسم فئة التعقيد R.

الدوال التكرارية من النوع μ (أو الدوال التكرارية العامة ) هي دوال جزئية تأخذ مجموعات منتهية من الأعداد الطبيعية وتعيد عددًا طبيعيًا واحدًا. وهي أصغر فئة من الدوال الجزئية التي تشمل الدوال الأولية، وهي مغلقة تحت التركيب والتكرار الأولي ومعامل التصغير μ .

أصغر فئة من الدوال، بما فيها الدوال الأولية والمغلقة تحت التركيب والتكرار البدائي (أي بدون تصغير)، هي فئة الدوال التكرارية البدائية . بينما جميع الدوال التكرارية البدائية كلية، فإن هذا لا ينطبق على الدوال التكرارية الجزئية؛ فعلى سبيل المثال، تصغير دالة التابع غير مُعرَّف. تُعد الدوال التكرارية البدائية مجموعة جزئية من الدوال التكرارية الكلية، والتي بدورها مجموعة جزئية من الدوال التكرارية الجزئية. فعلى سبيل المثال، يمكن إثبات أن دالة أكرمان تكرارية كلية، وأنها غير بدائية.

الوظائف الأولية أو "الأساسية":

1. الدوال الثابتة C ^k _n : لكل عدد طبيعي n ولكل k

   ${\displaystyle C_{n}^{k}(x_{1},\ldots ,x_{k})\ {\stackrel {\mathrm {def} }{=}}\ n}$

   تستخدم التعريفات البديلة بدلاً من ذلك دالة الصفر كدالة أولية تُرجع دائمًا الصفر، وتبني الدوال الثابتة من دالة الصفر، ودالة الخلف، وعامل التركيب .

2. الوظيفة اللاحقة S:

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

3. دوال الإسقاط${\displaystyle P_{i}^{k}}$(وتسمى أيضًا دالة التطابق ): لجميع الأعداد الطبيعية${\displaystyle i,k}$بحيث${\displaystyle 1\leq i\leq k}$:

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

العوامل ( مجال الدالة المعرفة بواسطة عامل هو مجموعة قيم الوسائط بحيث يوفر كل تطبيق للدالة يجب إجراؤه أثناء الحساب نتيجة محددة جيدًا):

1. عامل التركيب${\displaystyle \circ \,}$(يُسمى أيضًا عامل الاستبدال ): بالنظر إلى دالة من الرتبة m${\displaystyle h(x_{1},\ldots ,x_{m})\,}$و m k -ary functions${\displaystyle g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k})}$:

   ${\displaystyle 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})).}$

   هذا يعني أن${\displaystyle f(x_{1},\ldots ,x_{k})}$يتم تعريفها فقط إذا${\displaystyle g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}),}$و${\displaystyle h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}))}$جميعها محددة.

2. عامل الاستدعاء الذاتي البدائي ρ : بالنظر إلى الدالة k -ary${\displaystyle g(x_{1},\ldots ,x_{k})\,}$ودالة k + 2${\displaystyle h(y,z,x_{1},\ldots ,x_{k})\,}$:

   ${\displaystyle {\begin{aligned}\rho (g,h)&\ {\stackrel {\mathrm {def} }{=}}\ f\quad {\text{where the }}k+1{\text{-ary function }}f{\text{ is defined by}}\\f(0,x_{1},\ldots ,x_{k})&=g(x_{1},\ldots ,x_{k})\\f(S(y),x_{1},\ldots ,x_{k})&=h(y,f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})\,.\end{aligned}}}$

   هذا يعني أن${\displaystyle f(y,x_{1},\ldots ,x_{k})}$يتم تعريفها فقط إذا${\displaystyle g(x_{1},\ldots ,x_{k})}$و${\displaystyle h(z,f(z,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})}$يتم تعريفها للجميع${\displaystyle z<y.}$

3. عامل التصغير μ : بالنظر إلى دالة من الرتبة ( k +1)${\displaystyle f(y,x_{1},\ldots ,x_{k})\,}$، الدالة k -ary${\displaystyle \mu (f)}$يُعرَّف بما يلي:

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

بشكل بديهي، تسعى عملية التصغير - بدءًا من الصفر والتقدم تصاعديًا - إلى إيجاد أصغر وسيط يجعل الدالة تُرجع صفرًا؛ إذا لم يكن هناك وسيط كهذا، أو إذا صادفنا وسيطًا لا تُعرَّف الدالة f عنده، فلن ينتهي البحث أبدًا، و${\displaystyle \mu (f)}$غير مُعرَّف للوسيط${\displaystyle (x_{1},\ldots ,x_{k}).}$

بينما تستخدم بعض الكتب الدراسية عامل μ كما هو مُعرَّف هنا، ^{[ 5 ] [ 6 ]} يشترط البعض الآخر ^{[ 7 ] [ 8 ]} تطبيق عامل μ على الدوال الكلية f فقط. ورغم أن هذا يُقيِّد عامل μ مقارنةً بالتعريف الوارد هنا، فإن فئة الدوال μ-التكرارية تبقى كما هي، وهو ما يستنتج من نظرية الشكل الطبيعي لكلين (انظر أدناه ) . ^{[ 5 ] [ 6 ]} والفرق الوحيد هو أنه يصبح من غير الممكن تحديد ما إذا كان تعريف دالة مُحدَّد يُعرِّف دالة μ-تكرارية، كما أنه من غير الممكن تحديد ما إذا كانت الدالة القابلة للحساب (أي μ-التكرارية) كلية. ^{[ 7 ]}

علاقة المساواة القوية${\displaystyle \simeq }$يمكن استخدام هذا لمقارنة الدوال الجزئية المتكررة من النوع μ. ويُعرَّف هذا لجميع الدوال الجزئية f و g بحيث

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

يتحقق هذا الشرط إذا وفقط إذا كان لأي اختيار للوسائط إما أن تكون كلتا الدالتين معرفتين وقيمهما متساوية أو أن تكون كلتا الدالتين غير معرفتين.

يمكن العثور على أمثلة لا تتضمن عامل التصغير في Primitive recursive function#Examples .

تهدف الأمثلة التالية فقط إلى توضيح استخدام عامل التصغير؛ ويمكن تعريفها أيضًا بدونه، وإن كان ذلك بطريقة أكثر تعقيدًا، لأنها جميعًا بدائية تكرارية.

تحدد الأمثلة التالية الدوال التكرارية العامة التي ليست تكرارية بدائية؛ وبالتالي لا يمكنها تجنب استخدام عامل التصغير.

تُسمى الدالة التكرارية العامة دالة تكرارية كلية إذا كانت مُعرَّفة لكل مُدخل، أو بعبارة أخرى، إذا أمكن حسابها بواسطة آلة تورينج كلية . لا توجد طريقة حسابية لتحديد ما إذا كانت دالة تكرارية عامة معينة كلية أم لا - انظر مسألة التوقف .

في تكافؤ نماذج الحوسبة ، يُجرى تشبيه بين آلات تورينج التي لا تتوقف عند مدخلات معينة، ونتيجة غير مُعرَّفة لتلك المدخلات في الدالة التكرارية الجزئية المقابلة. لا يمكن تعريف عامل البحث غير المحدود بقواعد التكرار البدائي، لأنها لا توفر آلية للحلقات اللانهائية (القيم غير المُعرَّفة).

تنص نظرية الشكل الطبيعي التي وضعها كلين على أنه لكل قيمة k توجد دوال استرجاعية أولية${\displaystyle U(y)\!}$و${\displaystyle T(y,e,x_{1},\ldots ,x_{k})\!}$بحيث يكون لأي دالة تكرارية من النوع μ${\displaystyle f(x_{1},\ldots ,x_{k})\!}$مع وجود k متغيرات حرة، يوجد عدد e بحيث

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

يُطلق على العدد e اسم دليل أو عدد غودل للدالة f . ^{[ 10 ] : 52-53.} ومن نتائج هذه النتيجة أنه يمكن تعريف أي دالة μ-تكرارية باستخدام حالة واحدة من عامل μ المطبق على دالة تكرارية أولية (كليًا).

يلاحظ مينسكي${\displaystyle U}$إن التعريف المذكور أعلاه هو في جوهره المكافئ التكراري μ لآلة تورينج العالمية :

إن بناء U هو كتابة تعريف دالة عامة متكررة U ( n , x ) التي تفسر العدد n بشكل صحيح وتحسب الدالة المناسبة لـ x . إن بناء U مباشرة سيتطلب نفس القدر من الجهد تقريبًا، ونفس الأفكار تقريبًا ، التي استثمرناها في بناء آلة تورينج العالمية ^{[ 11 ].}

تُستخدم في الأدبيات عدة رموز مختلفة. ومن مزايا استخدام هذه الرموز سهولة كتابة اشتقاق الدالة عن طريق "تداخل" المعاملات، بحيث يكون أحدها داخل الآخر، بشكل مختصر. فيما يلي سلسلة المعاملات${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$يُختصر إلى${\displaystyle x}$:

• وظيفة ثابتة : تستخدم كلين "${\displaystyle C_{q}^{n}(x)=q}$"وBoolos-Burgess-Jeffrey (2002) (BBJ) يستخدمان الاختصار"${\displaystyle \mathrm {const} ^{n}(x)=n}$":

مثال${\displaystyle C_{13}^{7}(r,s,t,u,v,w,x)=13}$

مثال${\displaystyle \mathrm {const} ^{13}(r,s,t,u,v,w,x)=13}$

• الوظيفة اللاحقة : يستخدم كلين${\displaystyle x'}$و${\displaystyle S}$بالنسبة لكلمة "الخليفة". وبما أن كلمة "الخليفة" تعتبر كلمة بدائية، فإن معظم النصوص تستخدم الفاصلة العليا على النحو التالي:

${\displaystyle S(a)=a+1;{\overset {\mathrm {def} }{=}};a'}$، أين

${\displaystyle 1{\overset {\mathrm {def} }{=}}0'}$،

${\displaystyle 2{\overset {\mathrm {def} }{=}}0''}$، إلخ.

• دالة الهوية : يستخدمها كلين (1952)${\displaystyle U_{i}^{n}}$للإشارة إلى دالة التطابق على المتغيرات${\displaystyle x_{i}}$تستخدم BBJ دالة التطابق${\displaystyle \mathrm {id} _{i}^{n}}$على المتغيرات${\displaystyle x_{1}}$ل${\displaystyle x_{n}}$:

${\displaystyle U_{i}^{n}(x)=\mathrm {id} _{i}^{n}(x)=x_{i}}$

مثال${\displaystyle U_{3}^{7}(r,s,t,u,v,w,x)=\mathrm {id} _{3}^{7}(r,s,t,u,v,w,x)=t}$

• عامل التركيب (الاستبدال) : يستخدم كلين خطًا غامقًا${\displaystyle \mathbf {S} _{m}^{n}}$(لا ينبغي الخلط بينه وبين${\displaystyle S}$(لـ "الخليفة"!). الرقم العلوي${\displaystyle m}$يشير إلى${\displaystyle m^{th}}$وظيفة${\displaystyle f_{m}}$، بينما الرمز السفلي${\displaystyle n}$يشير إلى${\displaystyle n^{th}}$عامل${\displaystyle x_{n}}$:

إذا أُعطينا

${\displaystyle h(x)=g(f_{1}(x),\ldots ,f_{m}(x))}$

ثم

${\displaystyle h(x)=\mathbf {S} _{m}^{n}(g,f_{1},\ldots ,f_{m})}$

وبطريقة مماثلة، ولكن بدون الرموز السفلية والعلوية، يكتب BBJ:

${\displaystyle h(x')=Cg,f_{1},\ldots ,f_{m}}$

• الاستدعاء الذاتي البدائي : يستخدم كلين الرمز${\displaystyle R^{n}({\text{base step}},{\text{induction step}})}$حيث يشير n إلى عدد المتغيرات؛ استخدام BBJ${\displaystyle \Pr({\text{base step}},{\text{induction step}})(x)}$. منح:

• الخطوة الأساسية:${\displaystyle h(0,x)=f(x)}$
• خطوة الحث:${\displaystyle h(y+1,x)=g(y,h(y,x),x)}$

مثال: تعريف الاستدعاء الذاتي البدائي لـ${\displaystyle a+b}$

• الخطوة الأساسية:${\displaystyle f(0,a)=a=U_{1}^{1}(a)}$U ¹ ₁ (أ)
• خطوة الحث:${\displaystyle f(b',a)=(f(b,a))'=g(b,f(b,a),a)=g(b,c,a)=c'=S(U_{2}^{3}(b,c,a))}$

${\displaystyle R^{2}\left(U_{1}^{1}(a),;S(U_{2}^{3}(b,c,a))\right)}$

${\displaystyle \Pr \left(U_{1}^{1}(a),;S(U_{2}^{3}(b,c,a))\right)}$

مثال : يقدم كلين مثالاً على كيفية إجراء الاشتقاق التكراري لـ${\displaystyle f(b,a)=b+a}$(لاحظ انعكاس المتغيرات)${\displaystyle a}$و${\displaystyle b}$). يبدأ بـ${\displaystyle 3}$الدوال الأولية

1. ${\displaystyle S(a)=a'}$
2. ${\displaystyle U_{1}^{1}(a)=a}$
3. ${\displaystyle U_{2}^{3}(b,c,a)=c}$
4. ${\displaystyle g(b,c,a)=S(U_{2}^{3}(b,c,a))=c'}$
5. الخطوة الأساسية:${\displaystyle h(0,a)=U_{1}^{1}(a)}$

خطوة الحث:${\displaystyle h(b',a)=g(b,h(b,a),a)}$

يصل إلى:

${\displaystyle a+b=R^{2}\left(U_{1}^{1},;S_{1}^{3}(S,U_{2}^{3})\right)}$

• عدد فيبوناتشي
• وظيفة مكارثي 91

• نظرية التكرار
• التكرار
• الاستدعاء الذاتي (علوم الحاسوب)

• مدخل موسوعة ستانفورد للفلسفة
• مُترجم لتحويل دالة تكرارية إلى آلة تورينج مكافئة