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

שינויים ותוספות
מ (פונקציות פרימיטיביות רקורסיביות הועבר לפונקציה פרימיטיבית רקורסיבית במקום הפניה: שם ערך נכתב בצורת היחיד)
(שינויים ותוספות)
{{עריכה}}
בתורת ה[[חישוביות]], '''פונקציה פרימיטיבית רקורסיבית''' היא [[פונקציה]] בין מספר כלשהו של [[מכפלה קרטזית|מכפלות קרטזיות]] של [[מספר טבעי|קבוצת המספרים הטבעיים]] עם עצמה לבין קבוצת המספרים הטבעיים, הנוצרת מ[[הרכבה של פונקציות|הרכבת פונקציות]] ורקורסיה פרימיטיבית חוזרות ונשנות של מספר פונקציות בסיסיות קבועות: החזרתהפונקציה הקבועה אפס, הוספת אחד, ובחירת אחד מרכיבי הפונקציה.
 
מעבר להגיון הנעוץ בהגדרתן, הפונקציות הפרימיטיביות הרקורסיביות מהוות שלב ביניים בדרך להגדרת [[פונקציה רקורסיבית|פונקציות רקורסיביות]] מלאות. בנוסף, הוכחות רבות לגבי מחלקות חישוביות מסתמכות עליהן בשל הגדרתן הנוחה. רבות מן הפונקציות הבסיסיות בתורתב[[תורת המספרים]] הן פרימיטיביות רקורסיביות, כגון פונקציות ה[[חיבור]],ארבע ה[[כפלפעולות החשבון]], ה[[חזקה]], ה[[עצרת]], בצד. גרסאותמשיקולים מסוימותטכניים המתאימותיש למספריםלהתאים שלמיםמעט שלאת פונקציות ה[[חיסור]] וה[[חילוק]] כך שיחזירו רק ערכים טבעיים.
 
==הגדרה==
ההגדרה של פונקציות אלו כפונקציות פרימיטיביות רקורסיביות דומה להגדרה הניתנת בבית הספר, ולכן אינטואיטיבית ופשוטה.
בתורת ה[[מחלקתחישוביות]], פונקציות|מחלקה של פונקציות]] [[פונקציה על|שלמותפונקציות]], בתורת ה[[חישוביות]]שלמות, נקראת '''סגורה תחת רקורסיה פרימיטיבית''' (Primitive Recursively Closed או PRC), אם היא מכילהסגורה אתתחת ה'''פונקציותהפעולה התחיליות'''של יצירת פונקציה חדשה מהפונקציות קיימות באופן הבא:
 
את הפונקציה החדשה נגדיר על נקודת התחלה באמצעות פונקציה קיימת, וכן נתאר את התקדמותה באמצעות פונקציה נוספת:
אם <math>\ f: \N^k \rightarrow \N</math> ו-<math>\ g: \N^{k+2} \rightarrow \N</math> פונקציות פרימיטיביותשנמצאות במחלקה, אז הפונקציה <math>\ h: \N^{k+1} \rightarrow \N</math> שמוגדרת ב[[רקורסיה]]:
* <math>\ h(0, x_1 , ... , x_k)=f(x_1, ... , x_k)</math>
*<math>\ h(n+1,x_1, ... ,x_k)=g(h(n,x_1, ... ,x_k), n, x_1, ... ,x_k )</math>
היא פונקציה רקורסיביתהנוצרת מהן על ידי רקורסיה פרימיטיבית.
 
'''מחלקת הפונקציות הרקורסיביות פרימיטיביות''' היא מחלקת הפונקציות שמכילה את הפונקציות התחיליות:
==הגדרה==
[[מחלקת פונקציות|מחלקה של פונקציות]] [[פונקציה על|שלמות]], בתורת ה[[חישוביות]], נקראת '''סגורה תחת רקורסיה פרימיטיבית''' (Primitive Recursively Closed או PRC), אם היא מכילה את ה'''פונקציות התחיליות''':
*<math>\
s(x) = x+1
</math> - פונקציית העוקב.
 
*<math>\
n(x) = 0
</math> - פונקציית האפס.
 
*<math>\ s_n^i(x_1, ... , x_{i-1}, x_i, x_{i+1}, ... , x_n) = x_i</math> - פונקציית ההטלה לרכיב ה-i.<br />
ובנוסף סגורה לפעולות של [[הרכבה של פונקציות]], ורקורסיה פרימיטיבית. כלומר, זוהי מחלקת ההפונקציותהפונקציות שמכילה בדיוק את הפונקציות התחיליות, ואת כל הפונקציות המתקבלות משרשור והרכבה חוזרת ונשנית שלהן מספר סופי של פעמים, נקראת '''מחלקת הפונקציות הפרימיטיביות רקורסיביות'''. ניתן להראות שהיא מחלקת הפונקציות הסגורה תחת רקורסיה פרימיטיבית המינימלית. כל פונקציה השייכת למחלקה מינימלית זו נקראת '''פונקציה פרימיטיבית רקורסיבית'''.
 
