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