הבדלים בין גרסאות בדף "פונקציה פרימיטיבית רקורסיבית"

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

עריכות