دالة تكرارية بدائية

دالة (متجهة القيمة) ^{[ 5 ]}${\displaystyle f:\mathbb {N} ^{m}\to \mathbb {N} ^{n}}$تكون الدالة بدائية تكرارية إذا أمكن كتابتها على النحو التالي

${\displaystyle f(x_{1},\dots ,x_{m})=(f_{1}(x_{1},\dots ,x_{m}),\dots ,f_{n}(x_{1},\dots ,x_{m}))}$

حيث كل مكون${\displaystyle f_{i}:\mathbb {N} ^{m}\to \mathbb {N} }$هي دالة تكرارية أولية (ذات قيمة عددية). ^{[ 6 ]}

تعريف الدالة الثنائية${\displaystyle \operatorname {Add} }$يمكن الحصول على ، لحساب مجموع وسيطاتها، باستخدام عامل الاستدعاء الذاتي البدائي${\displaystyle \rho }$ولتحقيق هذه الغاية، المعادلات المعروفة

${\displaystyle {\begin{aligned}0+y&=y,\\S(x)+y&=S(x+y)\end{aligned}}}$

"أعيدت صياغتها بمصطلحات الدوال التكرارية الأولية": في تعريف${\displaystyle \rho (g,h)}$تشير المعادلة الأولى إلى اختيار${\displaystyle g=P_{1}^{1}}$للحصول على${\displaystyle \operatorname {Add} (0,y)=g(y)=y}$تشير المعادلة الثانية إلى اختيار${\displaystyle h=S\circ P_{2}^{3}}$للحصول على${\displaystyle \operatorname {Add} (S(x),y)=h(x,\operatorname {Add} (x,y),y)=(S\circ P_{2}^{3})(x,\operatorname {Add} (x,y),y)=S(\operatorname {Add} (x,y))}$لذلك، يمكن تعريف دالة الجمع على النحو التالي:${\displaystyle \operatorname {Add} =\rho (P_{1}^{1},S\circ P_{2}^{3})}$كمثال على الحساب،

${\displaystyle {\begin{aligned}\operatorname {Add} (1,7)&=\rho (P_{1}^{1},S\circ P_{2}^{3})(S(0),7)&&{\text{ by Def. }}\operatorname {Add} ,S\\&=(S\circ P_{2}^{3})(0,\operatorname {Add} (0,7),7)&&{\text{ by case }}\rho (g,h)(S(...),...)\\&=S(\operatorname {Add} (0,7))&&{\text{ by Def. }}\circ ,P_{2}^{3}\\&=S(\rho (P_{1}^{1},S\circ P_{2}^{3})(0,7))&&{\text{ by Def. }}\operatorname {Add} \\&=S(P_{1}^{1}(7))&&{\text{ by case }}\rho (g,h)(0,...)\\&=S(7)&&{\text{ by Def. }}P_{1}^{1}\\&=8&&{\text{ by Def. }}S.\\\end{aligned}}}$

منح${\displaystyle \operatorname {Add} }$، الدالة أحادية الأصل${\displaystyle \operatorname {Add} \circ (P_{1}^{1},P_{1}^{1})}$يضاعف حجته،${\displaystyle (\operatorname {Add} \circ (P_{1}^{1},P_{1}^{1}))(x)=\operatorname {Add} (x,x)=x+x.}$

وبطريقة مشابهة للجمع، يمكن تعريف الضرب بواسطة${\displaystyle \operatorname {Mul} =\rho (C_{0}^{1},\operatorname {Add} \circ (P_{2}^{3},P_{3}^{3}))}$وهذا يعيد إنتاج معادلات الضرب المعروفة:

${\displaystyle {\begin{aligned}\operatorname {Mul} (0,y)&=\rho (C_{0}^{1},\operatorname {Add} \circ (P_{2}^{3},P_{3}^{3}))(0,y)&&{\text{ by Def. }}\operatorname {Mul} \\&=C_{0}^{1}(y)&&{\text{ by case }}\rho (g,h)(0,...)\\&=0&&{\text{ by Def. }}C_{0}^{1}.\end{aligned}}}$

