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

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

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

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

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

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

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

כל דרגה כוללת גם קבוצות של מספרים (למשל קבוצות שמייצגות את הגרף של פונקציה). אפשר להמיר בין פונקציות לקבוצות דרך זיווגים רקורסיביים. לכן פעמים רבות בונים דרגות על ידי בניית קבוצות מתאימות.

בכל דרגה יש בדיוק סופר-נמני (בניהול) של פונקציות, ולכן יש ממש הרבה דרגות טיורינג בסך הכל. מתחת לכל דרגה יש רק מספר בן-מניין של דרגות. קיימת דרגה מינימלית, הדרגה של פונקציות רקורסיביות (הפונקציות שניתן לחשב מאפס), שמסומנת ב-0.

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

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

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

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

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

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

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