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

עיון אינטראקטיבי בהיסטוריה

→ העריכה הקודמת העריכה הבאה ←

תוכן שנמחק תוכן שנוסף

חזותיקוד ויקי

בשורה

גרסה מ־11:41, 25 בספטמבר 2006

פרק זה טעון עריכה. אנא תרמו לוויקיפדיה ועזרו לערוך אותו. ייתכן שתמצאו פירוט בדף השיחה.

פונקציות פרימיטיביות רקורסיביות הן אחד הנושאים הבסיסיים בתורת החישוביות.

פונקציה פרימיטיבית רקורסיבית היא פונקציה בין מספר כלשהו של מכפלות קרטזיות של קבוצת המספרים הטבעיים עם עצמה לבין קבוצת המספרים הטבעיים, הנוצרת מהרכבת פונקציות ורקורסיה פרימיטיבית חוזרות ונשנות של מספר פונקציות בסיסיות קבועות: החזרת אפס, הוספת אחד, ובחירת אחד מרכיבי הפונקציה.

מעבר להגיון הנעוץ בהגדרתן, הן מהוות שלב ביניים בדרך להגדרת פונקציות רקורסיביות מלאות. בנוסף, הוכחות רבות לגבי מחלקות חישוביות מסתמכות עליהן, בשל הגדרתן הנוחה. רבות מן הפונקציות הבסיסיות בתורת המספרים הן פרימיטיביות רקורסיביות, כגון פונקציות החיבור הכפל החזקה והעצרת, בצד גרסאות מסוימות המתאימות למספרים שלמים של פונקציות החיסור והחילוק.

ההגדרה של פונקציות אלו כפונקציות פרימיטיביות רקורסיביות דומה להגדרה הניתנת בבית הספר, ולכן אינטואיטיבית ופשוטה.

הגדרה

מחלקה של פונקציות שלמות, בתורת החישוביות, נקראת סגורה תחת רקורסיה פרימיטיבית (Primitive Recuresively Closed או PRC), אם היא מכילה את הפונקציות התחיליות:

$\ s(x)=x+1$ - פונקציית העוקב.

$\ n(x)=0$ - פונקציית האפס.

$\ s_{n}^{i}(x_{1},...,x_{i-1},x_{i},x_{i+1},...,x_{n})=x_{i}$ - פונקציית ההטלה לרכיב ה-i.

ובנוסף סגורה לפעולות של הרכבה של פונקציות, ורקורסיה פרימיטיבית. רקורסיה פרימיטיבית היא הגדרת פונקציה חדשה באמצעות הגדרתה על נקודת התחלה באמצעות פונקציה רקורסיבית פרימיטיבית, ותיאור ההתקדמות שלה באמצעות פונקציה רקורסיבית פרימיטיבית נוספת: אם $\ f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ ו- $\ g:\mathbb {N} ^{k+2}\rightarrow \mathbb {N}$ פונקציות פרימיטיביות, אז הפונקציה $\ h:\mathbb {N} ^{k+1}\rightarrow \mathbb {N}$ שמוגדרת ברקורסיה:

$\ h(0,x_{1},...,x_{k})=f(x_{1},...,x_{k})$
$\ h(n+1,x_{1},...,x_{k})=g(h(n,x_{1},...,x_{k}),n,x_{1},...,x_{k})$

היא פונקציה רקורסיבית פרימיטיבית.

מחלקת ההפונקציות שמכילה בדיוק את הפונקציות התחיליות, ואת כל הפונקציות המתקבלות משרשור והרכבה חוזרת ונשנית שלהן מספר סופי של פעמים, נקראת מחלקת הפונקציות הפרימיטיביות רקורסיביות. ניתן להראות שהיא מחלקת הפונקציות הסגורה תחת רקורסיה פרימיטיבית המינימלית. כל פונקציה השייכת למחלקה מינימלית זו נקראת פונקציה פרימיטיבית רקורסיבית.

דוגמאות

