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

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

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

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

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

הגדרה

מחלקה של פונקציות, בתורת החישוביות, נקראת סגורה תחת רקורסיה פרימיטיבית (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})$

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

דוגמאות

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

פונקציות כאלו הן, למשל:
$\ f(x,y)=x+y$
$\ f(x,y)=x\cdot y$
$\ f(x,y)=x^{y}$
$\ f(x)=x!$

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

שימושים

בהוכחות מתמטיות הדבר יכול להיות שימושי ביותר.

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

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

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

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

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