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