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

אין תקציר עריכה
(סידור)
בתורת ה[[חישוביות]]; '''פונקציה פרימיטיבית רקורסיבית''' היא [[פונקציה]] n-מקומית (עבור n כלשהו) מ[[קבוצת המספרים הטבעיים]] לעצמה, הנוצרת מ[[הרכבה של פונקציות|הרכבת פונקציות]] ופעולה שנקראת "רקורסיה פרימיטיבית" באופן חוזר ונשנה על מספר פונקציות בסיסיות קבועות: הפונקציה הקבועה אפס, הוספת אחד, ובחירת אחד מרכיבי הקלט.
 
הפונקציות הפרימיטיביות הרקורסיביות מהוות שלב ביניים בדרך להגדרת [[פונקציה רקורסיבית|פונקציות רקורסיביות]] מלאות. בנוסף, הוכחות רבות לגבי מחלקות חישוביות מסתמכות עליהן בשל הגדרתן הנוחה. רבות מן הפונקציות הבסיסיות ב[[תורת המספרים]] הן פרימיטיביות רקורסיביות, כגון [[ארבע פעולות החשבון]], ה[[חזקה (מתמטיקה)|חזקה]] וה[[עצרת]]. משיקוליםגם טכניים יש להתאים מעט את פונקציותפעולות ה[[חיסור]] וה[[חילוק]] הן פרימיטיביות רקורסיביות לאחר שמתאימים אותן כך שיחזירו רק ערכים טבעיים.
 
==הגדרה==