תורת הרקורסיה

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

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

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

בבסיס תורת הרקורסיה נמצא מושג הפונקציה הרקורסיבית - פונקציה מהטבעיים אל עצמם (פונקציה אריתמטית) שניתן לחשב באמצעות מכונות טיורינג. מכונת טיורינג בנויה מרצף של הוראות, כאשר יש רק מספר סופי של הוראות שונות (מספר זה תלוי באופן ההגדרה), ולכן עוצמת קבוצת מכונות טיורינג היא $\aleph _{0}$. יתר על כן, ניתן לבנות מכונת טיורינג שתקבל כקלט מספר טבעי e ותחזיר כפלט רצף של הוראות עבור מכונת טיורינג.
את המכונה שמתקבלת מהקלט e נסמן ב- $\ M_{e}$ והמספר e נקרא האינדקס של המכונה.

קיימות אינסוף שיטות שונות למנות באמצעות מכונה את כל המכונות. למעשה אי אפשר להצביע על מכונה ולומר שהיא $M_{0}$, כי בכל שיטת מנייה תתקבל מכונה שונה.

מספור המכונות יוצר מספור לפונקציות הרקורסיביות - את הפונקציה $\varphi _{e}$ מחשבים באמצעות המכונה $\ M_{e}$ כך ש-$\varphi _{e}(n)$ הוא הפלט של $\ M_{e}$ בהינתן הקלט n. זוהי פונקציה חלקית, כלומר - יכולים להיות ערכים שעליהם הפונקציה כלל לא מוגדרת (כי המכונה לא עוצרת), ואפילו קיימות פונקציות ריקות שהמכונות שלהן לא עוצרות על שום קלט. המספור אינו חד-חד ערכי - קיימות פונקציות רקורסיביות שאינדקס שמתאים להן שונה אף שהן מחזירות ערכים זהים על כל פלט.

פונקציה רקורסיבית עם אורקל

ניתן להרחיב את מושג הרקורסיביות כך שיכלול את האפשרות לחשב מידע מתוך מידע נתון, ולא רק חישוב מאפס. לצורת החישוב הזו קוראים פונקציה רקוסיבית עם אורקל. לפונקציות אלו יש מקור מידע חיצוני בצורת פונקציה מהטבעיים לעצמם, כך שבכל שלב המכונה יכולה לשלוח "שאלה" לפונקציה- מספר טבעי, והפונקציה מחזירה את התשובה (שהיא גם כן מספר טבעי). למקור המידע החיצוני, הפונקציה, קוראים אורקל, ובמקרים רבים התשובה שתתקבל, ואפילו עצם עצירת הפונקציה על קלט מסוים תלויה באורקל- עבור אורקלים מסוימים הפונקציה תחזיר תוצאה אחת ועבור אחרים היא תחזיר תוצאה אחרת. כמו שניתן למספר את הפונקציות הרקורסיביות, כך בהינתן אורקל g, ניתן למספר את כל הפונקציות הרקורסיביות עם אותו אורקל ולכן ניתן לסמן את הפונקציה הרקורסיבית עם אורקל g ה-e ב-$\varphi _{e}^{g}$. אם $\ f=\varphi _{e}^{g}$ נאמר ש f ניתנת לחישוב מ-g. כל פונקציה רקורסיבית רגילה היא פונקציה רקורסיבית עם האורקל g=0.

דרגות טיורינג

באמצעות המושג של פונקציה רקורסיבית עם אורקל נוצר יחס סדר בין מאגרי המידע השונים (שמיוצגים על ידי פונקציות שלמות מהטבעיים לעצמם). את היחס הזה מסמנים ב- $\leq _{T}$ (קרי: ניתן לחישוב מ-) והוא מוגדר: $\ f\leq _{T}g$ אם קיים אינדקס e כך ש- $\ f=\varphi _{e}^{g}$. זהו יחס רפלקסיבי היות שניתן לבנות מכונה שבהינתן קלט כלשהו היא תעביר אותו אל האורקל ואת התשובה תדפיס כפלט - כלומר כל פונקציה ניתנת לחישוב מעצמה. בנוסף זהו יחס טרנזיטיבי כי אם f ניתנת לחישוב מ-g ו-g ניתנת לחישוב מ-h, כלומר $\ f=\varphi _{e}^{g}$,$\ g=\varphi _{i}^{h}$, אז ניתן לכתוב את רצף ההוראות של המכונה ה-i בתוך המכונה ה-e כל פעם שכתוב "שאל את האורקל", וכך לקבל מכונה שמחשבת את f מ-h. יחס זה אינו אנטיסימטרי לדוגמה תמיד $\ f\leq _{T}2f,2f\leq _{T}f$ למרות שf ו- 2f שונים.

כדי להתגבר על הבעיה הזו מגדירים יחס שקילות שמבטא את הרעיון שבשני מאגרים יש, בסופו של דבר, את אותו מידע. זהו היחס $\equiv _{T}$ שמוגדר- $\ f\equiv _{T}g$ אם מתקיים $\ f\leq _{T}g$ וגם $\ g\leq _{T}f$. מחלקות השקילות נקראות דרגות טיורינג וקבוצת כל דרגות טיורינג מסומנת ב-D. על דרגות טיורינג יחס הניתנות לחישוב (שמוגדר על ידי נציגים) הוא יחס סדר חלקי.

דרגות טיורינג כקבוצות

בכל דרגת טיורינג יש פונקציה מציינת של קבוצת מספרים טבעיים כלומר פונקציה שמקבלת רק את הערכים 0 ו-1. ניתן לראות את זה על ידי מושג הגרף של פונקציה- הקבוצה $\left\{(x,f(x))|x\in \mathbb {N} \right\}$. ניתן לזהות כל קבוצה ב-$\mathbb {N} ^{2}$ עם קבוצת מספרים טבעיים באופן רקורסיבי לדוגמה על ידי הפונקציה החד חד ערכית ועל $\ (m,k)\rightarrow 2^{m}(2k+1)$ (או כל פונקציית זיווג אחרת). בצורה הזו ניתן להמיר בצורה רקורסיבית כל פונקציה לקבוצה וכל קבוצה לפונקציה.

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

תכונות בסיסיות של דרגות טיורינג

בכל דרגה יש בדיוק $\aleph _{0}$ פונקציות שונות, ולכן קיימות $\ 2^{\aleph _{0}}$ דרגות טיורינג שונות. בנוסף מתחת לכל דרגה יש רק מספר בן מנייה של דרגות, כי יש רק מספר בן מנייה של פונקציות רקורסיביות מנציג כלשהו של הדרגה.

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

לכל פונקציה $\ f$ ניתן לבנות בעיית עצירה משלה. זוהי הקבוצה $\ K_{f}=\left\{e\in \mathbb {N} :\varphi _{e}^{f}(e){\mbox{ halts}}\right\}$.
כמו שלא ניתן לחשב את בעיית העצירה על ידי פונקציה רקורסיבית כך לכל f לא ניתן לחשב ממנה את K_f. לעומת זאת, אפשר להראות שניתן לחשב מתוך K_f את f, ולכן הדרגה של K_f גדולה ממש מהדרגה של f. אם הדרגה של f היא a מסמנים את הדרגה של K_f ב-'a (נקרא a-קפץ), זו דרגה שגדולה ממש מהדרגה של a, ולכן לא קיימת דרגה מקסימלית.

ראו גם

• קבוצה רקורסיבית
• קבוצה ניתנת למנייה רקורסיבית
• בעיית העצירה

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0