פונקציה רקורסיבית – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
Yonidebot (שיחה | תרומות)
מ בוט החלפות: שוויון;
שורה 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 המינימלי שעבורו מתקיים השיוויוןהשוויון <math>\ f(y,x_1, \dots , x_n ) =1</math>. y כזה לא בהכרח קיים, ורק אם הוא קיים הפונקציה עוצרת על אותו קלט. פונקציות אלו הן פונקציות חלקיות, כלומר הן אינן מוגדרות על כל קלט ולפעמים אפילו על שום קלט. לדוגמה הפעלת אופרטור <math>\mu</math> על הפונקציה הפרימיטיביות-רקורסיבית הקבועה 1 תיצור בהכרח פונקציה שלא מוגדרת על שום מספר טבעי.
 
תוספת האופטור מגדילה בהרבה את החופש ביצירת הפונקציות ולפי [[תזת צ'רץ'-טיורינג]]- מספיקה כדי לבנות את כל האלגוריתמים הסבירים.