מספר חשיב

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

מספר a נקרא חשיב אם קיימת מכונת טיורינג M_a שהנתונה קלט n מפיקה קירוב של a עד הספרה ה-n; אפשר להגדיר זאת בבסיס בינארי או עשרוני. נוסח שקול אומר: המכונה מפיקה מספר רציונלי k/n שקרוב ל-a עד טעות של 1/n. גרסאות שוות ערך של ההגדרה ניתנות גם במונחים של פונקציות רקורסיביות (פונקציות שנחשבות חישוביות) או תחשיב למדא (שיטת תיאור חישוב).

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

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

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

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