פונקציה רקורסיבית – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ תיקון קל |
פונקציה רקורסיבית |
||
שורה 5:
===פונקציה רקורסיבית פרימיטיבית===
<!-- זו ההגדרה הראשונה שניתנה למושג הפונקציה הרקורסיבית. -->
קבוצת כל הפונקציות הרקורסיביות הפרימיטיביות מוגדרת להיות הקבוצה המינימלית של פונקציות מ<math>\N^k</math> למספרים הטבעיים, <math>\
*הפונקציה הקבועה 0 נמצאת ב-
*פונקציות ההטלה לקואורדינטה מסויימת נמצאות ב-
*פונקציית העוקב <math>\ f(n)=n+1</math> נמצאת ב-
*הקבוצה סגורה תחת [[הרכבת פונקציות]].
*הקבוצה סגורה תחת '''רקורסיה''' במובן הבא: f נמצאת ב-
:: אם מתקיים המקרה הראשון אז הקלט מועבר לפונקציה אחרת ב-R.
:: אם מתקיים המקרה השני אז מחשבים את f על הקלט <math>\ ( y-1, r_1 (x_1, \dots , x_{k-1} ), \dots ,r_{k-1} (x_1, \dots , x_{k-1} ) )</math> כאשר <math>\ r_i \in
הפונקציות הרקורסיביות הפרמיטיביות כוללות את כל הפונקציות האריתמטיות,
===פונקציה רקורסיבית===
הפונקציות הרקורסיביות מתקבלות מהפונקציות הרקורסיביות-פרימיטיביות על ידי הוספת אופטור, שמכונה אופרטור <math>\mu</math>. נסמן את קבוצת הפונקציות הרקורסיביות הפועלות על קלט בן k מספרים ב- <math>\ R^{(k)}</math>. אופרטור זה פועל על פונקציה רקורסיבית קיימת <math>\ f \in R^{(k+1)}</math>, ומחזיר את הפונקציה <math>\ \mu f (\in R^{(k)} )</math>, שעבור הקלט <math>\ (x_1, \dots , x_k)</math> מחזירה כפלט את ה-y המינימלי שעבורו מתקיים השיוויון <math>\ f(y,x_1, \dots , x_n ) =1</math>. y כזה לא בהכרח קיים, ורק אם הוא קיים הפונקציה עוצרת על אותו קלט.
| |||