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

אין תקציר עריכה
{{עריכה}}
פונקציות פרימיטיביות רקורסיביות הן אחד הנושאים הבסיסיים בתורת ה[[חישוביות]].
 
פונקציה פרימיטיבית רקורסיבית היא [[פונקציה]] בין מספר כלשהו של [[מכפלה קרטזית|מכפלות קרטזיות]] של [[מספר טבעי|קבוצת המספרים הטבעיים]] עם עצמה לבין קבוצת המספרים הטבעיים, הנוצרת מ[[הרכבה של פונקציות|הרכבת פונקציות]] ורקורסיה פרימיטיבית חוזרות ונשנות של מספר פונקציות בסיסיות קבועות: החזרת אפס, הוספת אחד, ושינוי סדר המשתנים.
 
מעבר להגיון הנעוץ בהגדרתן, הן מהוות שלב ביניים בדרך להגדרת [[פונקציות רקורסיביות]] מלאות. בנוסף, הוכחות רבות מסתמכות עליהן, בשל הגדרתן הנוחה.
ניתן להוכיח שרבות מן הפונקציות הבסיסיות ביותר בתורת המספרים הן פרימיטיביות רקורסיביות, כגון פונקציות [[חיבור|החיבור]] [[כפל|הכפל]] [[חזקה|החזקה]] [[עצרת|והעצרת]], בצד גרסאות מסוימות המתאימות למספרים שלמים של פונקציות [[חיסור|החיסור]] [[חילוק|והחילוק]].
 
 
==הגדרה==
[[מחלקת פונקציות|מחלקה של פונקציות]], בתורת ה[[חישוביות]], נקראת '''סגורה תחת רקורסיה פרימיטיבית''' (Primitive Recuresively Closed או PRC), אם היא מכילה את ה'''פונקציות התחיליות''':
משתמש אלמוני