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

מ (תוספת)
(יישור קו עם פונקציה רקורסיבית)
==הגדרה==
[[מחלקת פונקציות|מחלקה של פונקציות]], בתורת ה[[חישוביות]], נקראת '''סגורה תחת רקורסיה פרימיטיבית''' (PRC), אם היא מכילה את ה'''פונקציות התחיליות''':<br />
:<math>\
s(x) = x+1
</math> -פונקצית העוקב.<br />
:<math>\
n(x) = 0
</math> -פונקצית האפס.<br />
:<math>\
s_n^i(x_1, ... , x_{i-1}, x_i, x_{i+1}, ... , x_n) = x_i
</math> -פונקצית ההטלה לרכיב ה-i.<br />
ובנוסף סגורה לפעולות של [[הרכבה של פונקציות]], ורקורסיה פרימיטיבית. כאשר הרקורסיה הפרימיטיבית היא בעצם הגדרת פונקציה חדשה באמצעות הגדרתה על נקודת התחלה באמצעות פונקציה רקורסיבית פרימיטיבית, ותיאור ההתקדמות שלה באמצעות פונקציה רקורסיבית פרימיטיבית אחרת:<br>
ובנוסף סגורה לפעולות של [[הרכבה של פונקציות]], ו-[[רקורסיה]].
אם <math>\ f: \N^k \rightarrow \N</math> ו-<math>\ g: \N^{k+2} \rightarrow \N</math> פונקציות פרימיטיביות, אז הפונקציה <math>\ h: \N^{k+1} \rightarrow \N</math> שמוגדרת ב[[רקורסיה]]:
 
* <math>\ h(0, x_1 , ... , x_k)=f(x_1, ... , x_k)</math>
*<math>\ h(n+1,x_1, ... ,x_k)=g(h(n,x_1, ... ,x_k), n, x_1, ... ,x_k )</math>
היא פונקציה רקורסיבית פרימיטיבית. <br>
מחלקת ה-PRC שמכילה בדיוק את הפונקציות התחיליות, ואת כל הפונקציות המתקבלות משרשור והרכבה חוזרת ונשנית שלהן מספר סופי של פעמים, נקראת '''מחלקת הפונקציות הפרימיטיביות רקורסיביות'''. ניתן להראות שהיא מחלקת הפונקציות PRC המינימלית.