הצגת המקור של הדף "מספר חשיב"

ב[[מתמטיקה]], ב[[מדעי המחשב]] ובלוגיקה חישובית, '''מספר חשיב''', הנקרא גם '''מספר רקורסיבי''', הוא [[מספר ממשי]] שאפשר לחשב אותו, בכל דיוק רצוי, בזמן סופי. החישוב יכול להתבצע על ידי [[מכונת טיורינג]], האמורה להחזיר את ה[[פיתוח עשרוני|ספרות]] של המספר בזו אחר זו. קיימות למושג הגדרות שקולות אחרות, במונחים של [[פונקציה רקורסיבית|פונקציות רקורסיביות]] או [[תחשיב למדא]]. מספרים אלו הוגדרו לראשונה על ידי [[אלן טיורינג]] כחלק ממחקרו בנושא בעיית ה[[כריעות]] (Entscheidungsproblem){{הערה|Turing, A.M. (1936), "[http://www.abelard.org/turpap2/tp2-ie.asp On Computable Numbers, with an Application to the Entscheidungsproblem]", Proceedings of the London Mathematical Society, 2 42: 230–65, 1937}}.

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

==הגדרה==
מספר <math>\ a</math> יקרא '''חשיב''', אם קיימת מכונת טיורינג  <math>\ M_a</math> שמקבלת כ[[קלט]] מספר <math>\ n</math> ו[[פלט|פולטת]] את ה[[בסיס בינארי|ייצוג הבינארי]] של <math>\ a</math> עד הספרה ה-<math>\ n</math>. באופן שקול ניתן להגדיר מכונה העובדת ב[[בסיס עשרוני]] ולא בינארי.

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

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

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

== ראו גם ==
* [[מספר בר-הגדרה]]
* [[פונקציה בת-חישוב]]

==קישורים חיצוניים==
{{מיזמים|ויקימילון=מספר רקורסיבי}}
* {{MathWorld}}
==הערות שוליים==
{{הערות שוליים|יישור=שמאל}}

[[קטגוריה:חישוביות]]
[[קטגוריה:מספרים ממשיים|חשיב]]