פונקציה פרימיטיבית רקורסיבית – הבדלי גרסאות

:<math>\ g(x , y ) = g (x-y , y) + 1</math> - כאשר החיסור פועל כמו שהוגדר לעיל.
== שימושים ==
מכיוון שמחלקת הפונקציות הפרימיטיביות רקורסיביות חלקית או שווה לכל מחלקת פונקציות הסגורה תחת רקורסיה פרימיטיבית, ומכיוון שמחלקות פונקציות רבות ומעניינות סגורות תחת רקורסיה פרימיטיבית, אזי אם נוכיח שמחלקחת סיבוכיות כלשהי, CL, מכילהסגורה אתלרקורסיה מחלקת הפונקציות הפרימיטיביות רקורסיביותפרימיטיבית, נקבל שכל הפונקציות הפרימיטיביות הרקורסיביות שייכות ל-CL. כך משייכים מגוון של פונקציות פרימיטיביות רקורסיביות למחלקות סיבוכיות חדשות, תוך הוכחת היות מחלקות אלו סגורות תחת רקורסיה פרימיטיבית, בלבד.
 
למשל, על מנת להוכיח שהפונקציות האריתמטיות הבסיסיות הן [[פונקציה רקורסיבית|פונקציות רקורסיביות]], די להוכיח שכל פונקציה פרימיטיבית רקורסיבית היא גם פונקציה רקורסיבית. וכך, כדי להראות היותר של פונקציה רקורסיבית, לעתים מציגים אותה כפונקציה פרימיטיבית רקורסיבית, ומכך גם רקורסיבית, בשל פשטות הדבר.
 
== קשר למודלים חישוביים שונים ==
קיימים קשרים הדוקים בין פונקציות פרימיטיביות רקורסיביות, ו[[פונקציה רקורסיבית|פונקציות רקורסיביות]]. לדוגמה, ניתן להראת שאם פונקציה היא רקורסיבית, ועוצרת תמיד לאחר מספר ידוע של צעדים (שחסום על ידי פונקציה פרימיטיבית רקורסיבית), אזי היא גם פרימיטיבית רקורסיבית.
20

עריכות