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

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