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

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

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

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

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

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

Postscript-viewer-shaded.png ערך מורחב – פונקציה פרימיטיבית רקורסיבית

קבוצת הפונקציות הרקורסיביות הפרימיטיביות מוגדרת להיות הקבוצה המינימלית, הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ PR^{(k)}} , של פונקציות מ-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \N^k} למספרים הטבעיים, שמקיימת את התנאים הבאים:

  • הפונקציה הקבועה 0 נמצאת ב-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ PR^{(k)}} .
  • פונקציות ההטלה לקואורדינטה מסוימת נמצאות ב-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ PR^{(k)}} .
  • פונקציית העוקב הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ f(n)=n+1} נמצאת ב-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ PR^{(1)}} .
  • הקבוצה סגורה תחת הרכבת פונקציות (במובן הרחב).
  • הקבוצה סגורה תחת רקורסיה במובן הבא: הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ f \in PR^{(k)}} ו-הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ g \in PR^{(k+2)}} אז פונקציית הרקורסיה של f עם g היא הפונקציה h שמוגדרת על ידי:
הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ h(0,x_1, \dots , x_k)=f(x_1, \dots , x_k)}
הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ h(n+1,x_1, \dots , x_k)=g(h(n, x_1, \dots , x_k) , n , x_1 \dots , x_k )}

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

קיימות הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \aleph _0} פונקציות רקורסיביות פרימיטיביות.

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

הפונקציות הרקורסיביות מתקבלות מהפונקציות הרקורסיביות-פרימיטיביות על ידי הוספת אופרטור, שמכונה אופרטור או אופרטור החיפוש. נסמן את קבוצת הפונקציות הרקורסיביות הפועלות על קלט בן k מספרים ב- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ R^{(k)}} . אופרטור זה פועל על פונקציה רקורסיבית קיימת הפענוח נכשל (שגיאת המרה. השרת ("https://en.wikipedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle \ f\in R^{(k+1)}} , ומחזיר את הפונקציה , שעבור הקלט מחזירה כפלט את ה-y המינימלי שעבורו מתקיים השוויון הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ f(y,x_1, \dots , x_n ) =0} . y כזה לא בהכרח קיים, ורק אם הוא קיים הפונקציה עוצרת על אותו קלט. פונקציות אלו הן פונקציות חלקיות, כלומר הן אינן מוגדרות על כל קלט ולפעמים אפילו על שום קלט. לדוגמה הפעלת אופרטור הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mu} על הפונקציה הפרימיטיביות-רקורסיבית הקבועה 1 תיצור בהכרח פונקציה שלא מוגדרת על שום מספר טבעי.

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

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

ראו גם