פונקציה רקורסיבית – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ בוט החלפות: שוויון; |
|||
שורה 21:
===פונקציה רקורסיבית===
הפונקציות הרקורסיביות מתקבלות מהפונקציות הרקורסיביות-פרימיטיביות על ידי הוספת [[אופרטור]], שמכונה אופרטור <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 המינימלי שעבורו מתקיים
תוספת האופטור מגדילה בהרבה את החופש ביצירת הפונקציות ולפי [[תזת צ'רץ'-טיורינג]]- מספיקה כדי לבנות את כל האלגוריתמים הסבירים.
|