ויקיפדיה

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

עיון אינטראקטיבי בהיסטוריה
→ העריכה הקודמתהעריכה הבאה ←
תוכן שנמחק תוכן שנוסף
חזותיקוד ויקי
אירי (שיחה | תרומות)
65 עריכות
מ ←‏שימושים: ניסוח
←‏שימושים: חזרה כפולה וחזרתית
שורה 66:
 
== שימושים ==
מכיוון שמחלקת הפונקציות הפרימיטיביות רקורסיביות חלקית או שווה לכל מחלקת פונקציות הסגורה תחת רקורסיה פרימיטיבית, ומכיוון שמחלקות פונקציות רבות ומעניינות סגורות תחת רקורסיה פרימיטיבית, אזי אם נוכיח שמחלקת סיבוכיות כלשהי, CL, סגורה לרקורסיה פרימיטיבית, נקבל שכל הפונקציות הפרימיטיביות הרקורסיביות שייכות ל-CL. כך משייכים מגוון של פונקציות פרימיטיביות רקורסיביות למחלקות סיבוכיות חדשות, תוך הוכחת היות מחלקות אלו סגורות תחת רקורסיה פרימיטיבית, בלבד.
 
מחלקת הפונקציות הפרימיטיביות רקורסיביות מוכלת בכל מחלקה הסגורה תחת רקורסיה פרימיטיבית והכוללת את הפונקציות הרקורסיביות פרימיטיביות היסודיות. למשל, על מנת להוכיח שהפונקציות האריתמטיות הבסיסיות הן [[פונקציה רקורסיבית|פונקציות רקורסיביות]], די להוכיח שכל פונקציה פרימיטיבית רקורסיבית היא גם פונקציה רקורסיבית. וכך, כדי להראות עבור פונקציה מסוימת היותה פונקציה רקורסיבית, לעיתים מספיק להראות אותה כפונקציה פרימיטיבית רקורסיבית, ומכך גם נובע שהיא רקורסיבית, בשל פשטות הדבר.
 
== קשר למודלים חישוביים שונים ==
אוחזר מתוך "https://he.wikipedia.org/wiki/פונקציה_פרימיטיבית_רקורסיבית"