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

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

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

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

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

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

Primitive or "basic" functions:

1. Constant functions C^k_n: For each natural number n and every k

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

   Alternative definitions use instead a zero function as a primitive function that always returns zero, and build the constant functions from the zero function, the successor function and the composition operator.

2. Successor function S:

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

3. Projection function${\displaystyle P_{i}^{k}}$ (also called the Identity function): For all natural numbers ${\displaystyle i,k}$ such that ${\displaystyle 1\leq i\leq k}$:

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

Operators (the domain of a function defined by an operator is the set of the values of the arguments such that every function application that must be done during the computation provides a well-defined result):

1. Composition operator${\displaystyle \circ \,}$ (also called the substitution operator): Given an m-ary function ${\displaystyle h(x_{1},\ldots ,x_{m})\,}$ and mk-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})).}$

   This means that ${\displaystyle f(x_{1},\ldots ,x_{k})}$ is defined only if ${\displaystyle g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}),}$ and ${\displaystyle h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}))}$ are all defined.

2. Primitive recursion operatorρ: Given the k-ary function ${\displaystyle g(x_{1},\ldots ,x_{k})\,}$ and k+2 -ary function ${\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}}}$

   This means that ${\displaystyle f(y,x_{1},\ldots ,x_{k})}$ is defined only if ${\displaystyle g(x_{1},\ldots ,x_{k})}$ and ${\displaystyle h(z,f(z,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})}$ are defined for all ${\displaystyle z<y.}$

3. Minimization operatorμ: Given a (k+1)-ary function ${\displaystyle f(y,x_{1},\ldots ,x_{k})\,}$, the k-ary function ${\displaystyle \mu (f)}$ is defined by:

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

Intuitively, minimisation seeks—beginning the search from 0 and proceeding upwards—the smallest argument that causes the function to return zero; if there is no such argument, or if one encounters an argument for which f is not defined, then the search never terminates, and ${\displaystyle \mu (f)}$ is not defined for the argument ${\displaystyle (x_{1},\ldots ,x_{k}).}$

While some textbooks use the μ-operator as defined here,^[5][6] others^[7][8] demand that the μ-operator is applied to total functions f only. Although this restricts the μ-operator as compared to the definition given here, the class of μ-recursive functions remains the same, which follows from Kleene's normal form theorem (see below).^[5][6] The only difference is, that it becomes undecidable whether a specific function definition defines a μ-recursive function, as it is undecidable whether a computable (i.e. μ-recursive) function is total.^[7]

The strong equality relation ${\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

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

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