חישוביות – מילון עברי-עברי
חישובי
(ת')
שמקורו בחישוב, תחשיבי, חשבוני, מתמטי, הערכתי
חישוביות
תורת ה
חישוביות היא הבסיס ל
מדעי המחשב, והיא עוסקת במודלים לחישוב ובפונקציות הניתנות לחישוב במסגרתם. השאלה הבסיסית בתורת החישוביות היא: מה מחשבים יכולים לחשב, ומה לא? בניגוד להנחה נפוצה, ישנן פונקציות שאי אפשר לחשב. בעיית העצירה מהווה דוגמה לפונקציה שכזו: ניתן להוכיח כי אין תוכנית היכולה לקבל כקלט תוכנית כלשהי וקלט לאותה התוכנית, ולהכריע האם התוכנית תעצור. למעשה, מספר הפונקציות שניתן לחשב הוא 
(קרי: אֲלף אפס), מאחר שלכל בעיה חשיבה ניתן לכתוב תוכנית מחשב, ומספר תוכניות מחשב שאנחנו יכולים לכתוב הוא . מאידך, מספר הבעיות החישוביות כולן הוא 
(ז"א, מעוצמת הרצף). לכן, רק מהשוואת עוצמות, ניתן להסיק שבהכרח קיימות בעיות חישוביות אשר לא ניתנות לפתרון תחת מודלים חישוביים מסוימים, כדוגמת מכונת טיורינג.
