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

{{תקציר פורטל|מדעי המחשב}}

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

 

== היסטוריה ==