פונקציה בת-חישוב

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

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

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

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

בין הדוגמאות החשובות ביותר לבעיות שאינן בנות חישוב אפשר למנות את: בעיית העצירה (K), בעיית המלה בחבורות מוצגות סופית (WP), הבעיה העשירית של הילברט (HTP), אוסף הפסוקים הנכונים בשפה מסדר ראשון של המספרים הטבעיים (עם הקבועים 0 ו-1, פעולות החיבור והכפל, ויחס הסדר) (TA), ועוד. בעיית העצירה ניתנת להכללה באופן הבא: לכל דרגת טיורינג f, מסמנים ב-'f את דרגת טיורינג הכוללת את כל התוכניות העוצרות בזמן סופי, שמותר להן להשתמש ב-f. זוהי קפיצת טיורינג. הקפיצה שומרת על יחס הסדר, ותמיד מקיימת $\ f<_{T}f'$ .

מתברר שסדר טיורינג בין בעיות טבעיות רבות, כגון אלה, הוא ליניארי. כך למשל $0<K\equiv WP\equiv HTP<TA$ . השערת מרטין (על שם דונלד מרטין) קובעת שעבור בעיות מסוימות סדר טיורינג ניתן לתיאור באמצעות שרשראות של קפיצות טיורינג.