פונקציות רבות מתורת המספרים, ובהן כל הפונקציות האריתמטיות הינן פונקציות פרימיטיביות רקורסיביות, לעתים לאחר שינויים קטנים בהגדרת הפונקציה. מכיוון שתמונת פונקציה פרימיטיבית רקורסיבית חייבת להיות מספר טבעי, יש לשנות את הפונקציות בהן התמונה אינה מספר טבעי, כך שתתאים ככל האפשר להגדרה המקורית.

להלן מספר פונקציות פרימיטיביות רקורסיביות פשוטות.

חיבור

פונקצית החיבור: $\ f(x,y)=x+y$
היא פונקציה פרימיטיבית רקורסיבית. {צריך לבוא הסבר על למה היא פרימיטיבית רקורסיבית}

חיסור

פונקצית החיסור מקבלת כקלט שני מספרים טבעיים, ומחזירה את ההפרש ביניהם. תמונת פונקצית החיסור אינה תמיד מספר טבעי, ולכן יש לתקן זאת. למשל, כאשר מופעלת פונקציית החיסור הרגילה על הפרמטרים 4 ו6 (ארבע פחות שש), תמונת הפונקציה תהיה הערך מינוס 2, אשר אינו מספר טבעי. לכן נשנה את תמונת הפונקציה ל-0 כאשר התמונה שלילית. כך, תמונת הפונקציה על הפרמטרים 4 ו-6 היא 0.

