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

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

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

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

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

ערך מורחב – פונקציה פרימיטיבית רקורסיבית

קבוצת הפונקציות הרקורסיביות הפרימיטיביות מוגדרת להיות הקבוצה המינימלית, $\ PR^{(k)}$, של פונקציות מ-$\mathbb {N} ^{k}$ למספרים הטבעיים, שמקיימת את התנאים הבאים:

• הפונקציה הקבועה 0 נמצאת ב-$\ PR^{(k)}$.
• פונקציות ההטלה לקואורדינטה מסוימת נמצאות ב-$\ PR^{(k)}$.
• פונקציית העוקב $\ f(n)=n+1$ נמצאת ב-$\ PR^{(1)}$.
• הקבוצה סגורה תחת הרכבת פונקציות (במובן הרחב).
• הקבוצה סגורה תחת רקורסיה במובן הבא: $\ f\in PR^{(k)}$ ו-$\ g\in PR^{(k+2)}$ אז פונקציית הרקורסיה של f עם g היא הפונקציה h שמוגדרת על ידי:

$\ h(0,x_{1},\dots ,x_{k})=f(x_{1},\dots ,x_{k})$

$\ h(n+1,x_{1},\dots ,x_{k})=g(h(n,x_{1},\dots ,x_{k}),n,x_{1}\dots ,x_{k})$

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

קיימות $\aleph _{0}$ פונקציות רקורסיביות פרימיטיביות.

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

הפונקציות הרקורסיביות מתקבלות מהפונקציות הרקורסיביות-פרימיטיביות על ידי הוספת אופרטור, שמכונה אופרטור $\mu$ או אופרטור החיפוש. נסמן את קבוצת הפונקציות הרקורסיביות הפועלות על קלט בן k מספרים ב- $\ R^{(k)}$. אופרטור זה פועל על פונקציה רקורסיבית קיימת $\ f\in R^{(k+1)}$, ומחזיר את הפונקציה $\ \mu f(\in R^{(k)})$, שעבור הקלט $\ (x_{1},\dots ,x_{k})$ מחזירה כפלט את ה-y המינימלי שעבורו מתקיים השוויון $\ f(y,x_{1},\dots ,x_{n})=0$. y כזה לא בהכרח קיים, ורק אם הוא קיים הפונקציה עוצרת על אותו קלט. פונקציות אלו הן פונקציות חלקיות, כלומר הן אינן מוגדרות על כל קלט ולפעמים אפילו על שום קלט. לדוגמה הפעלת אופרטור $\mu$ על הפונקציה הפרימיטיביות-רקורסיבית הקבועה 1 תיצור בהכרח פונקציה שלא מוגדרת על שום מספר טבעי.

תוספת האופטור מגדילה בהרבה את החופש ביצירת הפונקציות ולפי תזת צ'רץ'-טיורינג- מספיקה כדי לבנות את כל האלגוריתמים הסבירים.

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

ראו גם

• רקורסיה
• מכונת טיורינג
• תזת צ'רץ'-טיורינג

קישורים חיצוניים

• פונקציה רקורסיבית, באתר אנציקלופדיה בריטניקה (באנגלית)
• פונקציה רקורסיבית, באתר MathWorld (באנגלית)
• פונקציות רקורסיביות, דף שער בספרייה הלאומית