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

תוכן שנמחק תוכן שנוסף
Felagund-bot (שיחה | תרומות)
בוט - מחליף 'דוגמא' ב'דוגמה', 'מסויים' ב'מסוים', 'מסויימ' ב'מסוימ', 'פונקצית' ב'פונקציית'
מ תיקון קישור
שורה 16:
: <math>\ h(n+1,x_1, \dots , x_k)=g(h(n, x_1, \dots , x_k) , n , x_1 \dots , x_k )</math>
 
הפונקציות הרקורסיביות הפרמטיביות כוללות את כל הפונקציות האריתמטיות, ופונקציות רבות נוספות, אבל קיימות פונקציות שניתנות לחישוב על ידי אלגוריתם סביר שאינן פרמטיביות (כמו [[פונקצייתפונקצית אקרמן]]), ולכן הגדרה זו לא עומדת בקריטריון של [[תזת צ'רץ'-טיורינג]].
 
קיימות <math>\aleph _0</math> פונקציות רקורסיביות פרמטיביות.