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

מ
השלמה, הסרת תבנית
מ (בוט החלפות: כדי;)
מ (השלמה, הסרת תבנית)
בתורת ה[[חישוביות]], '''פונקציה פרימיטיבית רקורסיבית''' היא [[פונקציה]] בין מספר כלשהו של [[מכפלה קרטזית|מכפלות קרטזיות]] של [[מספר טבעי|קבוצת המספרים הטבעיים]] עם עצמה לבין קבוצת המספרים הטבעיים, הנוצרת מ[[הרכבה של פונקציות|הרכבת פונקציות]] ורקורסיהופעולה שנקראת "רקורסיה פרימיטיבית" חוזרותבאופן ונשנותחוזר שלונשנה על מספר פונקציות בסיסיות קבועות: הפונקציה הקבועה אפס, הוספת אחד, ובחירת אחד מרכיבי הפונקציההקלט.
{{עריכה}}
בתורת ה[[חישוביות]], '''פונקציה פרימיטיבית רקורסיבית''' היא [[פונקציה]] בין מספר כלשהו של [[מכפלה קרטזית|מכפלות קרטזיות]] של [[מספר טבעי|קבוצת המספרים הטבעיים]] עם עצמה לבין קבוצת המספרים הטבעיים, הנוצרת מ[[הרכבה של פונקציות|הרכבת פונקציות]] ורקורסיה פרימיטיבית חוזרות ונשנות של מספר פונקציות בסיסיות קבועות: הפונקציה הקבועה אפס, הוספת אחד, ובחירת אחד מרכיבי הפונקציה.
 
הפונקציות הפרימיטיביות הרקורסיביות מהוות שלב ביניים בדרך להגדרת [[פונקציה רקורסיבית|פונקציות רקורסיביות]] מלאות. בנוסף, הוכחות רבות לגבי מחלקות חישוביות מסתמכות עליהן בשל הגדרתן הנוחה. רבות מן הפונקציות הבסיסיות ב[[תורת המספרים]] הן פרימיטיביות רקורסיביות, כגון [[ארבע פעולות החשבון]], ה[[חזקה]], הוה[[עצרת]]. משיקולים טכניים יש להתאים מעט את פונקציות ה[[חיסור]] וה[[חילוק]] כך שיחזירו רק ערכים טבעיים.
 
==הגדרה==
 
כלומר, נגדיר:
<math> f(x,y)=\left\{\begin{matrix} x-y-x, & x \gele y \\ 0, & \mbox{else } \end{matrix}\right. </math>
ופונקציה זו תשמש אותנו כפונקציית החיסור, המצומצמת למספרים הטבעיים.
<!-- יש להוסיף הסבר מדוע היא רקורסיבית פרימיטיבית -->
 
כדי ליצור את פונקציית החיסור יש ליצור את פונקציית ה"קודם" - <math>\ p(x)</math> שמחזירה לכל מספר, חוץ מאפס, את המספר הקודם לו, ועבור אפס - היא מחזירה אפס. את פונקציית הקודם ניתן להגדיר על ידי רקורסיה פרימיטיבית:
:<math>\ p(0) = 0</math>
:<math>\ p (n+1) = n</math>
מכאן ניתן להגדיר את החיסור:
:<math>\ f(0,x,y) = n, x = y \cdot n + m </math><br />
:<math>\ f(n+1,x) = p (f (n,x) )</math>
===חילוק===
בדומה לפונקציית החיסור, מתקנים את פונקציית החילוק כך שתמונתה תהיה תמיד מספרים שלמים. לכן, מגדירים את פונקציית [[חילוק|החילוק]] כחלקכעיגול השלםכלפי מעלה של תוצאת החילוק. הדברזהו דומהלמעשה ל[[חילוק עם שארית]]. כלומרשלילית, כאשר מתעלמים מהשארית. החילוק מתבצע כך:
:<math>\ f(x,y) = n, x = y \cdot n + m , \ -y < m \le 0</math>
 
נגדיר את פונקציית החילוק:
<math>\ f(x,y) = n, x = y \cdot n + m </math><br />
:<math>\ g(0,x) = 0</math>
<!---איך עושים "חילוק" כזה?--->
:<math>\ g(x , y ) = g (x-y , y) + 1</math> - כאשר החיסור פועל כמו שהוגדר לעיל.
== שימושים ==
מכיוון שמחלקת הפונקציות הפרימיטיביות רקורסיביות חלקית או שווה לכל מחלקת פונקציות הסגורה תחת רקורסיה פרימיטיבית, ומכיוון שמחלקות פונקציות רבות ומעניינות סגורות תחת רקורסיה פרימיטיבית, אזי אם נוכיח שמחלקחת סיבוכיות כלשהי, CL, מכילה את מחלקת הפונקציות הפרימיטיביות רקורסיביות, נקבל שכל הפונקציות הפרימיטיביות הרקורסיביות שייכות ל-CL. כך משייכים מגוון של פונקציות פרימיטיביות רקורסיביות למחלקות סיבוכיות חדשות, תוך הוכחת היות מחלקות אלו סגורות תחת רקורסיה פרימיטיבית, בלבד.
למשל, על מנת להוכיח שהפונקציות האריתמטיות הבסיסיות הן [[פונקציה רקורסיבית|פונקציות רקורסיביות]], די להוכיח שכל פונקציה פרימיטיבית רקורסיבית היא גם פונקציה רקורסיבית. וכך, כדי להראות היותר של פונקציה רקורסיבית, לעתים מציגים אותה כפונקציה פרימיטיבית רקורסיבית, ומכך גם רקורסיבית, בשל פשטות הדבר.
== קשר למודלים חישוביים שונים ==
קיימים קשרים מעניינים ביותרהדוקים בין פונקציות פרימיטיביות רקורסיביות, ו[[פונקציה רקורסיבית|פונקציות רקורסיביות]]. בפרטלדוגמה, ניתן להראת שאם פונקציה היא רקורסיבית, ועוצרת תמיד לאחר מספר ידוע של צעדים (שחסום על ידי פונקציה פרימיטיבית רקורסיבית), אזי היא גם פרימיטיבית רקורסיבית.
 
למרות שנובע מכך שפונקציות רקורסיביות רבות ביותר הן פרימיטיביות רקורסיביות, קיימות פונקציות רקורסיביות שאינן פרימיטיביות רקורסיביות, כגון [[פונקציית אקרמן]].
 
 
[[קטגוריה:סיבוכיות]]