و

${\displaystyle {\begin{aligned}\operatorname {Mul} (S(x),y)&=\rho (C_{0}^{1},\operatorname {Add} \circ (P_{2}^{3},P_{3}^{3}))(S(x),y)&&{\text{ by Def. }}\operatorname {Mul} \\&=(\operatorname {Add} \circ (P_{2}^{3},P_{3}^{3}))(x,\operatorname {Mul} (x,y),y)&&{\text{ by case }}\rho (g,h)(S(...),...)\\&=\operatorname {Add} (\operatorname {Mul} (x,y),y)&&{\text{ by Def. }}\circ ,P_{2}^{3},P_{3}^{3}\\&=\operatorname {Mul} (x,y)+y&&{\text{ by property of }}\operatorname {Add} .\end{aligned}}}$

تُعتبر الدالة السابقة بمثابة "عكس" الدالة اللاحقة، ويتم تعريفها بشكل متكرر بواسطة القواعد.${\displaystyle \operatorname {Pred} (0)=0}$و${\displaystyle \operatorname {Pred} (S(n))=n}$التعريف التكراري الأولي هو${\displaystyle \operatorname {Pred} =\rho (C_{0}^{0},P_{1}^{2})}$كمثال على الحساب،

${\displaystyle {\begin{aligned}\operatorname {Pred} (8)&=\rho (C_{0}^{0},P_{1}^{2})(S(7))&&{\text{ by Def. }}\operatorname {Pred} ,S\\&=P_{1}^{2}(7,\operatorname {Pred} (7))&&{\text{ by case }}\rho (g,h)(S(...),...)\\&=7&&{\text{ by Def. }}P_{1}^{2}.\end{aligned}}}$

دالة الطرح المحدودة (وتسمى أيضًا " monus "، ويرمز لها بـ "${\displaystyle \mathbin {\dot {-}} }$يمكن تعريف ") من الدالة السابقة. وهي تحقق المعادلات

${\displaystyle {\begin{aligned}y\mathbin {\dot {-}} 0&=y,\\y\mathbin {\dot {-}} S(x)&=\operatorname {Pred} (y\mathbin {\dot {-}} x).\end{aligned}}}$

بما أن الاستدعاء الذاتي يعمل على الوسيط الثاني، فإننا نبدأ بتعريف استدعاء ذاتي بدائي لعملية الطرح المعكوسة.${\displaystyle \operatorname {RSub} (y,x)=x\mathbin {\dot {-}} y}$ثم يتم تطبيق التكرار على الوسيط الأول، وبالتالي يمكن الحصول على تعريفه التكراري الأولي، على غرار الجمع، كما يلي:${\displaystyle \operatorname {RSub} =\rho (P_{1}^{1},\operatorname {Pred} \circ P_{2}^{3})}$للتخلص من ترتيب الوسائط المعكوس، قم بتعريف${\displaystyle \operatorname {Sub} =\operatorname {RSub} \circ (P_{2}^{2},P_{1}^{2})}$كمثال على الحساب،

${\displaystyle {\begin{aligned}\operatorname {Sub} (8,1)&=(\operatorname {RSub} \circ (P_{2}^{2},P_{1}^{2}))(8,1)&&{\text{ by Def. }}\operatorname {Sub} \\&=\operatorname {RSub} (1,8)&&{\text{ by Def. }}\circ ,P_{2}^{2},P_{1}^{2}\\&=\rho (P_{1}^{1},\operatorname {Pred} \circ P_{2}^{3})(S(0),8)&&{\text{ by Def. }}\operatorname {RSub} ,S\\&=(\operatorname {Pred} \circ P_{2}^{3})(0,\operatorname {RSub} (0,8),8)&&{\text{ by case }}\rho (g,h)(S(...),...)\\&=\operatorname {Pred} (\operatorname {RSub} (0,8))&&{\text{ by Def. }}\circ ,P_{2}^{3}\\&=\operatorname {Pred} (\rho (P_{1}^{1},\operatorname {Pred} \circ P_{2}^{3})(0,8))&&{\text{ by Def. }}\operatorname {RSub} \\&=\operatorname {Pred} (P_{1}^{1}(8))&&{\text{ by case }}\rho (g,h)(0,...)\\&=\operatorname {Pred} (8)&&{\text{ by Def. }}P_{1}^{1}\\&=7&&{\text{ by property of }}\operatorname {Pred} .\end{aligned}}}$

