לדלג לתוכן

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

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

עריכות