מספר חשיב

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

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

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

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

שפות אחרות