מספר חשיב

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

במתמטיקה, במדעי המחשב ובלוגיקה חישובית, מספר חשיב, הנקרא גם מספר רקורסיבי, הוא מספר ממשי שאפשר לחשב אותו, בכל דיוק רצוי, בזמן סופי. החישוב יכול להתבצע על ידי מכונת טיורינג, האמורה להחזיר את הספרות של המספר בזו אחר זו. קיימות למושג הגדרות שקולות אחרות, במונחים של פונקציות רקורסיביות או תחשיב למדא. מספרים אלו הוגדרו לראשונה על ידי אלן טיורינג כחלק ממחקרו בנושא בעיית הכריעות (Entscheidungsproblem)‏[1].

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

הגדרה[עריכת קוד מקור | עריכה]

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

הגדרה שקולה מבוססת על קירוב המספר \ a בין שני מספרים רציונליים קרובים כרצוננו. בהינתן קלט \ n המכונה \ M_a תפלוט מספר \ k, כך ש {k-1\over n} \leq a \leq {k+1\over n}.

אוסף המספרים החשיבים[עריכת קוד מקור | עריכה]

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

עם זאת, לא קיים אלגוריתם המונה את המספרים החשיבים. ניתן להוכיח זאת בלכסון בדומה לאלכסון של קנטור: נניח בשלילה כי קיים אלגוריתם M^* שפולט את סדרת המספרים החשיבים a_1, a_2, a_3,\ldots (ליתר דיוק בהינתן n ו-m האלגוריתם פולט את m הספרות העשרוניות הראשונות של n המספרים הראשונים בסדרה כלשהי של כל המספרים החשיבים). נגדיר אלגוריתם M שבהינתן קלט n, M פולט רצף של n ספרות עשרוניות באופן הבא: לקביעת הספרה ה-k ברצף, M מריץ את M^* כדי למצוא את הספרה ה-k של a_k (נמנעים מייצוגים עם אינסוף תשעיות חוזרות). אם הספרה ה-k של a_k היא 0, אז הספרה ה-k ברצף תהיה 1, ואם הספרה ה-k של a_k אינה 0, אז הספרה ה-k ברצף תהיה 0. האלגוריתם M מגדיר מספר חשיב a שנקבע על ידי רצף הספרות ש-M פולט. עם זאת, לכל k, a נבדל מ-a_k בספרה ה-k שלו, ולכן a אינו מופיע בסדרה a_1, a_2, a_3,\ldots, בסתירה להנחה שזוהי סדרת כל המספרים החשיבים.

ראו גם[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Turing, A.M. (1936), "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, 2 42: 230–65, 1937