כלומר, נגדיר: $f(x,y)=\left\{{\begin{matrix}x-y,&x\geq y\\0,&{\mbox{else }}\end{matrix}}\right.$ ופונקציה זו תשמש אותנו כפונקציית החיסור, המצומצמת למספרים הטבעיים. {צריך לבוא הסבר על למה היא פרימיטיבית רקורסיבית}

כפל, חזקה, ועצרת

פונקציית הכפל, החזקה, והעצרת:

$\ f(x,y)=x\cdot y$
$\ f(x,y)=x^{y}$
$\ f(x)=x!$
הן פרימיטיבית רקורסיבית גם כן. ניתן להוכיח זאת באופן דומה לפונקצית החיבור.

חילוק

בדומה לפונקצית החיסור, מתקנים את פונקצית החילוק כך שתמונתה תהיה תמיד מספרים שלמים. לכן, מגדירים את פונקצית החילוק כחלק השלם של תוצאת החילוק. הדבר דומה לחילוק עם שארית. כלומר, כך:

$\ f(x,y)=n,x=y\cdot n+m$
{איך עושים "חילוק" כזה?}

שימושים

מכיוון שמחלקת הפונקציות הפרימיטיביות רקורסיביות חלקית או שווה לכל מחלקת פונקציות הסגורה תחת רקורסיה פרימיטיבית, ומכיוון שמחלקות פונקציות רבות ומעניינות סגורות תחת רקורסיה פרימיטיבית, אזי אם נוכיח שמחלקחת סיבוכיות כלשהי, CL, מכילה את מחלקת הפונקציות הפרימיטיביות רקורסיביות, נקבל שכל הפונקציות הפרימיטיביות הרקורסיביות שייכות ל-CL. כך משייכים מגוון של פונקציות פרימיטיביות רקורסיביות למחלקות סיבוכיות חדשות, תוך הוכחת היות מחלקות אלו סגורות תחת רקורסיה פרימיטיבית, בלבד.

למשל, על מנת להוכיח שהפונקציות האריתמטיות הבסיסיות הן פונקציות רקורסיביות, די להוכיח שכל פונקציה פרימיטיבית רקורסיבית היא גם פונקציה רקורסיבית. וכך, בכדי להראות היותר של פונקציה רקורסיבית, לעתים מציגים אותה כפונקציה פרימיטיבית רקורסיבית, ומכך גם רקורסיבית, בשל פשטות הדבר.

קשר למודלים חישוביים שונים

קיימים קשרים מעניינים ביותר בין פונקציות פרימיטיביות רקורסיביות, ופונקציות רקורסיביות. בפרט, ניתן להראת שאם פונקציה היא רקורסיבית, ועוצרת תמיד לאחר מספר ידוע של צעדים (שחסום על ידי פונקציה פרימיטיבית רקורסיבית), אזי היא גם פרימיטיבית רקורסיבית.

למרות שנובע מכך שפונקציות רקורסיביות רבות ביותר הן פרימיטיביות רקורסיביות, קיימות פונקציות רקורסיביות שאינן פרימיטיביות רקורסיביות, כמו לדוגמה פונקציית אקרמן.

@@ שורה 2: / שורה 2: @@
 פונקציות פרימיטיביות רקורסיביות הן אחד הנושאים הבסיסיים בתורת ה[[חישוביות]].
-פונקציה פרימיטיבית רקורסיבית היא [[פונקציה]] בין מספר כלשהו של [[מכפלה קרטזית|מכפלות קרטזיות]] של [[מספר טבעי|קבוצת המספרים הטבעיים]] עם עצמה לבין קבוצת המספרים הטבעיים, הנוצרת מ[[הרכבה של פונקציות|הרכבת פונקציות]] ורקורסיה פרימיטיבית חוזרות ונשנות של מספר פונקציות בסיסיות קבועות: החזרת אפס, הוספת אחד, ושינוי סדר המשתנים.
+פונקציה פרימיטיבית רקורסיבית היא [[פונקציה]] בין מספר כלשהו של [[מכפלה קרטזית|מכפלות קרטזיות]] של [[מספר טבעי|קבוצת המספרים הטבעיים]] עם עצמה לבין קבוצת המספרים הטבעיים, הנוצרת מ[[הרכבה של פונקציות|הרכבת פונקציות]] ורקורסיה פרימיטיבית חוזרות ונשנות של מספר פונקציות בסיסיות קבועות: החזרת אפס, הוספת אחד, ובחירת אחד מרכיבי הפונקציה.
-מעבר להגיון הנעוץ בהגדרתן, הן מהוות שלב ביניים בדרך להגדרת [[פונקציות רקורסיביות]] מלאות. בנוסף, הוכחות רבות מסתמכות עליהן, בשל הגדרתן הנוחה.
-ניתן להוכיח שרבות מן הפונקציות הבסיסיות ביותר בתורת המספרים הן פרימיטיביות רקורסיביות, כגון פונקציות [[חיבור|החיבור]] [[כפל|הכפל]] [[חזקה|החזקה]] [[עצרת|והעצרת]], בצד גרסאות מסוימות המתאימות למספרים שלמים של פונקציות [[חיסור|החיסור]] [[חילוק|והחילוק]].
+מעבר להגיון הנעוץ בהגדרתן, הן מהוות שלב ביניים בדרך להגדרת [[פונקציות רקורסיביות]] מלאות. בנוסף, הוכחות רבות לגבי מחלקות חישוביות מסתמכות עליהן, בשל הגדרתן הנוחה. רבות מן הפונקציות הבסיסיות בתורת המספרים הן פרימיטיביות רקורסיביות, כגון פונקציות [[חיבור|החיבור]] [[כפל|הכפל]] [[חזקה|החזקה]] [[עצרת|והעצרת]], בצד גרסאות מסוימות המתאימות למספרים שלמים של פונקציות [[חיסור|החיסור]] [[חילוק|והחילוק]].
+ההגדרה של פונקציות אלו כפונקציות פרימיטיביות רקורסיביות דומה להגדרה הניתנת בבית הספר, ולכן אינטואיטיבית ופשוטה.
 ==הגדרה==
-[[מחלקת פונקציות|מחלקה של פונקציות]], בתורת ה[[חישוביות]], נקראת '''סגורה תחת רקורסיה פרימיטיבית''' (Primitive Recuresively Closed או PRC), אם היא מכילה את ה'''פונקציות התחיליות''':
+[[מחלקת פונקציות|מחלקה של פונקציות]] [[פונקציה על|שלמות]], בתורת ה[[חישוביות]], נקראת '''סגורה תחת רקורסיה פרימיטיבית''' (Primitive Recuresively Closed או PRC), אם היא מכילה את ה'''פונקציות התחיליות''':
 *<math>\
 s(x) = x+1
-</math>  -פונקציית העוקב.
+</math>  - פונקציית העוקב.
 *<math>\
 n(x) = 0
-</math>  -פונקציית האפס.
+</math>  - פונקציית האפס.
-*<math>\ s_n^i(x_1, ... , x_{i-1}, x_i, x_{i+1}, ... , x_n) = x_i</math>  -פונקציית ההטלה לרכיב ה-i.<br />
+*<math>\ s_n^i(x_1, ... , x_{i-1}, x_i, x_{i+1}, ... , x_n) = x_i</math>  - פונקציית ההטלה לרכיב ה-i.<br />
-ובנוסף סגורה לפעולות של [[הרכבה של פונקציות]], ורקורסיה פרימיטיבית. רקורסיה פרימיטיבית היא הגדרת פונקציה חדשה באמצעות הגדרתה על נקודת התחלה באמצעות פונקציה רקורסיבית פרימיטיבית, ותיאור ההתקדמות שלה באמצעות פונקציה רקורסיבית פרימיטיבית נוספת.:<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>
-היא פונקציה רקורסיבית פרימיטיבית. <br>
+היא פונקציה רקורסיבית פרימיטיבית.
-מחלקת ה-PRC שמכילה בדיוק את הפונקציות התחיליות, ואת כל הפונקציות המתקבלות משרשור והרכבה חוזרת ונשנית שלהן מספר סופי של פעמים, נקראת '''מחלקת הפונקציות הפרימיטיביות רקורסיביות'''. ניתן להראות שהיא מחלקת הפונקציות PRC המינימלית.
+מחלקת ההפונקציות שמכילה בדיוק את הפונקציות התחיליות, ואת כל הפונקציות המתקבלות משרשור והרכבה חוזרת ונשנית שלהן מספר סופי של פעמים, נקראת '''מחלקת הפונקציות הפרימיטיביות רקורסיביות'''. ניתן להראות שהיא מחלקת הפונקציות הסגורה תחת רקורסיה פרימיטיבית המינימלית. כל פונקציה השייכת למחלקה מינימלית זו נקראת '''פונקציה פרימיטיבית רקורסיבית'''.
 == דוגמאות ==
+פונקציות רבות מ[[תורת המספרים]], ובהן כל [[אריתמטיקה|הפונקציות האריתמטיות]] הינן פונקציות פרימיטיביות רקורסיביות, לעתים לאחר שינויים קטנים בהגדרת הפונקציה. מכיוון שתמונת פונקציה פרימיטיבית רקורסיבית חייבת להיות מספר טבעי, יש לשנות את הפונקציות בהן התמונה אינה מספר טבעי, כך שתתאים ככל האפשר להגדרה המקורית.
-מכיוון שמחלקת הפונקציות הפרימיטיביות רקורסיביות חלקית או שווה לכל מחלקת פונקציות PRC, ומכיוון שמחלקות פונקציות רבות ומעניינות הן PRC, נוח למצוא פונקציות שנמצאות במחלקת הפונקציות הפרימיטיביות רקורסיביות, ולהראות בכך שהן נמצאות בכל מחלקת פונקציות PRC.
+להלן מספר פונקציות פרימיטיביות רקורסיביות פשוטות.
+===חיבור===
+פונקצית [[חיבור|החיבור]]:
+<math>\ f(x,y) = x+y </math> <br />
+היא פונקציה פרימיטיבית רקורסיבית.
+{צריך לבוא הסבר על למה היא פרימיטיבית רקורסיבית}
+===חיסור===
+פונקצית [[חיסור|החיסור]] מקבלת כקלט שני מספרים טבעיים, ומחזירה את ההפרש ביניהם. תמונת פונקצית החיסור אינה תמיד מספר טבעי, ולכן יש לתקן זאת. למשל, כאשר מופעלת פונקציית החיסור הרגילה על הפרמטרים 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>
+ופונקציה זו תשמש אותנו כפונקציית החיסור, המצומצמת למספרים הטבעיים.
+{צריך לבוא הסבר על למה היא פרימיטיבית רקורסיבית}
+===כפל, חזקה, ועצרת===
+פונקציית [[כפל|הכפל]], [[חזקה|החזקה]], [[עצרת|והעצרת]]:
-פונקציות כאלו הן, למשל: <br />
-<math>\ f(x,y) = x+y </math> <br />
 <math>\ f(x,y) = x\cdot y </math><br />
 <math>\ f(x,y) = x^y </math><br />
 <math>\ f(x) = x! </math><br />
+הן פרימיטיבית רקורסיבית גם כן. ניתן להוכיח זאת באופן דומה לפונקצית החיבור.
+===חילוק===
-כלומר, ניתן להראות שכל אחת מהן מתקבלת מהרכבה, ורקורסיה, של הפונקציות התחיליות, ומכך נובע שכל אחת מהן נמצאת במחלקת הפונקציות הפרימיטיביות רקורסיביות. כך נקבל שכל אחת מהן נמצאת ב'''כל''' מחלקת פונציות PRC.
+בדומה לפונקצית החיסור, מתקנים את פונקצית החילוק כך שתמונתה תהיה תמיד מספרים שלמים. לכן, מגדירים את פונקצית [[חילוק|החילוק]] כחלק השלם של תוצאת החילוק. הדבר דומה [[חילוק עם שארית|לחילוק עם שארית]]. כלומר, כך:
+<math>\ f(x,y) = n, x = y \cdot n + m </math><br />
+{איך עושים "חילוק" כזה?}
 == שימושים ==
+מכיוון שמחלקת הפונקציות הפרימיטיביות רקורסיביות חלקית או שווה לכל מחלקת פונקציות הסגורה תחת רקורסיה פרימיטיבית, ומכיוון שמחלקות פונקציות רבות ומעניינות סגורות תחת רקורסיה פרימיטיבית, אזי אם נוכיח שמחלקחת סיבוכיות כלשהי, CL, מכילה את מחלקת הפונקציות הפרימיטיביות רקורסיביות, נקבל שכל הפונקציות הפרימיטיביות הרקורסיביות שייכות ל-CL. כך משייכים מגוון של פונקציות פרימיטיביות רקורסיביות למחלקות סיבוכיות חדשות, תוך הוכחת היות מחלקות אלו סגורות תחת רקורסיה פרימיטיבית, בלבד.
-בהוכחות מתמטיות הדבר יכול להיות שימושי ביותר.
-כדוגמה, ניתן להראות שמחלקת [[פונקציה רקורסיבית|הפונקציות הרקורסיביות]] היא מחלקת PRC, וכך לקבל שהיא מכילה את כל הפונקציות הפרימיטיביות רקורסיביות, מבלי להוכיח ישירות שהן רקורסיביות.
-נוח מאוד להראות עבור פונקציות חישוביות רבות שהן פרימיטיביות רקורסיביות, ולכן מודל זה שימושי.
+למשל, על מנת להוכיח שהפונקציות האריתמטיות הבסיסיות הן [[פונקציה רקורסיבית|פונקציות רקורסיביות]], די להוכיח שכל פונקציה פרימיטיבית רקורסיבית היא גם פונקציה רקורסיבית. וכך, בכדי להראות היותר של פונקציה רקורסיבית, לעתים מציגים אותה כפונקציה פרימיטיבית רקורסיבית, ומכך גם רקורסיבית, בשל פשטות הדבר.
 == קשר למודלים חישוביים שונים ==
 קיימים קשרים מעניינים ביותר בין פונקציות פרימיטיביות רקורסיביות, ו[[פונקציה רקורסיבית|פונקציות רקורסיביות]]. בפרט, ניתן להראת שאם פונקציה היא רקורסיבית, ועוצרת תמיד לאחר מספר ידוע של צעדים (שחסום על ידי פונקציה פרימיטיבית רקורסיבית), אזי היא גם פרימיטיבית רקורסיבית.
-ולמרות שנובע מכך שפונקציות רקורסיביות רבות ביותר הן פרימיטיביות רקורסיביות, קיימות פונקציות רקורסיביות שאינן פרימיטיביות רקורסיביות, כמו לדוגמה [[פונקציית אקרמן]].
+למרות שנובע מכך שפונקציות רקורסיביות רבות ביותר הן פרימיטיביות רקורסיביות, קיימות פונקציות רקורסיביות שאינן פרימיטיביות רקורסיביות, כמו לדוגמה [[פונקציית אקרמן]].
 [[קטגוריה:סיבוכיות]]