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

←‏שימושים: חזרה כפולה וחזרתית
מ (←‏שימושים: ניסוח)
(←‏שימושים: חזרה כפולה וחזרתית)
 
== שימושים ==
מכיוון שמחלקת הפונקציות הפרימיטיביות רקורסיביות חלקית או שווה לכל מחלקת פונקציות הסגורה תחת רקורסיה פרימיטיבית, ומכיוון שמחלקות פונקציות רבות ומעניינות סגורות תחת רקורסיה פרימיטיבית, אזי אם נוכיח שמחלקת סיבוכיות כלשהי, CL, סגורה לרקורסיה פרימיטיבית, נקבל שכל הפונקציות הפרימיטיביות הרקורסיביות שייכות ל-CL. כך משייכים מגוון של פונקציות פרימיטיביות רקורסיביות למחלקות סיבוכיות חדשות, תוך הוכחת היות מחלקות אלו סגורות תחת רקורסיה פרימיטיבית, בלבד.
 
מחלקת הפונקציות הפרימיטיביות רקורסיביות מוכלת בכל מחלקה הסגורה תחת רקורסיה פרימיטיבית והכוללת את הפונקציות הרקורסיביות פרימיטיביות היסודיות. למשל, על מנת להוכיח שהפונקציות האריתמטיות הבסיסיות הן [[פונקציה רקורסיבית|פונקציות רקורסיביות]], די להוכיח שכל פונקציה פרימיטיבית רקורסיבית היא גם פונקציה רקורסיבית. וכך, כדי להראות עבור פונקציה מסוימת היותה פונקציה רקורסיבית, לעיתים מספיק להראות אותה כפונקציה פרימיטיבית רקורסיבית, ומכך גם נובע שהיא רקורסיבית, בשל פשטות הדבר.
 
== קשר למודלים חישוביים שונים ==