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