في بعض السياقات، من الطبيعي النظر في الدوال التكرارية الأولية التي تأخذ كمدخلات أزواجًا مرتبة تجمع بين الأرقام وقيم الصواب (أي،${\displaystyle t}$صحيح، و${\displaystyle f}$(للقيم الخاطئة)، أو التي تُنتج قيمًا صحيحة كمخرجات. ^{[ 8 ]} يمكن تحقيق ذلك من خلال تحديد القيم الصحيحة بأرقام بطريقة ثابتة. على سبيل المثال، من الشائع تحديد القيمة الصحيحة${\displaystyle t}$مع الرقم${\displaystyle 1}$وقيمة الحقيقة${\displaystyle f}$مع الرقم${\displaystyle 0}$بمجرد تحديد هذه الهوية، تصبح الدالة المميزة لمجموعة ما${\displaystyle A}$، وهو ما يعود دائمًا${\displaystyle 1}$أو${\displaystyle 0}$يمكن اعتبارها بمثابة مسند يحدد ما إذا كان الرقم موجودًا في المجموعة${\displaystyle A}$. سيتم افتراض هذا التحديد للمسندات مع الدوال العددية لبقية هذا المقال.

كمثال على المسند الاستدعائي الأولي، الدالة أحادية المعامل${\displaystyle \operatorname {IsZero} }$يُعرَّف بحيث${\displaystyle \operatorname {IsZero} (x)=1}$لو${\displaystyle x=0}$، و${\displaystyle \operatorname {IsZero} (x)=0}$وإلا. يمكن تحقيق ذلك عن طريق تحديد${\displaystyle \operatorname {IsZero} =\rho (C_{1}^{0},C_{0}^{2})}$. ثم${\displaystyle \operatorname {IsZero} (0)=\rho (C_{1}^{0},C_{0}^{2})(0)=C_{1}^{0}()=1}$و على سبيل المثال${\displaystyle \operatorname {IsZero} (8)=\rho (C_{1}^{0},C_{0}^{2})(S(7))=C_{0}^{2}(7,\operatorname {IsZero} (7))=0}$.

استخدام الخاصية${\displaystyle x\leq y\iff x\mathbin {\dot {-}} y=0}$، الدالة الثنائية${\displaystyle \operatorname {Leq} }$يمكن تعريفها بواسطة${\displaystyle \operatorname {Leq} =\operatorname {IsZero} \circ \operatorname {Sub} }$. ثم${\displaystyle \operatorname {Leq} (x,y)=1}$لو${\displaystyle x\leq y}$، و${\displaystyle \operatorname {Leq} (x,y)=0}$وإلا. كمثال حسابي،

${\displaystyle {\begin{aligned}\operatorname {Leq} (8,3)&=\operatorname {IsZero} (\operatorname {Sub} (8,3))&&{\text{ by Def. }}\operatorname {Leq} \\&=\operatorname {IsZero} (5)&&{\text{ by property of }}\operatorname {Sub} \\&=0&&{\text{ by property of }}\operatorname {IsZero} \\\end{aligned}}}$

تعريف سابق لـ${\displaystyle \operatorname {Leq} }$إذا تم الحصول على ذلك، يمكن تعريف المسند العكسي على النحو التالي:${\displaystyle \operatorname {Geq} =\operatorname {Leq} \circ (P_{2}^{2},P_{1}^{2})}$. ثم،${\displaystyle \operatorname {Geq} (x,y)=\operatorname {Leq} (y,x)}$يكون صحيحًا (أو بتعبير أدق: قيمته 1) إذا وفقط إذا${\displaystyle x\geq y}$.

يمكن تعريف عامل الشرط الثلاثي if-then-else المعروف في لغات البرمجة بواسطة${\displaystyle \operatorname {If} =\rho (P_{2}^{2},P_{3}^{4})}$ثم، لأي${\displaystyle x}$،

${\displaystyle {\begin{aligned}\operatorname {If} (S(x),y,z)&=\rho (P_{2}^{2},P_{3}^{4})(S(x),y,z)&&{\text{ by Def. }}\operatorname {If} \\&=P_{3}^{4}(x,\operatorname {If} (x,y,z),y,z)&&{\text{ by case }}\rho (S(...),...)\\&=y&&{\text{ by Def. }}P_{3}^{4}\end{aligned}}}$

و

${\displaystyle {\begin{aligned}\operatorname {If} (0,y,z)&=\rho (P_{2}^{2},P_{3}^{4})(0,y,z)&&{\text{ by Def. }}\operatorname {If} \\&=P_{2}^{2}(y,z)&&{\text{ by case }}\rho (0,...)\\&=z&&{\text{ by Def. }}P_{2}^{2}.\end{aligned}}}$

إنه،${\displaystyle \operatorname {If} (x,y,z)}$يُعيد الجزء اللاحق (${\displaystyle y}$) إذا كان الجزء الشرطي (${\displaystyle x}$) صحيح، والجزء else (${\displaystyle z}$) خلاف ذلك.

بناءً على${\displaystyle \operatorname {If} }$من السهل تعريف الوصلات المنطقية في الدالة. على سبيل المثال، تعريف${\displaystyle \operatorname {And} =\operatorname {If} \circ (P_{1}^{2},P_{2}^{2},C_{0}^{2})}$، يحصل المرء${\displaystyle \operatorname {And} (x,y)=\operatorname {If} (x,y,0)}$، إنه،${\displaystyle \operatorname {And} (x,y)}$يكون صحيحاً إذا وفقط إذا كان كلاهما${\displaystyle x}$و${\displaystyle y}$صحيح ( الاقتران المنطقي لـ${\displaystyle x}$و${\displaystyle y}$).

بصورة مماثلة،${\displaystyle \operatorname {Or} =\operatorname {If} \circ (P_{1}^{2},C_{1}^{2},P_{2}^{2})}$و${\displaystyle \operatorname {Not} =\operatorname {If} \circ (P_{1}^{1},C_{0}^{1},C_{1}^{1})}$يؤدي ذلك إلى تعريفات مناسبة للفصل والنفي :${\displaystyle \operatorname {Or} (x,y)=\operatorname {If} (x,1,y)}$و${\displaystyle \operatorname {Not} (x)=\operatorname {If} (x,0,1)}$.

باستخدام الوظائف المذكورة أعلاه${\displaystyle \operatorname {Leq} }$،${\displaystyle \operatorname {Geq} }$و${\displaystyle \operatorname {And} }$التعريف${\displaystyle \operatorname {Eq} =\operatorname {And} \circ (\operatorname {Leq} ,\operatorname {Geq} )}$يطبق شرط المساواة. في الواقع،${\displaystyle \operatorname {Eq} (x,y)=\operatorname {And} (\operatorname {Leq} (x,y),\operatorname {Geq} (x,y))}$يكون صحيحاً إذا وفقط إذا${\displaystyle x}$يساوي${\displaystyle y}$.

وبالمثل، التعريف${\displaystyle \operatorname {Lt} =\operatorname {Not} \circ \operatorname {Geq} }$يطبق المسند "أقل من"، و${\displaystyle \operatorname {Gt} =\operatorname {Not} \circ \operatorname {Leq} }$يطبق "أكبر من".

تُعتبر عمليات الأسس واختبار أولية الأعداد من الدوال التكرارية الأولية. بالنظر إلى الدوال التكرارية الأولية${\displaystyle e}$،${\displaystyle f}$،${\displaystyle g}$، و${\displaystyle h}$، دالة تُعيد قيمة${\displaystyle g}$متى${\displaystyle e\leq f}$وقيمة${\displaystyle h}$وإلا فهو بدائي تكراري.

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

الأمثلة والتعريفات التالية مأخوذة من كتاب كلين (1974) ، الصفحات 222-231 . يُرفق العديد منها ببراهين. كما تظهر معظمها بأسماء مشابهة، إما كبرهان أو كأمثلة، في كتاب بولوس، بورغيس، وجيفري (2002) ، الصفحات 63-70، حيث يُضاف اللوغاريتم lo(x, y) أو lg(x, y) حسب الاشتقاق الدقيق.  

فيما يلي، تُشير العلامة " ' "، مثل a'، إلى العلامة الأولية التي تعني "اللاحق لـ"، والتي تُعرف عادةً باسم "+1"، مثل a +1 = _{def a'. وتُعدّ الدوال من 16 إلى 20 و#G ذات أهمية خاصة فيما يتعلق بتحويل المسندات التكرارية الأولية إلى شكلها "الحسابي" المُعبَّر عنه} بأعداد غودل ، واستخراجها منه .

1. الجمع: أ + ب
2. الضرب: أ × ب
3. الأسس: أ ^ب
4. المضروب a!  : 0! = 1، a'! = a!×a'
5. pred(a): (السابق أو النقصان): إذا كانت a > 0 فإن a−1 وإلا 0
6. عملية الطرح الصحيحة a ∸ b: إذا كان a ≥ b فإن a−b يساوي صفرًا، وإلا فإن a ∸ b يساوي صفرًا.
7. الحد الأدنى (أ ₁ ، ... أ _ن )
8. القيمة القصوى (a ₁ , ... a _n )
9. الفرق المطلق: | أ - ب | = _تعريف (أ ∸ ب) + (ب ∸ أ)
10. ~sg(a): NOT[signum(a)]: إذا كانت a=0 فإن 1 وإلا 0
11. sg(a): signum(a): إذا كانت a=0 فإن 0 وإلا 1
12. أ | ب: (أ يقسم ب): إذا كان ب = ك × أ لبعض قيم ك، فإن الناتج 0، وإلا فإن الناتج 1
13. باقي قسمة (أ، ب): هو الناتج المتبقي إذا لم يقسم ب أ بالتساوي. ويُسمى أيضاً باقي قسمة (أ، ب).
14. a = b: sg | a − b | (كان اصطلاح كلين هو تمثيل الصواب بـ 0 والخطأ بـ 1؛ في الوقت الحاضر، وخاصة في أجهزة الكمبيوتر، فإن الاصطلاح الأكثر شيوعًا هو العكس، أي تمثيل الصواب بـ 1 والخطأ بـ 0، وهو ما يعادل تغيير sg إلى ~sg هنا وفي البند التالي)
15. a < b: sg( a' ∸ b )
16. احتمال (أ): أ عدد أولي. احتمال (أ) = _تعريف أ > 1 و ليس (يوجد ج) _{1 < ج < أ} [ ج | أ ]
17. p _i : العدد الأولي رقم i+1
18. (أ) _i : أس p _i في a: x الوحيد الذي يحقق p _i ^x |a & NOT(p _i ^x' |a)
19. lh(a): "طول" أو عدد الأسس غير الصفرية في a
20. lo(a, b): (لوغاريتم a للأساس b): إذا كان a و b > 1، فإن أكبر قيمة لـ x بحيث يكون b ^x | a، وإلا فإن 0

فيما يلي، يمكن استخدام الاختصار x = _def x ₁ , ... x _n ; ويمكن تطبيق الرموز السفلية إذا اقتضى المعنى ذلك.

• #أ: الدالة φ التي يمكن تعريفها بشكل صريح من الدوال Ψ والثوابت q ₁ ، ... q _n هي دالة بدائية تكرارية في Ψ.
• #B: المجموع المحدود Σ _y<z ψ( x , y) والمنتج Π _y<z ψ( x , y) متكرران بدائيان في ψ.
• #C: المسند P الذي تم الحصول عليه عن طريق استبدال الدوال χ ₁ ,..., χ _m بالمتغيرات المقابلة للمسند Q هو بدائي تكراري في χ ₁ ,..., χ _m , Q.
• #D: المسندات التالية بدائية تكرارية في Q و R:

• NOT_Q( x ) .
• Q OR R: Q( x ) VR( x ),
• Q AND R: Q( x ) & R( x ),
• Q تستلزم R: Q( x ) → R( x )
• Q مكافئ لـ R: Q( x ) ≡ R( x )

• #E: المسندات التالية بدائية تكرارية في المسند R:

• (Ey) _y<z R( x , y) حيث (Ey) _y<z تعني "يوجد على الأقل قيمة واحدة لـ y أقل من z بحيث"
• (y) _y<z R( x , y) حيث (y) _y<z تعني "لكل y أقل من z، يكون صحيحًا أن"
• μy _y<z R( x , y). المؤثر μy _y<z R( x , y) هو شكل محدود لما يسمى بمؤثر التصغير أو مؤثر mu : يُعرَّف بأنه "أصغر قيمة لـ y أقل من z بحيث تكون R( x , y) صحيحة؛ أو z إذا لم تكن هناك مثل هذه القيمة".

• #F: التعريف حسب الحالات: الدالة المعرفة على هذا النحو، حيث Q ₁ ، ...، Q _{m عبارة عن} مسندات متنافية (أو "ψ( x ) لها القيمة المعطاة بواسطة العبارة الأولى التي تنطبق")، هي دالة بدائية تكرارية في φ ₁ ، ...، Q ₁ ، ... Q _m :

φ( x ) =

• φ ₁ ( x ) إذا كانت Q ₁ ( x ) صحيحة،
• . . . . . . . . . . . . . . . . . . .
• φ _m ( x ) إذا كانت Q _m ( x ) صحيحة
• φ _m+1 ( x ) خلاف ذلك

• #G: إذا كانت φ تحقق المعادلة:

إذا كانت φ(y, x ) = χ(y, COURSE-φ(y; x ₂ , ... x _n ), x ₂ , ... x _n) ، فإن φ دالة تكرارية أولية في χ. وتُشفّر قيمة COURSE-φ(y; x _{2 to n} ) لدالة مسار القيم تسلسل القيم φ(0, x _{2 to n} ), ..., φ(y-1, x _{2 to n} ) للدالة الأصلية.

بدلاً من${\displaystyle C_{n}^{k}}$تستخدم التعريفات البديلة دالة صفرية واحدة فقط.${\displaystyle C_{0}^{0}}$كدالة أولية تُرجع دائمًا الصفر، وبناء الدوال الثابتة من دالة الصفر، ودالة الخلف، وعامل التركيب.

درس روبنسون ^{[ 10 ]} قيودًا مختلفة على قاعدة الاستدعاء الذاتي. أحدها ما يسمى بقاعدة التكرار حيث لا يمكن للدالة h الوصول إلى المعاملات x _i (في هذه الحالة، يمكننا أن نفترض دون فقدان للعمومية أن الدالة g هي دالة التطابق، حيث يمكن الحصول على الحالة العامة عن طريق التعويض):

${\displaystyle {\begin{aligned}f(0,x)&=x,\\f(S(y),x)&=h(y,f(y,x)).\end{aligned}}}$

لقد أثبت أنه لا يزال من الممكن الحصول على فئة جميع الدوال التكرارية الأولية بهذه الطريقة.

هناك قيد آخر أخذه روبنسون في الاعتبار ^{[ 10 ]} وهو الاستدعاء الذاتي البحت ، حيث لا يمكن لـ h الوصول إلى متغير الاستقراء y :

${\displaystyle {\begin{aligned}f(0,x_{1},\ldots ,x_{k})&=g(x_{1},\ldots ,x_{k}),\\f(S(y),x_{1},\ldots ,x_{k})&=h(f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k}).\end{aligned}}}$

أثبت غلادستون ^{[ 11 ]} أن هذه القاعدة كافية لتوليد جميع الدوال التكرارية الأولية. وقد حسّن غلادستون ^{[ 12 ]} هذا الأمر بحيث يكفي حتى الجمع بين هذين القيدين، أي قاعدة التكرار البحتة أدناه.

${\displaystyle {\begin{aligned}f(0,x)&=x,\\f(S(y),x)&=h(f(y,x)).\end{aligned}}}$

من الممكن إجراء المزيد من التحسينات: أثبت سيفرين ^{[ 13 ]} أن حتى قاعدة التكرار البحتة بدون معلمات ، أي

${\displaystyle {\begin{aligned}f(0)&=0,\\f(S(y))&=h(f(y)),\end{aligned}}}$

يكفي لتوليد جميع الدوال التكرارية الأولية الأحادية إذا قمنا بتوسيع مجموعة الدوال الأولية بإضافة عملية الطرح المقتطع x ∸ y . ونحصل على جميع الدوال التكرارية الأولية إذا أضفنا إليها دالة الجمع (+) كدالة أولية.

تُعرّف بعض أشكال الاستدعاء الذاتي الإضافية دوالًا تُعتبر في الواقع دوال استدعاء ذاتي بدائية. قد تكون التعريفات في هذه الأشكال أسهل في العثور عليها أو أكثر سلاسة في القراءة والكتابة. يُعرّف الاستدعاء الذاتي ذو مسار القيم دوال استدعاء ذاتي بدائية. كما تُعرّف بعض أشكال الاستدعاء الذاتي المتبادل دوال استدعاء ذاتي بدائية.

إنّ الدوال التي يمكن برمجتها في لغة البرمجة LOOP هي تحديدًا الدوال التكرارية الأولية. وهذا يُعطي توصيفًا مختلفًا لقوة هذه الدوال. أما القيد الرئيسي للغة LOOP، مقارنةً بلغة كاملة تورينج ، فهو أن عدد مرات تنفيذ كل حلقة في لغة LOOP يُحدد قبل بدء تنفيذها.

من أمثلة لغات البرمجة التكرارية البدائية تلك التي تحتوي على عوامل حسابية أساسية (مثل الجمع والطرح)، وعبارات شرطية ومقارنة (مثل IF-THEN، وEQUALS، وLESS-THAN)، وحلقات محدودة، مثل حلقة for الأساسية ، حيث يوجد حد أعلى معروف أو قابل للحساب لجميع الحلقات (FOR i FROM 1 TO n، مع عدم إمكانية تعديل i أو n بواسطة جسم الحلقة). لا يُسمح باستخدام هياكل تحكم ذات عمومية أكبر، مثل حلقات while أو IF-THEN متبوعة بـ GOTO ، في لغة التكرار البدائية.

لغة LOOP ، التي طُرحت في ورقة بحثية عام 1967 من قِبل ألبرت ر. ماير ودينيس م. ريتشي ، ^{[ 14 ]} هي إحدى هذه اللغات. تتطابق قدرتها الحاسوبية مع الدوال التكرارية الأساسية. ومن بين متغيرات لغة LOOP لغة BlooP التي ابتكرها دوغلاس هوفستاتر في كتابه Gödel, Escher, Bach . إن إضافة حلقات غير محدودة (WHILE، GOTO) تجعل اللغة تكرارية عامة وكاملة تورينج ، كما هو الحال في جميع لغات برمجة الحاسوب المستخدمة في العالم الحقيقي.

يُشير تعريف الدوال التكرارية الأولية إلى أن حسابها يتوقف عند كل مُدخل (بعد عدد محدود من الخطوات). من ناحية أخرى، تُعدّ مسألة التوقف غير قابلة للحل بالنسبة للدوال التكرارية العامة.