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

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

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

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

[עריכה] פונקציה רקורסיבית פרימיטיבית

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

קבוצת הפונקציות הרקורסיביות הפרמטיביות מוגדרת להיות הקבוצה המינימלית, $\ PR^{(k)}$ , של פונקציות מ- $\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$ פונקציות רקורסיביות פרמטיביות.

[עריכה] פונקציה רקורסיבית

הפונקציות הרקורסיביות מתקבלות מהפונקציות הרקורסיביות-פרמטיביות על ידי הוספת אופטור, שמכונה אופרטור $μ$ או אופרטור החיפוש. נסמן את קבוצת הפונקציות הרקורסיביות הפועלות על קלט בן 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 ) =1$ . y כזה לא בהכרח קיים, ורק אם הוא קיים הפונקציה עוצרת על אותו קלט. פונקציות אלו הן פונקציות חלקיות, כלומר הן אינן מוגדרות על כל קלט ולפעמים אפילו על שום קלט. לדוגמה הפעלת אופרטור $μ$ על הפונקציה הפרמטיבית-רקורסיבית הקבועה 1 תיצור בהכרח פונקציה שלא מוגדרת על שום מספר טבעי.

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

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