ובנוסף סגורה לפעולות של [[הרכבה של פונקציות]], ורקורסיה פרימיטיבית. רקורסיה פרימיטיבית היא הגדרת פונקציה חדשה באמצעות הגדרתה על נקודת התחלה באמצעות פונקציה רקורסיבית פרימיטיבית, ותיאור ההתקדמות שלה באמצעות פונקציה רקורסיבית פרימיטיבית נוספת:
אם <math>\ f: \N^k \rightarrow \N</math> ו-<math>\ g: \N^{k+2} \rightarrow \N</math> פונקציות פרימיטיביות, אז הפונקציה <math>\ h: \N^{k+1} \rightarrow \N</math> שמוגדרת ב[[רקורסיה]]:
* <math>\ h(0, x_1 , ... , x_k)=f(x_1, ... , x_k)</math>
*<math>\ h(n+1,x_1, ... ,x_k)=g(h(n,x_1, ... ,x_k), n, x_1, ... ,x_k )</math>
היא פונקציה רקורסיבית פרימיטיבית.
 
 
מחלקת ההפונקציות שמכילה בדיוק את הפונקציות התחיליות, ואת כל הפונקציות המתקבלות משרשור והרכבה חוזרת ונשנית שלהן מספר סופי של פעמים, נקראת '''מחלקת הפונקציות הפרימיטיביות רקורסיביות'''. ניתן להראות שהיא מחלקת הפונקציות הסגורה תחת רקורסיה פרימיטיבית המינימלית. כל פונקציה השייכת למחלקה מינימלית זו נקראת '''פונקציה פרימיטיבית רקורסיבית'''.
 
== דוגמאות ==
פונקציות רבות מ[[תורת המספרים]], ובהן כל [[אריתמטיקה|הפונקציות האריתמטיות]] הינן פונקציות פרימיטיביות רקורסיביות, לעתים לאחר שינויים קטנים בהגדרת הפונקציה. מכיוון שתמונת פונקציה פרימיטיבית רקורסיבית חייבת להיות מספר טבעי, יש לשנות את הפונקציות בהן התמונה אינה מספר טבעי, כך שתתאים ככל האפשר להגדרה המקורית.
 
להלן מספר פונקציות פרימיטיביות רקורסיביות פשוטות.:
 
===חיבור===
פונקציית [[חיבור|החיבור]]:
<math>\ f(x,y) = x+y </math> <br />
היא פונקציה פרימיטיבית רקורסיבית.:
<!---צריך לבוא הסבר על למה היא פרימיטיבית רקורסיבית--->
 
פונקציית הזהות, <math>\ g(x) = x</math> היא פונקציה רקורסיבית פרימיטיבית - זוהי למעשה פונקציית ההטלה לרכיב הראשון. לכן, ניתן להגדיר על ידי רקורסיה פרימיטיבית:
===חיסור===
:<math>\ f(0,x) = g(x) =x</math>
פונקציית [[חיסור|החיסור]] מקבלת כקלט שני מספרים טבעיים, ומחזירה את ההפרש ביניהם. תמונת פונקציית החיסור אינה תמיד מספר טבעי, ולכן יש לתקן זאת. למשל, כאשר מופעלת פונקציית החיסור הרגילה על הפרמטרים 4 ו6 (ארבע פחות שש), תמונת הפונקציה תהיה הערך מינוס 2, אשר אינו מספר טבעי. לכן נשנה את תמונת הפונקציה ל-0 כאשר התמונה שלילית. כך, תמונת הפונקציה על הפרמטרים 4 ו-6 היא 0.
:<math> \ f(n+1 , x) = s(f(n,x)) = f(n,x) + 1</math>
 
כלומר, נגדיר:
<math> f(x,y)=\left\{\begin{matrix} x-y, & x \ge y \\ 0, & \mbox{else } \end{matrix}\right. </math>
ופונקציה זו תשמש אותנו כפונקציית החיסור, המצומצמת למספרים הטבעיים.
<!---צריך לבוא הסבר על למה היא פרימיטיבית רקורסיבית--->
 
===כפל, חזקה, ועצרת===
 
הן פרימיטיבית רקורסיבית גם כן. ניתן להוכיח זאת באופן דומה לפונקציית החיבור.
 
===חיסור===
פונקציית [[חיסור|החיסור]] מקבלת כקלט שני מספרים טבעיים, ומחזירה את ההפרש ביניהם. תמונת פונקציית החיסור אינה תמיד מספר טבעי, ולכן יש לתקן זאת. למשל, כאשר מופעלת פונקציית החיסור הרגילה על הפרמטרים 4 ו6 (ארבע פחות שש), תמונת הפונקציה תהיה הערך מינוס 2, אשר אינו מספר טבעי. לכן נשנה את תמונת הפונקציה ל-0 כאשר התמונה שלילית. כך, תמונת הפונקציה על הפרמטרים 4 ו-6 היא 0.
 
כלומר, נגדיר:
<math> f(x,y)=\left\{\begin{matrix} x-y, & x \ge y \\ 0, & \mbox{else } \end{matrix}\right. </math>
ופונקציה זו תשמש אותנו כפונקציית החיסור, המצומצמת למספרים הטבעיים.
<!-- יש להוסיף הסבר מדוע היא רקורסיבית פרימיטיבית -->
 
===חילוק===
בדומה לפונקציית החיסור, מתקנים את פונקציית החילוק כך שתמונתה תהיה תמיד מספרים שלמים. לכן, מגדירים את פונקציית [[חילוק|החילוק]] כחלק השלם של תוצאת החילוק. הדבר דומה ל[[חילוק עם שארית|לחילוק עם שארית]]. כלומר, כך:
 
<math>\ f(x,y) = n, x = y \cdot n + m </math><br />