מספר חשיב

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

כל מספר אלגברי ממשי, לרבות המספרים הרציונליים, הוא חשיב. גם מספרים טרנסצנדנטיים רבים, כגון פאי ו-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$, בסתירה להנחה שזוהי סדרת כל המספרים החשיבים.

ראו גם

• מספר בר-הגדרה
• פונקציה בת-חישוב

הערות שוליים

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

35138328מספר חשיב