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

 

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

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

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