חישוביות – הבדלי גרסאות

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

למעשה, מספר הפונקציות שניתן לחשב הוא [[אלף 0|<math>\!\, \aleph_0</math>]] (קרי: [[אלף 0|אֲלף אפס]]), מאחר שלכל בעיה חשיבה ניתן לכתוב תוכנית מחשב, ומספר תוכניות מחשב שאנחנו יכולים לכתוב הוא <math>\!\, \aleph_0</math>. מאידך, מספר השפות כולן הוא <math>\aleph</math> (ז"א, מ[[עוצמת הרצף|אלף]]).